1

北海道大学
Hokkaido University

情報知識ネットワーク特論「情報検索とパターン照合」
情報科学研究科 コンピュータサイエンス専攻
情報知識ネットワーク研究室

喜田拓也

2005/10/18

情報知識ネットワーク特論 講義資料

第３回
Suffix型アルゴリズム
Boyer-Moore アルゴリズム
Galil アルゴリズム
Horspool アルゴリズム
Sunday アルゴリズム

北海道大学 Hokkaido University3Naïve アルゴリズム
123

4

5

67891011 12 13 14 15 16 17

テキストT: a b a b b a b a b c b a a b a b c
パターンP: a b a b c
パターン出現！
パターン出現！
at positionat position
6 of T 13 of T

もっと大雑把にいえば、O(nm) 時間

一文字づつずらしてマッチングしていくNaïve-String-Matching (T, P)
テキスト上のポインタ
1 n ← length[T].
（比較する文字の現在
2 m ← length[P].
位置）が前後する！
3 for s ← 0 to n – m4
do if P[1..m] = T[s+1…s+m]
5
then report an occurrence at s.

最悪の場合 O((n-m+1)m) 時間かかる。
※演習：T=a8, P=a4b の場合を文字比較の回数は何回か？
2005/10/18

P=aaaab の意味

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

4

Knuth-Morris-Pratt アルゴリズム
D. E. Knuth, J. H. Morris, Jr, and V. R. Pratt. Fast pattern matching in strings.
SIAM Journal on Computing, 6(1):323-350, 1977.
123

4567891011 12 13 14 15 16 17

テキストT: a b a b b a b a b c b a a b a b c
パターンP: a b a b cnext[5] = 3
next[3] = 0

ababc
ababc

パターン出現！
at position 6 of T

next関数によって次にPの何文字目とテキストをKMP-String-Matching (T, P)比較するかがわかる。（シフト量は q－next[q]）1 n ← length[T].
2 m ← length[P].
値が0のときは、テキストの次の文字と比較する。
3 q ← 1.
テキストの各文字との比較はO(1)回ずつである。
4 next ← ComputeNext(P).
5 for i ← 1 to n do
6while q>0 かつ P[q]≠T[i] do q ← next[q];7if q=m then report an occurrence at i-m;
8q ← q+1.

最悪の場合でも O(n+m) 時間 （nextはあらかじめ配列として計算）
2005/10/18

情報知識ネットワーク特論 講義資料

5

北海道大学 Hokkaido University

効率的照合アルゴリズムの一般形
MatchingAlgorithm (P, T)
1 m ← length[P].
2 n ← length[T].
3 i ← 1.
4 while i ≦ n – m +1 do
5i が出現位置であるか否かを決定する;
6if i が出現位置 then report an occurrence at i;
7
パタンを右へシフトする量Δを求める;
8i ← i + Δ.
KMP法、BM法をはじめとする多くの効率的パタン照合アルゴリズムがこの枠組みに入る※※竹田正幸「全文テキスト処理のための高速パターン照合アルゴリズム」、情報学シンポジウム、1991年1月．

アルゴリズムの高速化のために大事なこと：• 5行目をいかに最小の手間で決定できるか• 7行目においてシフト量をどれだけ大きくできるか
2005/10/18

情報知識ネットワーク特論 講義資料

6Boyer-Moore アルゴリズム

北海道大学 Hokkaido UniversityR. S. Boyer and J. S. Moore. A fast string searching algorithm. Communications of the ACM, 20(10):762-772, 1977.

特徴： パタンの右から左へ文字を比較していく 二つの関数（delta1とdelta2）の値を比較し、より大きいほうを使ってパタンをシフトする
 最悪 O(mn) 時間だが、平均的には O(n/m) 時間となる （sub linear!!）delta1(char) := パタン内のcharの最右の出現位置に合わせるようにシフトした際のポインタ（文字比較位置）のとび幅 （出現しない場合はパタン長）
delta1(c) = 5
テキストT:
パタンP:(bad-character heuristic)a a b c d a a c b c a b c c a ・・・
abcbabababcbabab‘c’の位置を合わせるようにシフトする Δ=delta1(char) – j + 1 = 5 – 0 = 5

