strfriendを作ろうとすると、正規表現がスタック型の言語に見えてくる。

最初、"strfriend" という、誰かのブックマーク名だけ見たときは、 てっきり「友達リストを一発で返すAPI」かと思った。

strfriendがイケてないのは、改行やタブ、空白文字で整形した 正規表現記述 //x に対応していないこと。

関連: 正規表現実装の 処理方式の違いを説明するアニメーション。

/(?: [^\p{Han}]+ (\p{Han}+) )+ /x

[^\p{Han}]+は、漢字ではない文字の1文字以上の羅列。 \p{Han}+は、漢字(\p{Han})の1文字以上の羅列(+)だ。 後半の(\p{Han}+)の括弧のくくりで、この範囲の 文字列を、正規表現のキャプチャ文字列として返す。 さらに大きな外側の (?: ... ) 括弧では、このカッコ内が 繰り返しパターンとして(+)照合する形になっている。 ここで、+の特徴として、最後に照合して合致した文字列だけを 返すので、最後の漢字の羅列が取り出せる。

Perlの正規表現で、/x オプションを指定すると、正規表現内の スペース、タブ、改行は無視され、自由にスペースを入れたり 改行したり、インデントして記述でき、たいへんわかりやすい。 また、# に続けてコメント文も記述でき、これまたたいへん わかりやすい正規表現コーディングが可能になる。

が、正規表現内のコメント文内に / が現れると、 文法エラーになったり、0除算例外になったりするので注意。

0除算例外になる例:

% perl -e '$a="abc";$a=~/(b) #/co
/x;'

/$\d+\.txt$/

とあるのは、正規表現の最後に /ms オプションがついていればよさそうな気もしたが、

/$\d+\.txt$/ms

やはり正規表現最初の文字が ^ でないと、マッチしない。

/^\d+\.txt$/ms

これなら、マッチする

この一文字オペレータはどこか来た道。あ、sendmail.cf か。

• ^ は文字列の先頭ではなく行頭にマッチして欲しいな

• % man perlre
  ...
  Modifiers
  ...
  m   Treat string as multiple lines.  That is, change "^" and "$" from
      matching the start or end of the string to matching the start or
      end of any line anywhere within the string.
  

% time perl -e '
use utf8; \
use encoding "utf-8"; \
open(I,"200804file.html"); \
binmode(I, ":encoding(euc-jp)"); \
undef($/); \
<I>; \
for($n=0;$n<100000;$n++){$_ = s/a/b/isg;}'

ただの検索 /a/i; にしても、やはり長時間がかかる。

もともと UTF-8 のファイルを読み込んで、/a/i で検索すれば、 /i ありでも /i なしの 50% 増し程度の時間で完了するので、 use encoding の問題らしい。 かかる処理時間も、10万回の /a/i で 0.3秒。

UTF-8 での正規表現は日本語でもかなり自由に書けるようになった。

/ ( .+? ) ( [。？] ) /sx;

日記はいままでテキストファイルで書きためてあるのと、 DB に入れると、その DB の更新やらメモリなどのリソース調達やらで めんどうなので、テキストのままでいく。 あと、自分の日記にリクエストが来てあふれるということもない。

まず、日記を取り出す方法を次のようにした。

• 1か月分、日記のテキストファイルを全部読み込む
• 日別に分割する (split())
• 1日ごとに、記事に分割する (split())
• 記事ごとに、カテゴリラベル、タイトル、日付を取り出す

元の日記のテキストファイルは次のような構造になっている。

 <font size=+1><b>2008年4月29日 (火) くもりときどきはれ</b>lt;/font>lt;br>
        <blockquote>

        <blockquote>
        <br>
        <br>
        <br>

このようなテキストから、日ごとの文字列を配列を、split()で 取り出すための正規表現が、これ。

