1

北海道大学
Hokkaido University

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

2005/10/4

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

第1回
準備：用語と予備知識
パターン照合問題とは
テキストアルゴリズムの基本用語
有限オートマトンについて索引データ構造を用いた検索との違い

北海道大学 Hokkaido University

3

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


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

パターン P: compress

テキスト T:

2005/10/4

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 by
Amir, Benson and Farach [Amir94].
情報知識ネットワーク特論 講義資料

北海道大学 Hokkaido University

4

Existence problem と All-occurrences problem
Existence problem

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

Yes!

All-occurrences problem

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

210

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

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

北海道大学 Hokkaido University

5

索引データ構造を用いた検索との違い
文字列照合による検索

索引データ構造を用いた検索

小規模文書群に対する検索向き(例：UNIX の grep)

中・大規模DBに対する検索向き(例：namazu, sufary, mg, Googleほか)

 長所
 余計なデータ構造が不要
 データの更新に対して柔軟 短所
 検索がおそい スケーラビリティが低い

2005/10/4

 長所
 検索がはやい スケーラビリティが高い
 短所
 索引構造を構築する手間がかかる データの更新に対して柔軟性に欠ける
 索引構造のためのスペースが必要

情報知識ネットワーク特論 講義資料北海道大学 Hokkaido University6

基本用語（計算量の記法）


アルゴリズムの良し悪しを明確にするためには、計算の複雑さを明確に判断する必要がある– 計算にかかる時間や必要となる主記憶容量（メモリ量）が入力（データ）長 n に対してどのくらいかかるのか？

big-O記法

漸近的計算量の上界を示す記法（下界を示すΩ記法もある）– 定義：
f と g を整数から整数への関数とする。このとき、ある定数CおよびNについて、任意のn>Nに対し f(n) < C・g(n) ならば、f(n) = O(g(n)) と書く。
（f は オーダー g という）
– f と g が同じオーダーのとき、すなわち f(n) = O(g(n)) かつ g(n) = O(f(n))
が成り立つとき、 f = Θ(g) と書く。
– 計算時間を入力長nの関数T(n)で表し、いま T(n) = O(g(n)) であるとする。
これはすなわち、「漸近的には高々g(n)に比例した時間しかかからない」ということを意味している。
例：O(n)、O(n・log n)

2005/10/4

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

北海道大学 Hokkaido University7

基本用語（アルファベット、文字列の定義ほか）


用語の定義

– ∑: 文字の空でない有限集合（アルファベット）
文字 a∈∑は、
letters, characters, symbolsとも呼ばれる

例： ∑={a,b,c,…}, ∑={0,1}, ∑={0x00, 0x01, 0x02,…, 0xFF}– x∈∑*: 文字列（string）、語（word）、テキスト（text）|x|: 文字列xの長さ
例： |aba|=3
 ε: 長さが0の文字列＝空語（empty word）という。すなわち |ε|=0


– x[i]: 文字列xのi番目の文字– x[i. . j]: 文字列xのi番目からj番目までの連続した文字のならび
i>j の場合は、便宜上 x[i. . j]=ε とする x[1. . i] を特にxの接頭辞（prefix）という
 x[i. . |x|] を特にxの接尾辞（suffix）という


部分文字列（substring, subword）あるいはファクター（factor）と呼ばれる– 文字列xとyについて、yから0文字以上の文字を取り除くと、xに等しくなるとき、xをyの部分列（subsequence）という


例： x=abba は、y=aaababaab の部分列部分文字列との違いに注意！

– x = a1a2…ak ∈∑* に対して、これを反転させた文字列akak-1…a1をxR と表記する
2005/10/4

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

北海道大学 Hokkaido University

8Prefix, Factor, Suffixの例

w = cocoa
factorprefixccococ
coco

εcocoaoococo

suffixaoa
coaocoa演習1： 語 w=ROYCE のprefixを列挙せよ。
演習2： 語 w=ろくろくび のfactorを列挙せよ。
2005/10/4

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

北海道大学 Hokkaido University

9

有限オートマトン

有限オートマトン(Finite Automaton)– 出力が入力と内部状態に応じて決定される自動機械（Automata）– 状態数は有限個である– 状態遷移や出力の定義や補助記憶領域の有無によって、さまざまな種類がある


非決定性オートマトン、順序機械、プッシュダウンオートマトンなど– （機械的な）言語を定義する能力があり、文字列の字句解析に用いられることが多い
計算機科学分野ではあらいる方面ででてくる基礎的概念！
 ソフトウェア設計（UMLの状態遷移図）などにも用いられる！
 もちろん、パターン照合問題にも深く関係がある！
※ 参考文献： 「オートマトンと計算可能性」 有川節夫・宮野悟著、培風館「形式言語とオートマトン」 守屋悦朗著、サイエンス社
2005/10/4

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