2005/10/18

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

7

delta2(j)delta2(j) := パタンPの長さ j-1 のsuffixのP中の他の出現位置（あるいは最長一致するPrefix）に合わせた際のポインタのとび幅 （出現しない場合はパタン長）(good-suffix heuristic)delta2(3) = 8
テキストT:
パタンP:

a a b c d a a b b c a b c c a ・・・
abcbabababcbabab※delta2(3) の候補としては1と5の二つある。
しかし5の出現位置の左隣は’b’で既に一致しないことが分かっているので、この場合は1となる。

‘ab’の位置を合わせるようにシフトする Δ=delta2(3) – 3 + 1 = 8 – 2 = 6

delta2(5) = 10
テキストT:
パタンP:

a a b c a b a b b c a b c c a ・・・
abcbabababcbabab‘ab’の位置を合わせるようにシフトする Δ=delta2(5) – 5 + 1 = 10 – 4 = 6

2005/10/18

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

8BM法の問題点
delta関数を計算するのが難しい– 単純なやり方だと O(m2) 時間かかる– O(m) 時間の手法はひと手間かかる → KMPの裏返しdelta1 と delta2 の値をいちいち比較するので、手間がかかりすぎる– delta1 だけを用いる方法が一般的（ただしそのままでは、パタンがうまくシフトできないことがあるので、工夫が必要）

最悪の場合には、O(mn) 時間かかってしまう– T = an, P = bam の場合を考えよ

アルファベットのサイズが小さいときには効率が悪い– テキストもパタンも∑={0,1}の場合は、ほとんどシフトできない！
つまり、バイナリテキスト

2005/10/18

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

9Galil アルゴリズム

Z. Galil. On improving the worst case running time of the Boyer-Moore string searching algorithm.
Communications of the ACM, 22(9):505-508, 1979.

元のBM法では、一致した文字列の情報を「忘れてしまう」ので、O(mn)時間かかる
 Prefixが何文字一致しているかを記憶しておけばよい
 理論的には、テキスト走査をO(n)時間で行える
 実際には処理が煩雑になり、遅くなる

delta2(5) = 10
テキストT:
パタンP:

a a b c a b a b c b a b a b a ・・・
abcbabababcbabab

これ以降は「すでに比較ずみ」であることを記憶しておく
2005/10/18

テキストの各文字はせいぜい2回しか比較されなくなる！

比較する残りの部分はここだけ
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

10

Horspool アルゴリズム

R. N. Horspool. Practical fast searching in strings. Software Practice and Experience, 10(6):501-506, 1980.



∑が十分に大きい場合は、delta1関数（bad-character heuristic）が大抵の場合一番よいシフト量を与える→ 少しの変更を加えることで、よりとび幅を増やすことができる！
delta1(c) = 5
テキストT:
パタンP:

a a b c d c a d b c a b c c a b a c a・・・
abcbabadabcbabaddelta1’(d) = 10

テキストT:
パタンP:

a a b c d c a d b c a b c c a b a c a・・・
abcbabadabcbabad

2005/10/18

delta1’(b) = 3

常にパタンの最後の位置に対応するテキストの文字でとび幅を決定する
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

11

擬似コードHorspool (P, T)
1 m ← length[P].
2 n ← length[T].
3 Preprocessing:
4For each c∈∑ do delta1’[c] ← m.
5For j←1 to m – 1 do delta1’[ P[j] ] ← m – j .
6 Searching:7i ← 0.
8while i ≦ n – m do
9j ← m;10
while j > 0 かつ T[i+j] = P[j] do j ← j – 1;
11
if j = 0 then report an occurrence at i+1;
12i ← i + delta1’[ T[i+m] ].

2005/10/18

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

12

Sunday アルゴリズム

D. M. Sunday. A very fast substring search algorithm. Communications of the ACM, 33(8):132-142, 1990.

基本はBM型アルゴリズムと同じ
 異なる点– パタンが一致するか否かを、パタン中の任意の文字順で比較する


例えば、統計的に出現頻度の低い文字から順次比較を行う– delta1を引く際、パタンの最後の位置の右隣に対応するテキスト上の文字を使う （BMにおけるdelta2も計算し、長いほうを選択する）