最後の /s は、改行文字を含めて正規表現を適用する、という意味。 /x は、正規表現の間にスペースやタブ、改行を入れて、読みやすく 表記できるようにするオプション。コメントも書ける。

  my $DAY_DELIMIT = /			# 正規表現を変数に設定する
	# 使うときは split(/$DAY_DELIMIT/, $string) とすればよい
	# 変数に設定するときは、/ は気にせず指定できる
  # (?: は、split(//) の正規表現部分に与えたときに、
  # split() の結果として配列に返してほしくないために指定する
  (?: 	
	[\r\n]+					# 改行の 1 つ以上の連続
	>font \s+ size=\+1> >b> 	# タグにマッチする
	(\d{4}) \D+ (\d+) \D+ (\d+)		# 年月日をとりだして配列にして返す
	[^(]+ \(([^)]+)\) 			# (水) などの曜日をとりだす。
	\s*					# 曜日のあとに空白が続くかもしれない
	([^<]+)				# < でない文字、タグでない文字列をとりだして返す
	>/b> >/font> >br>	# タグの羅列。正規表現を変数に設定するので / はそのまま
	\s+ 					# 改行を含む空白の連続
	>blockquote>			# blockquote タグ
	\s+ 					# 改行を含む空白の連続
	# ここまでが前半の区切り文字列のパターン
  |
	# ここから先が後半の区切り文字列のパターン
	[\r\n]+					# 改行の 1 つ以上の連続
	\t					# タブ文字
		# ここまで、空白 \s の連続と指定しまうと、ほかの場所で
		# マッチしてしまうため、特にわかっている形式を指定する。
	>/blockquote> 			# blockquoteタグの終了
	(?: \s+ >br> )+ )			# br タグの羅列。必要ないので (?: を指定する
  /sx;	# 正規表現の指定終了

ここで、日付単位の配列は1セット 6個になる。おもしろいのは、 上の正規表現の前半部分に、配列として返すグループが 6 個指定してあるが、 後半はないのに、それぞれ前半がマッチしても、後半がマッチしても、 それぞれ 6 個づつの配列を返してくる。

確かに、前半が6個で、後半が0個では、どちらにマッチしているのかわからない。 なので、どちらにマッチしても 6個の配列を返してくれれば、処理は簡単だ。 返ってくる配列は、

• HTMLヘッダなどを書いた、日記ファイルの冒頭部分
• 6個がセットになった、日ごとのデータ
  前半にマッチした場合は、先頭から順に、次のような配列になっている。
  1. 年 - 数字4桁
  2. 月 - 数字1桁 (あとで使いやすくするため 2 桁に直す)
  3. 日 - 数字1桁 (あとで使いやすくするため 2 桁に直す)
  4. 曜日 - 漢字一文字
  5. 天候 - 複数のひらがな
  6. 1以上の記事の連続 - 改行を含む
  後半にマッチした場合は、すべて空の配列が 6 要素で返ってくる。
• サイドバーやアドレスなどが書いてある、日記ファイルの末尾部分

次に、各記事を分割する。単独の記事は次のような構造になっている。

<img src="img/news-icon.png" align=right>
Network: Web: 会社で14:00ごろからgoogle.co.jpがつながらなくなっていた。
google.com も gmail も youtube.com もつながらなかった。
...

これを正規表現で書くとこうなる。

  / (?: \s* < [^>]+ >)*
  \s* ( (?: [^:\r\n]+? [^\s:] : \s+ )* )
  \s* ( [^。]+ )。(.*) /sx;

上と同じ正規表現をコメントを入れて説明しておく。 こちらは split() ではなく、すでに取り出した文字列に 正規表現を適用して (=~)、括弧のグループ指定を使って、 特定の部分だけを配列としてとりだす形になっている。 そのため、括弧のグループで指定されていない部分は、 読み捨てる形になる。

 my @article = ($_artString =~ /	# $_artStringから、記事を分割する
  (?: \s* < [^>]+ >)*			# 記事冒頭にある HTML タグの連続を削除

  # カテゴリのラベル文字列の連続をかたまりで取り出す
  \s*
  (					# 空白文字列の連続があるかもしれない
    # ひとつの文字列で返るので、あとで split() すること
    (?:		### (?: ...)* という書き方をする
	[^:\r\n]+? 			# : でも改行文字でもない連続 (1行内だけ注目する)
					# 次の、直前に空白がない、を検査するため、+? にする
	[^\s:] 				# : の直前は空白ではない ... カテゴリ文字列は2文字以上
					# "C" などのカテゴリのラベル文字列は使えない
	: 				# コロン文字1文字
	\s+ 				# 空白文字が 1 文字以上 (:   ) のようになっているはず
    )*		### (?: ...) は配列として返らないが、この複数マッチをまとめて次の括弧で返す
  )		### この括弧で、カテゴリ文字列の組の複数マッチを一度に返す

  # タイトル文字列の取り出し
  \s* ( [^。]+ )。			# タイトル文字列は、。までの文字
  (.*)					# それ以後は本文

  /sx); 

