前のドキュメント
ＶｉＶｉの正規表現処理について説明する。
チョムスキーの言語理論によれば、形式文法はクラス０〜３に分類できる。正規表現は生成規則の制約が最も強いクラス３に属し、入力文字列が与えられた正規表現として受理されるかどうかを有限オートマトンにより決定することが出来る。
有限オートマトンとは下図の様に（有限の）状態と、入力文字によりどの状態に遷移するかの規則により構成されるものである。
'a' 'b' ○────→○────→◎ q0 q1 q2
上図では３つの状態、q0, q1, q2 があり、'a' が入力されると状態 q0 から q1 に遷移し、'b' が入力されると q1 から q2 に遷移することを表す。q2 は受理状態なので、"ab" が入力文字列であれば、めでたく受理されることになる。
正規表現を有限オートマトンに変換する場合、ひとつの状態から複数の状態に分岐可能である様に変換する方が楽である。たとえば (ab|ax) は以下のような有限オートマトンに対応させることができる。
'a' 'b' ○────→○────→◎ │ 'a' 'x' ↑ └────→○─────┘
このような場合、'a' が入力された場合、２つの状態が有効になる。また、正規表現の閉包の場合は繰り返しを行うので無条件に遷移する規則（これをε遷移と呼ぶ）を導入すると便利になる。このように入力に対し遷移状態が一意に決定しないものを非決定性オートマトン（ＮＦＡ）と呼ぶ。これに対し、最初の図のように遷移状態が一意に決まるものは決定性オートマトン（ＤＦＡ）と呼ばれる。
正規表現はこれから示す簡単な手順により非決定性オートマトンに変換することができる。
exp ○────→◎
の様に初期状態を最も左に、受理状態を最も右に配置するように変換する。
"str" ○────→◎
これは、
's' 't' 'r' ○────→○────→○────→◎
を省略した表記であるが、文字列をつなげることを“連接”と呼ぶ。
exp* ε ┌─────┐ │ exp ↓ ○────→◎ ↑ ε │ └─────┘
同様に、１回以上の繰り返し（+）、０回または１回の繰り返し（？）は以下のように変換される。
exp+ exp? ε ┌─────┐ exp │ exp ↓ ○────→◎ ○────→◎ ↑ ε │ └─────┘
(exp1|exp2) ε ┌───────┐ exp1 │ exp2 ↓ ○────→○ ○────→◎ │ ε ↑ └───────┘
上記のルールを再帰的に適用することで、正規表現文字列を非決定性オートマトンに変換できる。この手順で得られる有限オートマトンはε遷移以外の条件遷移はある状態からすぐ右の状態にのみ遷移することが保証される。このことは有限オートマトンを逆順に処理する時に利用される。
通常はこれを処理が容易な決定性オートマトンに変換する。しかし、場合によっては決定性オートマトンは膨大な大きさになる場合はある（たとえば ”......A” のような場合）。そこで、決定性への変換を場合により遅延させるか、非決定性のままで処理を行うことになる。従来は非決定性オートマトンを効率よく処理できなかったが、ＶｉＶｉで使用しているアルゴリズムでは処理を効率的に行うことが可能である。
非決定性有限オートマトンを処理するモジュールをＮＦＡエンジンと呼ぶ。これは遷移状態を内部変数として持ち、状態遷移規則に従ってそれを変化させていく。
ＶｉＶｉの実装では各状態を１次元に並べ、各ビットが０か１かで状態が有効かどうかを表す（１ならば有効）。ビットオーダはどちらでもいいのだが、処理の都合でビット０が初期状態を表すこととする。これは単なる数値であるから、ひとつの整数で表現できる（これをレジスタと呼ぶ）。状態数はそのビット数で制限される。ＶｉＶｉでは３２ビット整数を用いているので、状態数の上限は３２となる（倍の６４がいいかもしれないが、遷移処理のためのテーブルが膨大になるので、３２ビットとした）。
●が有効な状態であるとき、
○────→●────→○────→◎
は、0x00000002 で表現されることになる。この例では有効な状態はひとつだけであるが、非決定性オートマトンでは複数の状態が有効になり得るので、１になるビット数はひとつだけとは限らない。状態数がｎであれば、状態を表す数値は０〜2^n - 1 の全ての値をとり得ることになる。
状態遷移規則は、どの状態からどの状態に遷移が可能なのかと、その時の文字で表現される。形式的には δ(qi, ch) = qj と表現できる。qi qj は状態で ch は遷移するための文字である。文字による状態遷移は右隣の状態にのみ遷移するという制約があるので、j = i + 1 である。よって、ある状態（Ｒ）から遷移可能な状態はＲを１ビット左にシフトすること（R << 1）で取得することが出来る。
入力文字による状態遷移であるが、各文字により遷移可能な状態は決まっているので、各文字について遷移可能な状態を保持するテーブルを作成するとよい（cv_table[]）。たとえば、"vivid" という正規表現に対応する有限オートマトンは、
'v' 'i' 'v' 'i' 'd' ○────→○────→○────→○────→○────→◎ q0 q1 q2 q3 q4 q5
であるから、'v' により遷移可能な状態は、q1, q3 である。従って遷移可能状態テーブルの値は 0x0000000a となる。正規表現では [ ] により複数の文字列で状態遷移する場合もある。その時は該当する文字のテーブル値の遷移可能状態に対応するビットを１にしておけばよい（解るかな？）。たとえば、"a[xy]" は、
'a' 'x','y' ○────→○────→◎
なので、
cv_table['a'] = 0x00000002
cv_table['x'] = 0x00000004
cv_table['y'] = 0x00000004
cv_table[上記以外] = 0x00000000
となる。
文字による遷移可能テーブル（cv_table）を使用すれば、入力文字 ch による状態遷移は、
R = (R << 1) & cv_table[ch];
で処理できる。これはシフト演算とテーブルを引いて論理積を計算するだけなので、非常に高速である！！！
正確にはε遷移の処理も必要である。これは文字による制約は受けないので、状態遷移テーブルを作成する。状態はひとつの数値であるから、そのサイズの遷移テーブル e_table[] を用意すれば、
R = e_table[R];
で遷移先の状態を求めることができる。R の上限は 2^32 - 1 なので、このように巨大なテーブルを用意することは現実的ではない。そこで、レジスタの８ビットごとに遷移テーブルを作成する。そうすれば、
R = e_table1[R & 0xff] | e_table2[(R>>8) & 0xff] | e_table3[(R>>16) & 0xff] | e_table4[(R>>24) & 0xff];
で、遷移先の状態を求めることができる。テーブルサイズは 256 * 4 * 4 = 4096 バイトで、今日では全く問題にならないサイズである。レジスタの初期状態は 0x00000001 であるが、まずε遷移を行って処理を始めねばならない。
受理判定は受理状態を表すビットが１になったかどうかを見るだけでよい。また、上記処理は受理したかどうかの判定については状態遷移を開始する文字位置による干渉を受けない。これらを考慮すると、ＮＦＡエンジンは以下のように記述できる。
typedef unsigned int NFAstat;
NFAstat R = 1 | e_table[1]; // 初期状態とそこからのε遷移状態
NFAstat end = 受理状態の整数値; // 受理状態に対応するビットのみが１
while( (R & end) == 0 ) { // 受理状態ではないあいだ
char ch = 次の文字; // 入力から１文字取得（文字が無くなったら受理しない）
R = (R << 1) & cv_table[ch]; // 遷移可能な状態と文字による遷移可能な状態のＡＮＤ
R |= e_table[R | 1]; // 初期状態を有効にし、ε遷移
}
// 受理された
状態遷移の具体例として、正規表現が“vivid”、入力文字列が“vivivid”の場合を以下に示しておく。○ は各状態を、◎は受理状態を、●は状態が有効であることを表す。表は１文字入力した結果の状態を表わす。
'v' 'i' 'v' 'i' 'd' ○────→○────→○────→○────→○────→◎ q0 q1 q2 q3 q4 q5 q0 q1 q2 q3 q4 q5 -------- ----------------- 初期状態 ● ○ ○ ○ ○ ◎ v ● ● ○ ○ ○ ◎ i ● ○ ● ○ ○ ◎ v ● ● ○ ● ○ ◎ i ● ○ ● ○ ● ◎ v ● ● ○ ● ○ ◎ i ● ○ ● ○ ● ◎ d ● ○ ○ ○ ○ ●
前節に示した手順で正規表現が入力文字列を受理するかどうかを決定できる。grep では受理するかどうかが判定できれば十分であるが、通常の検索や置換ではマッチした文字列の開始位置と終了位置を取得しなくてはならない。ところが上記ＮＦＡエンジンは入力文字列を同時並行的に処理しているので、受理された時に一致箇所がどの位置から始まったかが解らない。各状態に開始位置情報を持たせることも考えられるが、処理の高速性を考えるとＮＦＡエンジンの単純性が損なわれるので好ましくない。そもそも入力文字列が受理される確率は低く、検索などでは受理した時点で処理が終了するので、受理後に文字列位置を決定するのがよいと考えた。
おもしろいことに有限オートマトンは受理状態から初期状態に向かって状態遷移させても受理するかどうかを正しく判定できる（可逆性がある）。そこで、逆方向のε遷移状態のテーブル re_table[] を用意し、文字列を逆に走査することで一致する最初の位置を求めることができる。cv_table[] は順方向のものを利用可能である。通常の文字による状態遷移は、必ず隣の状態（ q(n) から q(n+1) ）にのみ可能なように有限オートマトンを構成しておけば、逆走査の場合は順方向の遷移先情報を１ビットシフトすればよい（rcv_table[R] == cv_table[R] >> 1）ことになる。
NFAstat R = re_table[受理状態の整数値];
while( (R & ~1) != 0 ) { // 初期状態のみに達するまで
char ch = 前の文字; // 入力文字列を逆方向に走査
R = (R & cv_table[ch]) >> 1; // 遷移可能な状態と文字による遷移可能な状態のＡＮＤ
R |= re_table[R]; // ε遷移
}
// マッチした最初の位置にいる
最長一致をもとめるためには、入力文字列を再度順方向に走査するとよい。ただしこの時は毎回の初期状態有効化を行わない。
NFAstat R = e_table[1]; // 初期状態とそこからのε遷移状態
while( (R & ~end) != 0 && // 一致しているあいだ
次の文字が存在する )
{
char ch = 次の文字; // 入力から１文字取得
R = (R << 1) & cv_table[ch]; // 遷移可能な状態と文字による遷移可能な状態のＡＮＤ
R |= e_table[R]; // ε遷移
}
// 最長一致の位置にいる
この手順でマッチした最初の位置と最長一致の最後の位置を取得することができる。これを受理後最長一致法と呼ぶ。この手順は入力文字列を１往復半走査するが、その様子が文字“Ｚ”のようであるので、“Z-method”とも呼んでいる。:-p
具体例として、正規表現“ab*”、入力文字列“xabbbc”の場合を示しておく
ε ┌─────┐ 'a' │ 'b' ↓ ○────→○────→◎ q0 ↑q1 ε │q2 └─────┘ q0 q1 q2 -------- -------- 初期状態 ● ○ ◎ x ● ○ ◎ a ● ● ● // 受理 初期状態 ○ ● ● a ● ○ ○ x ○ ○ ○ // 先頭位置を発見 初期状態 ● ○ ◎ a ○ ● ● b ○ ● ● b ○ ● ● b ○ ● ● c ○ ○ ◎ // 最終位置を発見
:s/([a-z]+)/\1\1 の様に一致した文字列の一部分を置換パターンで参照する場合がある。これを可能にするにはマッチした文字列のどの部分がカッコでくくられた部分に対応するかを決定しなくてはならない。そのためにｎ番目のカッコに対応する状態のリストを作成する。たとえば、([a-z]+)=([a-z]+) の場合、非決定性有限オートマトンは、
[a-z] '=' [a-z]
○────→○────→○────→◎
↑q0 │q1 ↑q2 │q3
└─────┘ └─────┘
なので、最初のカッコには q1 が、２番目のカッコには q3 が対応する。これを数値で表せば、0x00000002, 0x00000008 となる。これを対応状態情報と呼び、m1, m2 ... で表記する。
次に最長一致を求めるとき、ε遷移を行う直前の有効状態、すなわち入力文字による遷移状態を保存しておき、これと対応状態情報とのＡＮＤをとることで対応する文字列を取得する。 たとえば、上記の正規表現に対し、入力が“aaa=bb”であれば、遷移状態と対応状態とのＡＮＤは以下のようになる。
遷移状態 and m1 and m2 a 0x00000002 0x00000002 0x00000000 a 0x00000002 0x00000002 0x00000000 a 0x00000002 0x00000002 0x00000000 = 0x00000004 0x00000000 0x00000000 b 0x00000008 0x00000000 0x00000008 b 0x00000008 0x00000000 0x00000008
これより、ＡＮＤ結果が０で無い部分を拾い出して、\1 = "aaa"、\2 = "bb" を得ることができる。
しかし、この手順ではうまく行かない場合が存在する。たとえば、正規表現 ((ab)+)ac に対し入力が "ababac" の非決定性オートマトン、有限場合の遷移状態は以下のようになる。（m1 は 0x00000006 である）
a b a c
○────→○────→○────→○────→◎
↑q0 ε q1 │q2 q3 q4
└───────────┘
遷移状態 and m1
a ○ ● ○ ○ ◎ 0x00000002 0x00000002
b ○ ○ ● ○ ◎ 0x00000004 0x00000004
a ○ ● ○ ● ◎ 0x0000000a 0x00000002
b ○ ○ ● ○ ◎ 0x00000004 0x00000004
a ○ ● ○ ● ◎ 0x0000000a 0x00000002
c ○ ○ ○ ○ ● 0x00000010 0x00000000
よって、\1 = "ababa" となってしまう。
これを避けるために逆順に遷移する場合も遷移状態を保持することにし、それらのビットごとの論理積をとるようにする。これにより不要な尻尾部分が削除され、正しい部分文字列を取得することができる（数値は１６ビットで表記する）。
順遷移状態 逆遷移状態 and m1 a ○ ● ○ ○ ◎ 0x0002 ● ○ ○ ○ ◎ 0x0002 0x0002 b ○ ○ ● ○ ◎ 0x0004 ○ ● ○ ○ ◎ 0x0004 0x0004 a ○ ● ○ ● ◎ 0x000a ● ○ ○ ○ ◎ 0x0002 0x0002 b ○ ○ ● ○ ◎ 0x0004 ○ ● ○ ○ ◎ 0x0004 0x0004 a ○ ● ○ ● ◎ 0x000a ○ ○ ● ○ ◎ 0x0008 0x0000 c ○ ○ ○ ○ ● 0x0010 ○ ○ ○ ● ◎ 0x0010 0x0000
[1] Ricardo Baeza-Yates, Gaston H. Gonnet: "A New Approach to Text Searching ", COMMUNICATION OF THE ACM Oct/1992, Vol.35, No.10
[2] Sun Wu, Udi Manber: "Fast Text Searching Allowing Errors", COMMUNICATIO N OF THE ACM Oct/1992, Vol.35, No.10
[3] Sun Wu, Udi Manber: "AGREP - A FAST APPROXIMATE PATTERN-MATCHING TOOL" (Preliminary version),
[4] Sun Wu, Udi Manber: "Fast Text Searching With Errors", June 1991
[5] Udi Manbar, Sun Wu: "Approximate Pattern Matching", NOVEMBER 1992, BYTE
since 04-Apr-1998
前のドキュメント
Copyright (c) 1998 by Nobuhide Tsuda, All Right Reserved.
このホームページに関するご質問、ご要望、バグレポート等は
ntsuda@beam.ne.jp
までメールをいただければ幸いです。