北海道大学 Hokkaido University10（決定性）有限オートマトンの定義
（決定性）有限オートマトン M = (K, Σ, δ, q0, F)– K = {q0, q1, …, qn} : 状態の集合– Σ= {a, b, …, c} : 文字の集合（アルファベット）– q0 : 初期状態
– δ : 遷移関数 K×Σ→ K– F : 受理状態の集合（K の部分集合）



遷移関数についてヘッド：（内部状態を保持）– 次のようにして定義域を拡張する
δ(q, e) = q(q ∈ K) δ(q, ax) =δ(δ(q, a), x)

入力テープ：

a1 a2

qai



(q∈K, a∈Σ, x∈Σ*)– 文字列wに対してδ(q0, w)は、語wを入力したときの状態をあらわす。
– δ(q0, w) = p ∈ F であるとき、M はwを受理するという。
– Mが受理する文字列全体 L(M) ={w|δ(q0, w) ∈ F} を有限オートマトンMによって受理される言語という。
2005/10/4

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

北海道大学 Hokkaido University11（決定性）有限オートマトンの例
状態遷移

状態遷移図（図２）aδ(q0, aba) = δ(δ(q0, a), ba)= δ(q1, ba)= δ(d(q1, b), a)= δ(q0, a)= q1 ∈ F

q0bbaq2

L(M) = {a(ba)n | n≧0}a,bヘッド入力テープ

2005/10/4

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

北海道大学 Hokkaido University12

非決定性の有限オートマトンの定義
非決定性有限オートマトン M=(K, Σ, δ, Q0, F)– K = {q0, q1, …, qn} : 状態の集合– Σ= {a, b, …, c} : 文字の集合（アルファベット）– Q0⊂K : 初期状態の集合
つまり、遷移する先が– δ : 遷移関数 K×Σ→ 2K
一意には決まらない！
– F : 受理状態の集合（K の部分集合）



遷移関数について：

現在の状態が複数存在– 遷移関数の定義域を次のようにしてK×Σから K×Σ*へ拡張する
δ(q, e) = {q} δ(q, ax) = ∪p∈δ(q, a) δ(p, x)(q∈K, a∈Σ, x∈Σ*)– さらに 2K×Σ* に拡張δ(S, x) = ∪q∈S δ(q, x)– x∈Σ* についてδ(Q0, x)∩F ≠Φ であるとき、 Mはxを受理するという。
2005/10/4

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

北海道大学 Hokkaido University13

非決定性オートマトンの例q0bq1

bq2a,b
非決定性有限オートマトンの状態図

例えば abb に対しては δ(q0, abb) = δ(q0, bb)= δ(q0,b)∪δ(q1,b)= {q0}∪{q1}∪{q2}= {q0, q1, q2}となり q2∈F であるから abb∈L(M) である。

2005/10/4

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

北海道大学 Hokkaido University

14

順序機械
順序機械とは･･･
atcgaatccg...

atcgaatccg...

有限オートマトン

順序機械

一種の翻訳機！
Yes
Yes
2005/10/4

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

北海道大学 Hokkaido University

15

順序機械の概念図
入力テープ

出力テープ

2005/10/4

a1 a2ai

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

北海道大学 Hokkaido University

16

順序機械の例

1/1q0

λ(q0, 011)

0/0

=λ(q0, 0)λ(δ(q0,0), 11)
q3

1/0

1/00/0q50/0q1

2005/10/4

1/1

0/0

1/1

q40/0
1/00/0q2= 0λ(q4, 11)= 0λ(q4, 1)λ(δ(q4,1), 1)= 01λ(q5, 1)= 010

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

北海道大学 Hokkaido University

17

索引データ構造を用いた検索との違い
文字列照合による検索

索引データ構造を用いた検索

小規模文書群に対する検索向き(例：UNIX の grep)

中・大規模DBに対する検索向き(例：namazu, sufary, mg, Googleほか)

 長所
 余計なデータ構造が不要
 データの更新に対して柔軟
 短所
O(n)
 検索がおそい スケーラビリティが低い

 長所O(m log n) 検索がはやい スケーラビリティが高い
 短所
 索引構造を構築する手間がかかる データの更新に対して柔軟性に欠ける
 索引構造のためのスペースが必要

文字列照合ベースの大規模全文検索DBシステムがある！
2005/10/4

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

北海道大学 Hokkaido University18

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


導入事例：

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


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

2005/10/4

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

北海道大学 Hokkaido University

19

第１回 まとめ

パターン照合問題とは、– テキストT中に含まれるパターンPの出現を求める問題– Existence problemとAll-occurrence problemがある

テキストアルゴリズムの基本用語– 計算量の記法：big-O記法– アルファベット、文字列、Prefix、Factor、Suffix有限オートマトン– 決定性有限オートマトン： 言語を定義できる– 非決定性有限オートマトン： 現在の状態と遷移先が複数ある– 順序機械： 入力に対して、逐次に出力がある

索引データ構造を用いた検索との違い– 文字列照合による検索は、索引データ構造を用いた検索に比べて遅いというのが一般的な見方だが、優れた利点もある。

2005/10/4

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