けっこう長くて気持ちが良い。 ここで、正規表現のグループの繰り返しについて。 ()* というように、グループを繰り返し指定すると、 これにマッチしたときには、マッチしたときの最後のマッチ文字列ひとつだけが返る。 そのため、"Network: IPv6: " のような文字列があると、 最後の IPv6: しか返ってこない。

そのため、マッチするための文字列は (?:...) で囲み、 複数マッチする、(?:...)* をさらに普通の括弧で囲んで、 ( (?:...)* ) としている。

こういう、正規表現のどの位置で何がマッチしたので、どの変数に 積み込むか、という作業を簡単にできそうなのが、 Perlの(... (?{code}))。

この "(?{ code })" は、正規表現のパターン中に、 その合致範囲 "()" に対してどのような処理ができるか コードを記述できる。$^N 変数から、マッチした文字列を とりだして、別の変数にセットできる。

また、()* のような正規表現を利用して、

( a (?{ local $cnt++; } ) )* 

"(?{ code })" は深いネストがある正規表現内で、 特定部分のマッチ文字列をとりだしたいときに便利そう。 ()がネストしたり、条件分岐が増えると、特定のマッチ文字列を とりだしにくくなる。

また、短い文字列に対して//を何度も呼ぶときに、 処理時間がかかるように感じられた。長い文字列(10KBほど)を正規表現で 検索しても、それほど時間がかからなかった。正規表現のコンパイルに 時間がかかるのか？＞Perl 5.8.8。

sprintf("%02d", $d);という書き方ももったいないので ($d < 10) ? "0" . $d : $d;という書き方にした。 ただし、処理速度に関して、この影響はあまりなかったもよう。

なんとなく、配列の添え字($arr[$i])も遅そうだったので、 配列のエレメント (foreach $element (@arr)) を 直接扱うようにした。

年月日の文字列を作ろうとして、 $y年$m月としたが、$y と "年" が連続した変数として みなされたようで、$y が展開されなかった。そのため、 ${y}年${m}月とした。UTF-8でも変数が記述できる弊害か？

どこが遅いか調べるために、 perl のスクリプト中に時刻を表示するデバッグ文を入れまくった。 いやはや。

正規表現 a*b|b*a の例では、最初に a を入力したとき、 非決定論的遷移図では、正規表現前半の a*b の a* にマッチした可能性が 青い一重円で表され、正規表現後半の b*a の a にマッチして マッチ完了した可能性が二重丸の緑色の円で示されている。 この両方の可能性が考えられるため、非決定論的遷移図では、 a*b の途中経過にある場合と b*a にマッチした場合の両方を保持する、 ということになる。このように複数の状態を保持すると、状態遷移のベクトル検索が 複雑になり、計算量が多くなり、計算時間を予測しにくくなる。 一方、決定論的な遷移図では、複数の状態は持たず、常に状態を 一つの記述として、その分岐ベクトルは正規表現全体の評価から 派生させるようにしている。そのため、遷移図を作ると、各状態からの ベクトルの本数を計算すれば計算量が予測できる。状態を保持する数も 1でよい。

このような説明は、たしかオライリーのPerl5の本に書いてあったような 気がする。読んだ当時は何を言っているのかよくわからなかったが、 このような図にして、例が示されると非常にわかりやすい。