Horspoolよりもとび幅は長くなる傾向がある– ただし、メモリ消費量はHorspoolより大きい– また、とび幅を計算する手間がHorspoolよりかかる
delta1’(d) = 9
テキストT:
パタンP:

delta1’(c) = 6a a b c d c a b d c a b c c a b a c a・・・
abcbabababcbabab2005/10/18

常にパタンの最後の位置の右隣に対応するテキストの文字でdelta1を計算する
情報知識ネットワーク特論 講義資料

Factor型アルゴリズム
BDM アルゴリズム
BOM アルゴリズム
BNDM アルゴリズム

北海道大学 Hokkaido University

14

Backward Dawg Matching (BDM)アルゴリズム
M. Crochemore, A. Czumanj, L. Gasieniec, S. Jarominek, T. Lecroq, W. Plandowski, and W. Rytter.
Speeding up two string matching algorithms. Algorithmica, 12(4/5):247-267, 1994.

基本はBM型アルゴリズムと同じ
 異なる点– パタンのSuffixと一致しているかではなく、Factorと一致しているかどうかでパタンの出現を判定する– Factorかどうかの判定はSuffix Automatonを使う(suffix treeでも可)Suffix automaton (SA) の特徴– 文字列 u がパタンPのFactorであるかどうかがO(|u|)時間で分かる– 文字列 u がパタンPのSuffixであるかどうかも判定できる– P=p0p2…pm に対して、O(m)時間のオンラインアルゴリズムがある
Factor search

テキストT:
パタンP:

Prefixかどうかは、SAの2番目の特徴からわかる

σ ua a b c d c a b d c a b c c a b a c a・・・
abcbabababcbabab

cc はFactorではないし、また、cはPrefixでもないので次の文字までパタンをずらせる

abcbabab2005/10/18

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

15

Suffix Automaton

A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. T. Chen and J. Seiferas. The smallest automation
recognizing the subwords of a text. Theoretical Computer Science (40):31-55, 1985.

パタンP = announce の反転PRのfactorを受理する決定性オートマトン

Suffix automatonaoc0ec1n2uncnuuoonnnna

2005/10/18a4on

5nunanacn

6anu

Suffix treeuooonnnnannaaaa78a9e

Suffix trie

u3nnouncaecnu noannaauonnanuonnaonna

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

16On-line 構築アルゴリズム
とっても複雑なので、SuffixAutomaton(P=p1p2…pm)
構築するのは
1 Create the one-node graph G=DAWG(e).
結構たいへん！
2 root ← sink ← the node of G. suf[root] ←θ.
3 for i ← 1 to m do
4
create a new node newsink;5
make a solid edge (sink, newsink) labeled by a;
6w ← suf[sink];
7
while w≠θ かつ son(w,a)=θ do
8make a non-solid a-edge (w, newsink);
9w ← suf[w];
10v ← son(w,a);11
If w=θthen suf[newsink] ← root
12
else if (w,v) is a solid edge then suf[newsink] ← v
13else14
create a node newnode;15
newnode has the same outgoing edges as v except that they are all non-solid;
16change (w,v) into a solid edge (w, newnode);17
suf[newsink] ← newnode;18
suf[newnode] ← suf[v]; suf[v] ← newnode;19
w ← suf[w];20
while w≠θかつ (w,v) is a non-solid a-edge do
21
redirect this edge to newnode; w ← suf[w].
22sink ← newsink.
2005/10/18

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

17

BNDM アルゴリズム

G. Navarro and M. Raffinot. Fast and flexible string matching by combining bit-parallelism and suffix automata.
ACM Journal of Experimental Algorithmics (JEA), 5(4), 2000.

基本はBDMと同じ
 異なる点– パタンのfactorかどうかを調べるため、非決定性（nondeterministic）のSuffix automataを用いる– そのNFAの状態遷移をBit-parallel手法でシミュレートする

パタンP = announce の反転PRのsuffixを受理する非決定性オートマトン
Iεε0eε1cε2nε3uε4o

ε5nε6n2005/10/18

7a8

このNFAをシミュレートする

初期状態：R0 = 1m
状態遷移：R = (R << 1) & M[ T[i] ]εShift-Andと同じ
Mask table

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University18

