1

北海道大学
Hokkaido University

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

喜田拓也

2005/10/11

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

第2回
Prefix型アルゴリズム※Naïve アルゴリズム
KMP アルゴリズム
Aho-Corasick アルゴリズム
Shift-And/Or アルゴリズム※ 参考文献：Felxible Pattern Matching in Strings, Gonzalo Navarro and Mathieu Raffinot

北海道大学 Hokkaido University

3

パターン照合問題（Pattern Matching Problem）とは？


テキストT中に含まれるパターンPの出現を求める問題
有名なアルゴリズム：– KMP法 (Knuth&Morris&Pratt[1974])– BM法 (Boyer&Moore[1977])– Karp-Rabin法 (Karp&Rabin[1987])

O(n+m) 時間

パターン P: compress

テキスト T:

2005/10/11

We introduce a general framework which is suitable to capture anessence of compressed pattern matching according to various
dictionary based compressions. The goal is to find all occurrences ofa pattern in a text without decompression, which is one of the mostactive topics in string matching. Our framework includes suchcompression methods as Lempel-Ziv family, (LZ77, LZSS, LZ78,LZW), byte-pair encoding, and the static dictionary based method.
Technically, our pattern matching algorithm extremely extends thatfor LZW compressed text presented byAmir, Benson and Farach [Amir94].
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University4Existence problem と All-occurrences problem
Existence problem

テキスト T: テクマクマヤコンテクマクマヤコン
パターン P: クマクマ

Yes!

All-occurrences problem

テキスト T: テクマクマヤコンテクマクマヤコン
パターン P: クマクマ

210

全文検索で文書を単位として検索する場合は、Existence problemで充分
しかし、一般的にはAll-Occurrences problemを指すことが多い
2005/10/11

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

北海道大学 Hokkaido University

5Naïve アルゴリズム
1

2

3

4

5

6

7

8910

11 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/11

P=aaaab の意味

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

北海道大学 Hokkaido University

