大規模Aho-Corasickオートマトンにおける追加更新手法の提案 An

DEIM Forum 2012 F11-5
大規模 Aho-Corasick オートマトンにおける追加更新手法の提案
石崎 文規†
遠山 元道 ††
† 慶應義塾大学理工学部理工学研究科 〒 223–8522 神奈川県横浜市港北区日吉 3–14–1
E-mail: †[email protected], ††[email protected]
あらまし
文字列テキストからキーワード集合に含まれる語およびその位置を探し出す辞書式マッチングは，情報検
索において重要な問題である．これを実行するオートマトンは文字列マッチングマシンと呼ばれ，入力テキストの１
回の走査で複数のキーワードとその位置を発見する Aho-Corasick 法 [1] などがある．辞書語集合が変化した際に AC
マシンを再構築するよりも動的更新を行う手法が有用であることが既存手法によって提案されている．本研究では，
AC マシンの動的追加更新において，AC マシンとは別に木構造のインデックスを持たせることにより既存手法よりも
高速な追加更新手法を提案する．
キーワード
Aho-Corasick 法
An Incremental Update Algorithm for Large Aho-Corasick Automaton
Fuminori ISHIZAKI† and Motomichi TOYAMA††
† ††Department of Information and Computer Science ,
Keio University
Hiyoshi 3–14–1, Kouhoku-ku, Yokohama-shi, Kanagawa, 223–8522 Japan
E-mail: †[email protected], ††[email protected]
Key words Aho-Corasick algorithm
1. は じ め に
点を高速で見つけられるようにすることで AC マシンの動的更
新速度と初期構築時間を改善した．
Aho-Corasick 法は辞書式マッチングを行うためのアルゴリ
以下，本稿の構成を示す．まず 2 章で Aho-Corasick 法の概要
ズムであるが，予め辞書語を使ったオートマトンを構築してお
と逆 Failure 集合を使ったの追加更新手法を述べる．次に，3
く．そのオートマトンは, トライ法を拡張して AC マシンと呼
章では関連研究である Expect 関数について述べて，4 章で
ばれる一種の有限オートマトンであるが, それを利用して高速
expect-tree の構築方法と expect-tree を使った追加更新方法に
に辞書式マッチングを行っている．新しい単語を検出できるよ
ついて述べる，そして，5 章で本研究の評価を行い，最後に 6
うにオートマトンを更新する場合，別なメモリに新たなオート
章で結論について述べる.
マトンを構築し，構築完了後切り替えると言った手法が使われ
ている．しかしその手法では更新結果がすぐに反映されない欠
2. Aho-Corasick 法
点がある．そこで津田らの研究 [3] では逆 Failure 集合をオー
2. 1 概
トマトンに持たせることにより動的更新処理を高速化してい
AC 法は，トライ法を拡張して AC マシンと呼ばれる一種の
要
る．しかしその手法では新たに追加する節点への Failure 遷移
有限オートマトンを構築する．AC マシンは Goto 関数，Failure
する節点を見つけるのに時間がかかる問題があった．また，動
関数，Output 関数から構成される．Goto 関数は節点 s から
的更新処理を高速化するために yabu らの研究 [2] では，ある
遷移種αによる遷移先節点 t を返し，Goto(s，α) = t と表す．
節点がどの文字列を表す節点が追加された時に Failure 遷移す
遷移が未定義である場合は失敗を表す fail を返す．Failure 関
る事を期待しているかを定義した Expect 関数を使うことで，
数は Goto 関数が fail を返した際に呼び出され，遷移失敗時に
動的更新処理の高速化を実現した．しかしこの手法では初期構
おける節点 s からの遷移先節点 f を返し，F ailure(s) = f と
築時間に時間がかかりすぎる問題があった．そこで本研究では
表す．以下，Goto 関数，Failure 関数による遷移をそれぞれ
expect-tree と呼ぶ木構造のインデックスをオートマトンに持
Goto 遷移，Failure 遷移と呼ぶ．Output 関数は，Goto 遷移に
たせることで逆 Failure 集合と追加節点に Failure 遷移する節
より到達した節点 s において検出するキー集合 Os を出力し，
Output(s) = Os と表す．Output 関数により出力するキー集合
2. 4 AC 法の追加更新の問題点
しかしこの手法では追加節点の親節点の逆 Failure 集合の数
Os を Output 集合と呼ぶ．
図 1 がキーワード集合 (abcde，bcd，c，de) を検出するオー
が多い場合に比較回数が増えるためにコストが大きい問題があ
トマトンである．実線が Goto 遷移，破線が Failure 遷移を表
る．特に追加した節点の親節点がルート節点の場合を考えると
す．破線が存在しない節点の Failure 遷移先は初期節点とする．
比較回数は膨大なものとなる．逆に Us の逆 Failure 集合の数
は大して大きくない事が多いので問題にならない．
図 1 AC オートマトン
図 2 AC オートマトン (追加後)
2. 2 AC マシンによる文字列照合
図 1 を用いてテキスト (bcde) における照合例を示す．まず，
初期節点 0 において，Goto(0，b) = 6 により，節点 6 へ Goto
遷移する．次に Goto(6，c) = 7 により節点 7 へ遷移する．ここ
0
で，節点 7 がアウトプット集合を持つので，Output(7) = c
0
3. Expect 関数
新規追加節点に Failure 遷移する節点を高速で見つけるた
めに yabu らの研究 [2] では,Failure 関数の更新を期待する節
を検出する．その後，goto(7，d) = 8 により節点 8 に遷移す
点一覧を転移インデックスとしてもたせておく. 例えば図 1 を
る．ここでもアウトプット集合を持つので，Output(8) =0 bcd0
見ると,’abcde’ を表す節点 5 の Failure 遷移先は’de を表す’ 節
を検出する．次に Goto(8，e) = f ail となるので, 節点 8 の
点 11 と定義されている. この時もし’cde’ や’bcde’ を表す節点
F ailure 関数を見る. そこで,F ailure(8) = 10 なので節点 10 に
が生成されればこれらの節点は節点 5 にとって最長の接尾辞
Failure 遷移する．Goto(10，e) = 11 なので，節点 11 に遷移
となる. そこで, 節点 5 はこれらの節点の生成を期待している
し，Output(11) =0 de0 を検出する．これで, テキストが終了な
と考え,Expect(”cde”) = 6，Expect(”bcde”) = 6 で表される
ので, 文字列集合は終了となる.
Expect 関数を定義しておく．これによって，もし新たに’cde’
2. 3 AC 法の追加更新
を表す節点が生成された場合，Expect(”cde”) を参照すること
次に図 1 に新キーワード’cd’ を追加した AC マシンが図 2 で
で，即座に Failure 関数更新対象となる節点を見つけることが
ある．ここではどのように図 1 から図 2 のようにオートマトン
を更新するかを説明する. まず図 1 から’cd’ を追加するために,
できる．
3. 1 Expect 関数の問題点
ルート節点から’c’ への遷移 Goto(0，c) = 9 が存在するので，節
この手法の大きな欠点は AC マシンの構築に時間がかかり過
点 9 に遷移する．次に Goto(9，d) が存在しないので，新節点
ぎる点である．例えば，n 文字の単語を表す節点の Failure 遷
12 と Goto(9，d) = 12 を追加する．次に，F ailure(12) = 10
移先がルート節点 (節点 0) であった場合，Expect 関数はその
を追加し，Output を更新し Output(12) =0 cd0 とする．ここ
節点において n − 1 個定義しなくてはならない．実際に，英語
まではインクリメンタルな更新が可能だが，節点 12 へ Failure
版 wikipedia の見出し語 200 万件を辞書語とした AC マシンを
遷移するものを探すことが問題になる．
構築するのに構築に時間がかかりすぎて測定不能であった．
そこで津田らの研究 [3] では節点 s に failure 遷移する集合を求
める逆 Failure 関数，RF ailure(s) = RFs (RFs は s を failure
4. Expect tree
遷移とする節点集合) を用いて更新を行っている．例えば, 節点
そこで, 上記の問題を解決し, 新規追加節点に Failure 遷移す
12 の親節点 9 の逆 Failure 集合を RF ailure(9) = t1 , t2 , ..., tn
る節点集合を即座に求めるために本研究では Expect Tree と呼
とした場合, 節点 ti から Goto(ti ，d) = u となる節点 u が節
ぶトライ木構造の被 Failure 節点数のサブツリーを作ることを提
点 12 への Failure 遷移なので F ailure(u) = 12 になる．また，
案する. 新規追加節点を s とし，s の Failure 遷移先を t とする．
Goto(ti ，d) = f ail である場合,ti の逆 Failure 集合の節点から d
その時，s に対して新しく Failure 遷移する節点 s1 , s2 , ..., sn は
で Goto 遷移できる節点が節点 12 への failure 遷移となる．また，
元々t の逆 Failure 集合 t1 , t2 , ..., tm の一部であると言うことを
節点 s を新たに Failure 遷移とした集合を Us = u1 , u2 , ..., un
利用して Expect Tree を構築し，それを使用することで高速に
とした場合，ui の逆 Failure 集合のアウトプット集合に s のア
s へ Failure 遷移する節点集合を求める手法を示す．
ウトプット値を加える必要がある．
4. 1 Expect Tree の構築
節点数 N ，節点を s1 , s2 , ...sn と表した時，Expect Tree の
構築のアルゴリズムはアルゴリズム 1 になる．図 3 は節点 5，
8 で Ecpect Tree を構築した後のものであり, 図 4 が Expect
Tree を全て構築した後の図である. Expect tree の構造は expBase 関数，expGoto 関数，expOutput 関数で構成されている.
expBase 関数は AC マシンの節点 s から expect tree の節点 t
へのポインタであり，expBase(s) = t のように構成され，図
の破線である。expGoto 関数と expOutput 関数は AC マシン
の Goto 関数，Output 関数とほぼ同じものであり，expOutput
関数は図では節点部分にある黄緑の□で書かれている部分で
あり，Output の値は節点番号を意味する値である．次にどの
図 4 Expect Tree(構築完了後)
ように Expect Tree を作っていくかをアルゴリズムに沿って
図を使って説明する．まず予め，各節点に置いて以下の処理を
トプット集合を得る関数を getF ailure 関数とし，関数はア
施して Expect tree を構築する．次の説明は具体的にするた
ルゴリズム 2 で表される．getF ailure 関数を使うことで，例
めに節点 5 についてのものである．図 1 が構築前, 図 3 が構
えば，節点 t の逆 Failure 集合 Ft は getF ailure(expbase[t])
築途中, 図 4 が構築後である. まず，図 1 を見ると, 節点 5 の
で求めることもできる．また，文字列’abc’ の節点を t とし
Failure 遷移先 (節点 11) の expBase(11) が存在しないので，
た場合，getF ailure(expgoto(expbase(t),0 d0 )) は文字列’dabc’
expBase(11) = ex0 と新規節点 exp0 を作成する．次に節点 5
に Failure 遷移する集合となる．これらを利用して実際に図
の文字列 (abcde) と節点 11 の文字列 (de) の差である’abc’ を逆
3 に’cd’ が追加された場合にどのように cd へ Failure する集
から処理していく (c → b → a と言う順番で処理をする) 文字が
合を見つけるかについて述べる．’cd’ の節点を 12 とすると
終端でない場合 (c，b の場合)，expGoto(ex0，c) が無ければ新
F ailure(12) = 10，expBase(10) = ex3 となる．そこから節
規節点 ex1 と expGoto(ex0，c) = ex1 を作る．新しく節点作っ
点 12 の文字列 (cd) と節点 10 の文字列 (d) の差 (c) を ex3 から
た場合はその節点 (ex1) へ，そうでない場合は expGoto(ex0，c)
遷移させていく．今回は’c’ のみなので expGoto(ex3，c) = ex4
に遷移して，次に expGoto(ex1，b) が無ければ新規節点 ex2 と
なので ex4 への遷移で終了となる．ここで，ex4 および ex4 以
expGoto(ex1，b) = ex2 を同じように作る．終端文字 (a) の場
下の節点集合のアウトプット集合 (8) を求め，それらの値の節
合，現在の ex 節点 (ex2) に現在の節点 (5) を Output として追
点が節点 12 への Failure 遷移となる．この時に，節点集合を高
加し，expOutput(ex2) = 5 とする．また，Expect tree では親
速で求めるために expChild 関数および，expSibiling 関数を使
節点が子節点集合のうち一つの節点番号を持つ expChild 関数
う．また，expchild[ex3] = ex4 の場合，別な ex3 の子節点へ
と，自分と同じ親節点を持つ節点集合 (兄弟節点集合) のうち一
ポインタを変更し，兄弟節点集合を求める expsibling から ex4
つのポインタである expSibling 関数を tree 構築時に作ってい
を除くことで，Expect tree 自体の更新も完了する．追加節点
る．expSibling は双方向リストで実装しているため追加，削除
s に Failure 遷移するものを探す Expect Tree の更新のアルゴ
がすぐに行える．
リズムはアルゴリズム 3 になる．
5. 評
価
本手法の評価では更新ができない AC マシンと逆 Failure 関
数を使用した既存手法と expect tree を使用した提案手法にお
いて，構築時間，更新時間，メモリ使用量の比較を行った．更
新時間はキーワード集合 K = y1 , y2 , ..., yn より構成された AC
マシンに，1000 から 100000 件のデータを追加を追加するのに
必要な時間を測定した．日本語データ，英語データは wikipedia
の見出し語を使用していて，日本語データで構成されたマシン
には日本語データの追加を，英語データで構成されたマシンに
は英語データを追加している．構築時間は AC マシンを最初か
図 3 Expect Tree(構築途中)
ら構築するのにかかった時間を測定している．実験に使用した
マシンは CPU:Intel(R) Xeon(R) CPU X5355 2.66GHz ×２，
4. 2 Expect tree を使用した更新
Expect tree ではある exp 節点以下のアウトプット集合を
得ることで逆 Failure 集合や，ある文字列に Failure 遷移する
節点の集合を求めることができる．ある exp 節点以下のアウ
OS:openSuse 11，メモリ:32GB であり，実装は Java で行って
いる．
Algorithm 1 Create Expect tree
1: for (i = 0, i <
= N − 1, i + +) do
2:
x ⇐ F ailure(si )
3:
if expBase(x) not exist then
4:
create expBase(x)
5:
end if
6:
expnode ⇐ expbase(x)
7:
str[] ⇐ x と si の非共通文字列
8:
L ⇐ str の文字列長
for (j = L − 1, j >
= 1, j − −) do
9:
10:
if expgoto(expnode, str[j]) = f alse then
Algorithm 3 Update with Expect tree
1: x ⇐ F ailure(s)
2: if expBase(x) not exist then
11:
create new expnode
3:
12:
set expchild(expnode)
4: end if
13:
set expsibling(newexpnode)
expnode ⇐ newexpnode
5: expnode ⇐ expbase(x)
14:
15:
16:
else
expnode ⇐expgoto(expnode,str[j])
17:
end if
18:
if j = 1 then
19:
20:
21:
create expOutput
end if
end for
22: end for
6: str[] ⇐ x と si の非共通文字列
7: L ⇐ str の文字列長
8: state ⇐ true
9: for (j = L − 1, j >
= 0, j − −) do
10:
11:
if expgoto(expnode, str[j]) = f alse then
create new expnode
12:
set expchild(expnode)
13:
set expsibling(newexpnode)
14:
expnode ⇐ newexpnode
15:
16:
17:
state ⇐ f alse
else
expnode ⇐ expgoto(expnode, str[j])
18:
end if
19:
if j = 1 then
20:
create expOutput
21:
end if
22:
if j = 0 then
23:
Algorithm 2 getFailure
create expBase(x)
24:
前 exp 節点から現在の exp 節点への expchild の削除
expsibling の削除
end if
1: s put queue
25:
2: while queue =
| empty do
26: end for
3:
x get queue
27: if state = f alse then
4:
if expchild(x) exist then
28:
Fs ⇐ getF ailure(expnode)
29:
Fs の F ailure 遷移先を s に変更
5:
expchild(x) put queue
6:
end if
7:
if expsibling(x) exist then
8:
9:
10:
11:
12:
expsibling(x) put queue
end if
if expOutput(x) exist then
expOutput(x) put Fs
end if
13: end while
14: return Fs
30: end if
5. 1 構築時間による比較
5. 2 追加更新速度による比較
表 1 が構築にかかった時間, 図 5, 図 6 はそのグラフである.
表 2，3 は追加更新時間をまとめたものである．構築済み件
表 1 を見ると更新が無い AC マシンと逆 Failure 関数ではほと
数が 50 万件 (日本語) の時のグラフを図 7 200 万件 (英語) の時
んど構築時間に差が無いが，本研究の手法は日本語の場合も英
の追加更新のグラフを図 8 としている．表を見ると，逆 Failure
語の場合も２∼３倍程度構築時間がかかる事がわかる．これは
の手法は構築済み件数が少ない時と構築済み件数が多い時の
各節点毎に Expect tree の生成に時間がかかっていることが原
追加更新の時間の差が大きく，数十倍の違いがでる．しかし，
因である．しかし，AC マシンを起動させるのは初めの１回の
Expect tree の方は 2 倍程度しか追加更新時間が変わっていな
みであるし，起動に差し支える程でもないため，この差は問題
いことがわかる．これは逆 Failure 関数は，追加節点の親節点
がないと考えられる．
の逆 Failure 集合の数に比例して追加更新時間がかかるのに対
し，Expect tree は追加節点に Failure 遷移する節点数に比例
表 1 横軸:構築件数 (万件) における構築時間 (ms)
10
20
更新なし (J)
2311
逆 Failure(J)
50
して追加更新時間がかかる事が差になっていると考えられる．
100
200
4149
9610 18876
-
2437
4177
9929 19713
-
本手法が約 100 倍速い事がわかる．また，英語 200 万件構築
Expect tree(J)
6175
9356 19366 34469
-
済みに対しての追加更新速度は本手法が約 10 倍速い事がわか
更新なし (E)
2131
3995
9421 17390 35282
る．日本語の方が速度の違いが出た理由としては，日本語は文
逆 Failure(E)
2349
4602 10227 21025 41421
字の種類が多いので，新規追加節点の親節点がルート節点であ
Expect tree(E) 7785 12598 25645 49300 96902
るケースが増えるので，逆 Failure 集合の数が増えて既存手法
図を見ると日本語 50 万件構築済みに対しての追加更新速度は
の時間が長くかかった事が考えられる．
表2
構築済み件数 (万件) に追加件数 (件) での追加更新時間 (ms) の
比較 (日本語)
PP
PP 構築済件数
PP
追加件数
PP
逆 Failure
図5
構築件数 (万件) における構築時間:日本語
Expect Tree
0
10
20
50 100 200
1000
488
1313
2557
7274
-
-
2000
702
8551
19216
50285
-
-
5000
1452
30199
67728 112982
-
-
10000
2178
41859
93076 154109
-
-
20000
4741
55561 122230 191482
-
-
50000
8828
76970 162955 294367
-
-
100000 32631 131448 251136 466483
-
-
1000
307
216
223
215
-
-
2000
433
378
355
588
-
-
5000
651
598
801
894
-
-
10000
955
776
1003
1150
-
-
20000
1314
1182
1310
1727
-
-
50000
2102
2257
2372
2977
-
-
100000
3687
3923
4453
5055
-
-
図 6 構築件数 (万件) における構築時間:英語
図7
追加更新時間の比較:日本語 50 万単語構築済み
表3
構築件数 (万件) に追加件数 (件) での追加更新時間 (ms) の比較
表 4 構築件数 (万件) におけるメモリサイズ (MB)
(英語)
PP
PP 構築済件数
PP
追加件数
PP
逆 Failure
1000
0
355
10
196
20
181
50
171
100
209
200
201
10
20
50
100
200
更新なし (J)
317
530
逆 Failure(J)
331
935 1624
-
586 1042 1779
Expect tree(J)
827 1288 2382 4961
-
555
603 1142 1780
2945
558
619 1216 1958
3463
-
2000
462
1692
3825
7746 14068
25651
更新なし (E)
5000
697
2246
4637
9342 16926
30625
逆 Failure(E)
10000 1002
2805
5599 11339 20811
37140
Expect tree(E) 2069 1973 4609 9090 16637
20000 1600
5873 11434 24349 43042
65547
50000 2689
7730 14091 29107 51155
79413
100000 6293 13978 22889 44211 76105 122308
ExpectTree
1000
371
284
304
322
354
317
2000
489
661
644
993
1378
1247
5000
775
890
885
1294
1783
1731
10000 1102
1336
1331
1833
2106
2680
20000 1643
2153
2265
3084
3911
4555
50000 3139
3953
4156
5228
6364
7173
100000 6033
7395
7074
9291 11225
12423
図 9 メモリ使用量の比較:日本語
図 8 追加更新時間の比較:英語 200 万単語構築済み
5. 3 メモリサイズによる比較
図 10
表 4 は構築件数におけるメモリサイズを比較した表であり，
メモリ使用量の比較:英語
日本語を構築した時のグラフは図 9, 英語を構築した時のグラ
フを図 10 のようになっている．メモリサイズは日本語の場合
における実験により，動的追加更新速度が約 10∼100 倍高速に
は既存手法と比較し約３倍，英語の場合は既存手法と比較し約
なった．
５倍となっている．なぜ，日本語と英語でこれほど差がでたか
と言うと英語の辞書語の方が平均文字列長が長かったので，そ
の分 Expect tree を作る節点数が増加したことが考えられる．
長さ n の節点でルート節点に Failure 遷移するものが Expect
tree を作った場合，n − 1 個の expGoto 関数を作る必要が出て
くるために，キーワード集合の文字列が長いほど本手法ではメ
モリサイズを使用することが予測される．一方，必要とする領
域は３∼５倍となるので，この点についての改良を今後に取り
組む予定である．
6. 結
論
Aho-Corasick 法の動的追加更新において，本研究では Expect tree と言う木構造のインデックスを AC マシンのオート
マトンとは別に持たせることで，追加節点に Failure 遷移する
節点を高速で求められる手法を提案した．日本語，英語の単語
文
献
[1] Alfred V. Aho and Margaret J. Corasick. Efficient string
matching: an aid to bibliographic search. Commun. ACM,
Vol. 18, pp. 333–340, 1975.
[2] 森 良介. 藪 達也. 朱 成敏. 遠山元道. Keio wix システム (2)
サーバサイド実装. DEIM2011, 2011.
[3] 青江 順一. 津田 和彦. ストリングパターンマッチングマシンの
動的構成法. 電子情報通信学会論文誌, Vol. J77, pp. 282–289,
1994.