擬似コード
BNDM (P, T)
1 m ← length[P].
2 n ← length[T].
3 Preprocessing:
4for c ∈ ∑ do M[c] ← 0m.
5for j ← 1 to m do M[ P[j] ] ← M[ P[j] ] | 0m–j10j–1.
6 Searching:7s ← 0.
8while s ≦ n – m do
9j ← m, last ← m, R ← 1m;
10
while R ≠ 0m do
11R ← (R << 1) & M[ T[s+j] ];12j ← j – 1;
13
If R & 10m-1 ≠ 0m then14
If j > 0 then last ← j;15
else report an occurrence at s+1;
16
R ← R << 1;
17s ← s + last.
2005/10/18

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

19

Backward
Oracle Matching (BOM)アルゴリズム
C. Allauzen, M. Crochemore, and M. Raffinot. Efficient experimental string matching by weak factor recognition.
In Proceedings of the 12th Annual Symposium on Combinatorial Pattern Matching, LNCS2089:51-72, 2001.

BDMとアイデアは同じ
 異なる点– 複雑なSuffix automatonではなく、Factor oracleを使う– BDMにおいて必要なことは、文字列uがFactorであることではなく、σuがFactorではないこと。

Factor oracleの性質– パタンPのFactor以外の文字列も受理してしまう可能性がある


例：下の図で、cnnはPRのFactorではない– O(m)時間で構築できるうえに、実装が容易で少メモリ

状態数m+1個、遷移関数の実現サイズ2m-1

P=announceの場合の、PRに対するFactor oracle

anc0

2005/10/18

e1c2anu

3u

4no

5n6n7a8o
情報知識ネットワーク特論 講義資料

20

北海道大学 Hokkaido University

Factor oracleの構築アルゴリズム
Oracle-on-line (P=p1p2…pm)
1 Create Oracle(ε) with2
One single initial state 0, S(0) ←θ.
3 for i∈1…m do
4Oracle(P=p1p2…pj)
5← Oracle_add_letter (Oracle(P=p1p2…pj-1), pj).
Oracle_add_letter (Oracle(P=p1p2…pm),σ)1 Create a new state m+1.
2 δ(m,σ) ← m+1.
3 k ← S(m)4 while k≠θかつδ(k,σ)=θ doδ(k,σ) ← m+1;
56k ← S(k).
7 If k =θthen s ← 0;
8 else s ← δ(k,σ).
9 S(m+1) ← s.
10 return Oracle(P=p1p2…pmσ).
2005/10/18

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

21

ちょっと、ひといき・・・

ここまでのまとめ– Suffix型アルゴリズム

 パターンを右から左へ照合する！
 テキストの文字を飛び飛びで照合できる！

– Factor型アルゴリズム

 パターンのすべてのFactorと比較しつつ、テキストの文字を飛び飛びで照合できる！

～トリビア～
二つの整数xとyの内容を余計な変数を用いずに交換できるか？
(x,y) = (y,x)
Perlだとリストを使える！
いわとびペンギン （旭山動物園にて ’05.3.13）
2005/10/18

情報知識ネットワーク特論 講義資料

Suffix・Factor型の複数パターンへの拡張
Set Horspool アルゴリズム
Wu-Manberアルゴリズム

北海道大学 Hokkaido University

23Suffix・Factor型 複数パターン照合
Commentz-Walterアルゴリズム
B. Commentz-Walter. A string matching algorithm fast on the average. In Proceedings of the 6th International
Colloquium on Automata, Languages and Programming, LNCS71:118-132, 1979.

• BMアルゴリズムの直接的な拡張

Set Horspoolアルゴリズム• Commentz-WalterのアルゴリズムをHorspoolのアイデアに基づいて簡略化したもの

Uratani-Takedaアルゴリズム• ACアルゴリズムのアイデアをBM型に転用したもの。CWより高速

Set Backward Oracle Matching (SBOM)アルゴリズム
C. Allauzen and M. Raffinot. Factor oracle of a set of words.
Techinical report 99-11, Institut Gaspard-Monge, Universite de Marne-la-Vallee, 1999.

• Factor oracleを複数文字列に拡張したものを利用。