6

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.
1234567891011 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] = 3next[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/11

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

北海道大学 Hokkaido University

7next関数の計算
next[q] = k の条件– P[1:k-1] が P[1:q-1] の接頭辞かつP[k]≠P[q]を満たす最長のもの
q+1
パタンP:

a b a b ca b a b ca b a b ckパターンをずらしながら比較し、next[q]を計算する
q12

3

4

5P[q]

ababc

next(q)01013

ComputeNext (P)1 m ← length[P]. next[1] ← 0. k ← 0.
2 for q ← 1 to m do3while k>0 かつ P[q]≠P[k] do k ← next[k];4k ← k+1; q ← q+1;
5
if P[q]=P[k] then6next[q] ← next[k]7else
8next[q] ← k;
2005/10/11

61O(m) 時間・領域

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

北海道大学 Hokkaido University8

決定性オートマトンによる照合パターン P = ababb を検知する（ε遷移付き）決定性有限オートマトン（KMPオートマトン）

任意の文字

a0b1-1a

テキスト：
状態：

0b1

2

a2

b3

b457: goto関数: failure関数

Next関数に対応

abb3

a42b34a510

前処理は O(|∑|m) 時間・領域。照合の時間はKMPと同じ O(n) 時間
2005/10/11

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

北海道大学 Hokkaido University

9Aho-Corasick(AC) アルゴリズム
A. V. Aho and M. J. Corasick. Efficient string matching: an aid to bibliographic search.
Communications of the ACM, 18(6):333-340, 1975.

パターン集合 ∏={AC,BA,BB,BAA,BACD} を検知する（ε遷移付き）順序機械
A1B

24CA

（AC照合機械）
35

A

7BA￢{A,B}

パターンが複数個でも、O(n) 時間で照合可能！

CB

6: goto関数: failure関数

7AC

BAA
8DAC

※状態1へのfailureは煩雑なので省略

9BACD

BB

KMPオートマトンは、パターンが一つの場合のAC照合機械に等しい※ 初期状態のとりかたが違うように見えるが、原理的には同じように構成できる
2005/10/11

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

北海道大学 Hokkaido University10構成アルゴリズム
A. V. Aho and M. J. Corasick. Efficient string matching: an aid to bibliographic search.
Communications of the ACM, 18(6):333-340, 1975.

パターン集合 ∏={AC,BA,BB,BAA,BACD} を検知する（ε遷移付き）順序機械
A1B

24CA

（AC照合機械）
35A

7BA￢{A,B}

CB

2005/10/11

6: goto関数: failure関数

7AC

BAA
8DAC

※状態1へのfailureは煩雑なので省略

9BACD

BB

Phase 1. パタンを処理しながらtrie(gotoグラフ)を作る
Phase 2. 幅優先探索しfailure関数を求めつつ、出力関数を補完する※ 詳細は配布資料を参照
Phase 3. 最適化する

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

11

北海道大学 Hokkaido University

AC照合機械構成の擬似コード
Build-ACmachine (P={p1,p2,…,pr)Phase 1
1 AC_trie ← Trie(P).
2 // 配列g,f,o をそれぞれgoto関数、failure関数、output関数とする
3 // AC_trie上の出力があるノードを terminal とよぶ
以下 Phase 2 の処理
4 initial_state ← root of AC_trie.
5 f[initial_state] ← nil.
6 for current in transversal order do7parent ← parent of current in AC_trie.
8σ← label of the transition from parent to current.
9down ← f[parent].
10
while down ≠ nil and g[down,σ] = nil do down ← f[down].
11
if down ≠ nil then12f[current] ← g[down,σ].
13
if f[current] is terminal then
14Mark current as terminal.
15
o[current] ← o[current] ∪ o[ f[current] ].
16
end_if17else18
f[current] ← initial_state.
19
end_if20 end_for※演習：P={cacao, ocaca} に対するAC照合機械を作図せよ
2005/10/11

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

北海道大学 Hokkaido University

12

SIGMA方式のデータベース
例）九州大学大学院 農学研究院 昆虫学教室の「昆虫学データベース(KONCHU)」（http://konchudb.agr.agr.kyushu-u.ac.jp/indexj.html）– データの各レコードは、タグ付けされたデータ項目の並び(FTAX)科名(亜科名等を含むレコードもある)(GTAX)
属名(亜属名を含むレコードもある)
このレコードが「デリミタ」で仕切られて(STAX)
種名または亜種名並べられ、一つのDBを構成する(JTAX)和名(DST) 分布(国内;国外) データ
検索は、検索語・タグ・デリミタをパターンタグとしたAC照合機械によって行われる– レコードの実例(FTAX)315180550000. Pieridae シロチョウ科(A)(GTAX)
Pieris (Artogeia)(STAX)
rapae crucivora Boisduval,1836(JTAX)モンシロチョウ(DST) HOKKAIDO, Rebun Is., Rishiri Is., HONSHU, Sado Is., Izu Isls., OgasawaraIsls., Awajishima Is., Oki Is., SHIKOKU, Shodoshima Is., KYUSHU, Tsushima Is., IkiIs., Goto Is., Tanegashima Is., Yakushima Is., Tokara Isls., AmamiOshima Is.,Tokunoshima Is., OkinawaHonto Is., Miyako Is., Ishigaki Is., Iriomote Is., YonaguniIs.; Taiwan, Far East Continent
2005/10/11
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University13

富士通 Interstage Shunsaku Data Manager

特徴：– XML形式のテキストをDBにみたてて、逐次検索（パターン照合）による高速なデータアクセスを実現する
インデックス不要
 データ様式の構成を柔軟に変更可能。
– コアの部分は、九州大学の有川節夫教授（現、同大学副学長）と研究グループが開発した検索システム「SIGMA」をベースにしている


導入事例：

理論的な中核は
Aho-Corasick アルゴリズム– 国立遺伝学研究所 生命情報・DDBJセンター


三大国際DNAデータバンクの一つ、DDBJ（日本DNAデータバンク）のARSA (All-round Retrieval of Sequence and Annotation) システム– 富士通社内

2005/10/11

生産管理システム、新電子電話帳システム
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

14

Shunsaku の優れた特徴（山手線方式）
http://software.fujitsu.com/jp/shunsaku/

データの集まりを一つのXML文書として表現
 AC照合機械をフルに活用して検索(1CPUで100MB/s)
 分散処理・フォールトトレラント機構 etc.
 複数のクエリをまとめて処理することで数万件の同時アクセス高速なレスポンスを確保（山手線方式）でも大丈夫！
クエリ

クエリ

2005/10/11

テキストDBを一括走査
クエリをまとめて一つのAC照合機械を構築

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

北海道大学 Hokkaido University

15

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

ここまでのまとめ– naïveな照合は大きなテキストやテキスト・ストリームには不向き– KMPアルゴリズムはO(m)時間・領域の前処理の後、O(n) 時間で照合– ACアルゴリズムはKMPオートマトンの考えを複数パターンに拡張したものである
 O(|∑|m)時間・領域の前処理の後、O(n) 時間で照合 （ここで、mはパターン長の総和）～トリビア～
二つの整数xとyの内容を余計な変数を用いずに交換できるか？
x←x⊕yy←y⊕xx←x⊕y（ここで、⊕は排他的論理和演算）
出典： 「ハッカーのたのしみ」

ペンギン隊の行進 （旭山動物園にて ’05.3.13）
2005/10/11

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

北海道大学 Hokkaido University

16

ビットパラレルにおけるビット列の基本操作

論理演算
ビット単位の 記号– 否定(not)– 積(and)– 和(or)– 排他的論理和(xor)– （0充填）左シフト– （0充填）右シフト– 代入– 比較演算子

集合
C～x~x
補集合
x&yx&y積集合x|yx|y和集合x⊕yx^y異なり集合（仮称）x << y x << y 全要素の加算
x >> y x >> y 全要素の減算x←y x=y
論理シフトとも言う
x>y, x<y x>y, x<y

算術演算ここでは、すべてunsigned注）１の補数と２の– 算術マイナス-x
補数では異なる– 加算x+y– 減算
x-y– 乗算・除算・剰余はほとんど使われない
参考：「ハッカーのたのしみ -本物のプログラマはいかにして問題を解くか」ヘンリー・S・ウォーレン, Jr.: “Hacker’s Delight”訳本
2005/10/11

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

北海道大学 Hokkaido University

17

Shift-And アルゴリズム
R. A. Baeza-Yates and G. H. Gonnet. A new approach to text searching. Proceedings of the 12th International
Conference on Research and Development in Information Retrieval, 168-175. ACM Press, 1989.
S. Wu and U. Manber. Fast text searching allowing errors. Communications of the ACM, 35(10):83-91, 1992.

レジスタ長のビット演算が並列に計算されることを利用 パタン長mがワード長wよりも短い場合には、O(n)時間で非常に高速に動作する
– 一般には O(n・⎡m/w⎤)時間、前処理はO(m+|∑|)

パタン P = ababb を受理する決定性有限オートマトン

任意の文字

0a1b2a3b4b5-1

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

パタン P = ababb を受理する非決定性有限オートマトン
任意の文字
2005/10/11

0a1b2a3b4b5

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

北海道大学 Hokkaido University

18

NFAの動き（状態遷移の様子）
パタン P = ababb を受理する非決定性有限オートマトン

任意の文字

状態番号

テキストT=

012345a01000001abb1100002aa1010003b110100b4a101010b5b110100b101010a100001110000

1: アクティブ
0: 非アクティブ
2005/10/11

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

北海道大学 Hokkaido University

19

ビットパラレル手法のアイデア
テキスト T: a

2005/10/11

Mask table Ma b a b b

パタン P:

b1
0000a12345000000 1
1 00 10 00 00
10001
1001 & 1
0000ba0 1
1 00 1
1 00 010100bb0
1010a0000110000ababbab

1010001011

Rii = (Ri-1i-1<<1 | 1) & M(T[i])O(1)時間で計算可能※つまり、マスクビット列Mと「＆」をとることで、正しい遷移だけを残している！
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

20

擬似コード
Shift-And (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:7
R ← 0m.
8for s ← 1 to n do
9R ← ((R << 1) | 0m-11) & M[ T[s] ];10If R & 10m-1 ≠ 0m then report an occurrence at s.
パターンが出現するかどうかの判定もビット演算で高速に処理できる！
パターン長がマシン語長（マシンのレジスタ長）より短い場合には、O(m+|∑|) 時間・領域の前処理の後、O(n) 時間で照合できる。
2005/10/11

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

北海道大学 Hokkaido University

21

文字クラスへの拡張
Mask table M

パターン P: a b [ a b ] b b
テキスト T: a1234500000b10000ab0 1
1 00 10 00 0bb0 01 00 11 00 1b00010a0000110000ab[ab]bbパターン P = ab[ab]bb を受理する非決定性有限オートマトン
任意の文字0a1

b2a3b※ 文字種[a..z,0..9]やその否定[^]、任意文字”!”が扱える
2005/10/11

b4b5ab10
1000
1
111

これだけ！
ここは同じ

Rii = (Ri-1i-1<<1 | 1) & M(T[i])
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

22

Shift-Or アルゴリズム
Shift-Andにおけるビット列を反転させたもの– 利点： Shift-Andよりも演算が少なくなる

テキスト T: a1
2
345

Mask table Ma b a b b

パタン P:

111
1
1b0
1
111a1 00 1
1 01 1
1 1ba1 00 1
1 00 1
1 1bb10101a1111001111ababbab0
101110100

Rii = (Ri-1i-1<<1) | M(T[i])※ チャレンジ！：この場合の擬似コードはどのようになるか？
2005/10/11

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

北海道大学 Hokkaido University23

第２回 まとめPrefix型アルゴリズム– Naïveアルゴリズム
O(mn)時間で照合、大きなテキストやテキスト・ストリームには不向き– KMPアルゴリズムO(m)時間・領域の前処理の後、O(n) 時間で照合– ACアルゴリズム
KMPオートマトンの考えを複数パターンに拡張したもの
 O(|∑|m)時間・領域の前処理の後、O(n) 時間で照合（ここで、mはパターン長の総和）
– Shift-And/Orアルゴリズム（ビットパラレル手法）
非決定性のKMPオートマトンを基にした考え方
 文字クラスへの拡張が容易 パターンが短いときにはO(m+|∑|)時間・領域の前処理の後、O(n)時間で照合

次回のテーマ– Suffix型アルゴリズム：より効率のよいパターン照合のための工夫

2005/10/11

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

北海道大学 Hokkaido University24

ビットパラレルとは何か？ 何ができるのか？
（レジスタ長の）ビット列に対する演算の並列性を利用して計算を高速化する手法
例：&0011 0101 1100 1001
1000 1000 1000 1000

= <3, 5, 12, 9>= <8, 8, 8, 8>0000 0000 1000 1000

= <0, 0, 8, 8>「1ビットどうしの論理積を１６回分」「ビット幅4の整数に対するマスク処理を4回分」

画像や音声などのマルチメディアデータを高速処理

特徴空間のベクトルをコンパクトに表現

定数時間で文字列処理（近似文字列照合、正規表現照合、他）の巧妙な実装による高速化※ このアイデアは、IntelのMMX・SSEテクノロジーやAthlonの3D Now!テクノロジーにも見られる
2005/10/11

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

北海道大学 Hokkaido University

25

ビットパラレル手法の真髄

整数の集まりをコンパクトに表現し、一括処理する！
– 順番に意味のある数字の列→ n-ビット幅の整数を一つにパック
一つのレジスタにパック可能な個数は、⎡w/n⎤ 個
例： <3, 5, 12, 9> = <0011 0101 1100 1001>→ MMX・SSEと同じアイデアw はレジスタ長（つまり32とか64）ビット幅が16の場合、– 重複がない整数の集合[1,16]でも[0,15]でも可→ 連続する w 個の整数の集合を一つにパック
例： { 3, 5, 9, 12 } = <0000 1001 0001 0100>→ 集合の演算 ⇔ ビット列の論理演算
例： { 3, 5, 9, 12 } ∪ { 2, 5, 8, 9, 15 } = { 2, 3, 5, 8, 9, 12, 15 }
<0000 1001 0001 0100>
各整数は、ビットが⇔ or <0100 0001 1001 0010>
立つ位置と対応する<0100 1001 1001 0110>
2005/10/11

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

北海道大学 Hokkaido University

26

長いビット列を扱う場合


2倍長の加算と減算– (z1, z0) ← (x1, x0) + (y1, y0)z0 ← x0 + y0c ← (z0 < x0)
z1 ← x1 + y1 + c–(z1, z0) ← (x1, x0) - (y1, y0)z0 ← x0 - y0b ← (x0 < y0)z1 ← x1 - y1 - b
ここでも、すべてunsigned

2倍長のシフト （0≦n≦w）– (y1, y0) ← (x1, x0) << ny1 ← x1 << n | x0 >> (w – n)y0 ← x0 << n–(y1, y0) ← (x1, x0) >> ny0 ← x0 >> n | x1 << (w – n)y1 ← x1 >> n

参考：「ハッカーのたのしみ -本物のプログラマはいかにして問題を解くか」ヘンリー・S・ウォーレン, Jr.: “Hacker’s Delight”訳本
2005/10/11

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