Wu-Manberアルゴリズム
S. Wu and U. Manber. A fast algorithm for multi-pattern searching.
Report TR-94-17, Department of Computer Science, University of Arizona, Tucson, AZ, 1994.

• 実用的に高速なアルゴリズム。Agrepにも用いられている
2005/10/18

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

24

Set Horspool アルゴリズム
パタン集合の各要素を反転（reverse）した文字列のtrieを作る
 あとはHorspoolと同じ
– Suffix search をしながらtrieをたぐる– どのパタンのSuffixでもないことが判ったら、delta1’でパタンをシフトする
パタンのリバースtrieα
テキストT:※Cf. Uratani-Takedaアルゴリズムでは、trieのかわりにACマシンを使い、failure関数によってとび幅を決定する

σsuffix search

テキストT:

β
どのパタンの中にもβが出現しない部分

2005/10/18

delta1’

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

25

パフォーマンスが悪くなる理由
delta (≦ ℓmin)
テキストT:
可能なとび幅の最大値はℓmin

パタンP:に制限される
ℓmax

ℓmin

パターンの個数が多くなると、各文字の出現頻度が高くなりbad-character heuristicがうまく働かない！
2005/10/18

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

26

Wu-Manberアルゴリズム

S. Wu and U. Manber. A fast algorithm for multi-pattern searching.
Report TR-94-17, Department of Computer Science, University of Arizona, Tucson, AZ, 1994.



テキストの照合位置からB文字分（T[i-B+1…i]）を用いて、パタンが出現する可能性を調べる– SHIFT[ T[i-B+1…i] ] : T[i-B+1…i]が、あるパタンの接尾辞であるとき0。そうでなければ、可能な最大シフト長を返す。
– HASH[ T[i-B+1…i] ] : SHIFTが0 （すなわちT[i-B+1…i]があるパタンの接尾辞）だった場合、出現の可能性があるパタンのリストを返す。

パタンP:

announ c eannua lannua l l y

テキストT:

CPM

パタン出現の可能性あり！

SFHIT[al]=0
HASH[al]=2, → シフト1

annua lc on f e r en c e

SFHIT[an]=4

SHIFT[Bl] =HASH[Bl] =2005/10/18

announ c e

SFHIT[l ]=5

文字列

llno ouanun nc

シフト量1341ua al ly0

文字列

ce lyua al＊パタン番号3, 12

φ0nn nu
2ce ＊05

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University27

擬似コード※agrep ver4.02 の実装(mgrep.c)では、SFHIT・HASH・Bはそれぞれ、4096、8192、3となっている（ようだ）

Construct_SHIFT (P={p1,p2,…,pr})1 initialize SHIFT table by ℓmin–B+1.
2 For each Bl=pi[j–B+1…j] do3
If SHIFT[h1(Bl)] > mi – j do SHIFT[h1(Bl)] = mi – j.

Wu-Manber (P={p1,p2,…,pr}, T=T[1…n])
1 Preprocessing:
2Computation of B.
3
Construction of the hash tables SHIFT and HASH.
4 Searching:
5pos ← ℓmin.
6
while pos≦n do
7i ← h1( T[pos–B+1…pos] );8
If SHIFT[i] = 0 then9list ← HASH[ h2( T[pos–B+1…pos] ) ];10
Verify all the patterns in list one by one against the text;
11
pos ← pos + 1;
12else pos ← pos + SHIFT[i].
2005/10/18

情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

28

第３回 まとめSuffix型アルゴリズム– パターンを右から左へ照合する– 最悪 O(mn) 時間だが、平均的には O(n/m) 時間– Boyer-Moore、Galil、Horspool、Sunday らのアルゴリズム

Factor型アルゴリズム– パターンのFactorかどうかを判定して、テキストを飛び飛びに照合する– BDM、BNDM、BOMアルゴリズム

Suffix型・Factor型アルゴリズムの複数パターンへの拡張– パターンの個数が多くなると、各文字の出現頻度が高くなりbad-character heuristicがうまく働かない– Set Horspool、Wu-Manberアルゴリズム

次回のテーマ– 近似文字列照合アルゴリズム： 誤りを許したパターン照合

2005/10/18

情報知識ネットワーク特論 講義資料