Vol. 0

No. 0

1959

情報処理学会論文誌

近似文字列照合による全文検索のための接尾辞配列の高速走査法
内

山

将

夫†

井 佐 原

均†

近似文字列照合による全文検索では，入力パターンと一定以下の編集距離にある部分テキスト全てをテキストから検索する．近似文字列照合による全文検索は，テキストを接尾辞トライにより索引付
けし，それを利用して検索することにより実現できる．しかし，接尾辞トライの占める空間領域は大きいため，接尾辞配列を索引として利用することもある．接尾辞配列を索引として利用する場合には，従来研究では，接尾辞トライ上での探索を接尾辞配列上での 2 分探索により模擬している．それに対して，本稿では，2 分探索ではなく，補助的な配列を用いることにより，高速に，接尾辞トライ上での探索を模擬することができる手法を提案した．更に，2 分探索による方法を利用した場合と提案手法を利用した場合とにおける検索速度を実験的に測定し，提案手法の方が検索速度が速いことを示した．

Fast Traversal of Suffix Arrays
for Full-Text Approximate String Matching
Masao Utiyama† and Hitoshi Isahara†
Given a text and an input pattern, the goal of full-text approximate string matching is tosearch for all parts of the text that match the pattern. Full-text approximate string matching
can be performed using a suffix trie as an index of the text. A suffix trie, however, is relatively
large. So, a suffix array, which is a compact representation of a suffix trie, is often used tosimulate searches on a suffix trie. A binary search algorithm is used to search the array. A
method is described in this paper that uses an auxiliary array to simulate searches on a suffix
trie. The method does not use a binary search algorithm so that it can perform a faster
simulation. Experiments showed that the proposed method is faster than one using a binary
search algorithm.

領域としている自然言語処理においても，翻訳メモリ

1. は じ め に（ translation memory ）☆ などでは，入力文と類似した

近似文字列照合による全文検索とは，入力パターン

文（類似用例）を検索する必要があるので，近似文字と検索対象テキストとが与えられたとき，テキスト中

列照合の技術が役立つ．

における部分テキストのうちで，入力パターンとの違近似文字列照合による全文検索の方法には，あらか

いが一定以下の（入力パターンと類似した）部分テキ

じめテキストに索引付けをしておいて，その索引をスト全てを検索することを言う．

利用してパターンを検索する方法と，索引は利用せ

近似文字列照合による全文検索には，様々な用途がずに，パターンが与えられる毎にテキスト 全体を走ある．たとえば ，光学的文字読み取り装置（ optical

査する方法とがある☆☆ ．索引を利用する方法では，3character reader, OCR ）により読み取られたテキス

章で述べるように，接尾辞トライ（ suffix trie ）あるトを検索したいときには，そのテキストの中には読み取り誤りがある可能性があるので，検索もれをなく☆

翻訳メモリとは，対訳文からなるデータベースのことである．たとえば ，翻訳メモリとして日英対訳データベースがあり，それを日英翻訳支援に使う場合には，ユーザが，ある日本語文をシステムに入力したときには，システムは，それに類似した日本語文を翻訳メモリから探し ，その対訳英文を出力する．ユーザ
は，出力された英文を参考にして，入力日本語文を翻訳する．
☆☆
本稿では，索引を利用しない場合については考察の対象外である．なお，索引を利用しない方法についてのサーベイ論文としては，文献 11) がある．

すためには，パターンに厳密に一致する部分テキスト
だけでなく，ある程度の違いも許した部分テキストも検索する必要がある．また，本稿の著者らが主な研究† 通信総合研究所
Communications Research Laboratory0Vol. 0No. 01

近似文字列照合による全文検索のための接尾辞配列の高速走査法

いは接尾辞木（ suffix tree ）6) を索引とする方法があSuffix trie

る 1),2),5),12),13),15) が，接尾辞トライあるいは接尾辞AB

木は空間領域を多くとるので，その代りに，接尾辞
配列（ suffix array ）9) を利用することもある 1),2),12) ．
接尾辞トライを利用した検索法☆ では，トライの根かC

らノードを下に辿ることにより検索をする．また，接尾辞配列を利用した検索では，接尾辞トライにおけるノードの走査を模擬することにより，検索を実現する．

C

B
D

C

D

E

A

A

$

B

B

A

A

$

B

B

D

E
$

8
A

A

7
B

B

D

E

A

法 1),2),12) では，次に走査すべきノード を決めるため

D

E

A

$

B

に 2 分探索を利用していた．したがって，その分だけ

A

$

B

E

B

E

$

E

$

案する方法では，補助的な配列を用いることにより，2分探索をせずに次に走査すべきノードを決めることができる．そのため，2 分探索をする方法に比べて，高速に検索することができる．

$
9

E

こ の ノ ード の 走 査 の 模 擬 に お い て ，従 来 の 手

計算コストが掛かっていた．一方，我々が，本稿で提

E

D

6
5
4
3
2
$
1

以下，2章では用語などの準備をし，3章では，接尾辞トライを用いた近似文字列照合による全文検索について述べ，4章で，接尾辞配列により接尾辞トライの走査を模擬する方法について述べる．5章では，提案手法の有効性を実験により確認し ，6章で関連研究を

Text

A B C A B D A B E $1 2 3 4 5 6 7 8 9

図1Fig. 1

テキストと接尾辞トライ．
Text and its suffix trie.

述べる．7章は結論である．

2. 準

は，n 個の葉を持ち，それらは T 中の全接尾辞を表す．

備

各葉は，それが表す接尾辞の開始位置をもち，T の全

2.1 接 尾 辞 等

接尾辞が，左の葉から右の葉に Σ 上の辞書式順序で並アルファベット Σ に対して，Σ の要素を「文字」あんでいる．ここで，ある葉が接尾辞 ti..n を表すとする

るいは「最小単位」と呼ぶ．また，Σ の要素数（アルと，そのことは，根からその葉に至る長さ n − i + 2 のファベットの大きさ）を |Σ| とする．

道において，根からその葉までの各辺のラベルとして，長さ n のテキスト T とは，文字列 T = t1 t2 . . . tn で

ti , ti+1 , . . . , tn , $ を付けることにより示される．ここある．ここで ti ∈ Σ である．また，T 中の i 番目から j

で，$は，$ 6∈ Σ であるような特別な区切記号である．

番目 (i ≤ j) までの部分文字列は，ti..j = ti ti+1 . . . tj

図 1 には，“ABCABDABE” というテキストから作である．次に，T の位置 i から始まる接尾辞（ suffix ）られる接尾辞トライを示す．

とは，ti..n のことである．また，T [i] = ti である．

なお，あるノードの深さとは，根からそのノードまで

さらに T の部分文字列 ti..j からなる集合を W (T ) =の道における辺の数である．また，先行順（ preorder ）{X|X = ti..j } とする．W (T ) は，T のなかで異なるの走査とは，1 ）根に訪問する，2 ）根に子供があれば左部分文字列全てからなる集合である．たとえば，T =の子供から順番に先行順走査する，という順に再帰的

abab のとき，W (T ) = {a, b, ab, ba, aba, bab, abab} でにノードを訪問する方法を言い，後行順（ postorder ）ある．ここで，a, b，ab などは複数回 T 中に現れるの走査とは，1 ）根に子供があれば左の子供から順番

が，W (T ) には一つずつしか含まれない．

に後行順走査する，2 ）根に訪問する，という順に再2.2 接尾辞ト ライ

帰的にノード を訪問する方法を言う．

テキスト T の接尾辞トライとは，T の全ての接尾辞を保持しているトライのことである☆☆

．このトライ

2.3 接尾辞配列
テキスト T の接尾辞配列 S とは，T の各接尾辞への
ポ インタを格納した一次元配列であり，各ポ インタ☆

本稿では，接尾辞トライに基づく検索法を 3章で概説するが，その方法は接尾辞木にも適用できる．
☆☆
以下の用語，「 トライ」「 根」「 葉」「 ノード（ 節点）」
「 辺」
「 道」
「子供（ 子）」の定義については文献 17) を参照のこと．

は，それが指し示す接尾辞の辞書式順序でソートされている．つまり，S[i] は T の S[i] 番目の接尾辞 tS[i]..nの開始位置であり，i < j のときには，tS[i]..n の方が，

2

Text

情報処理学会論文誌
1

2

3

4

5

6

7

8

9

A

B

C

A

B

D

A

B

E

1959

と 4(n + 1) バイトである☆1 ．また，テキストの占める空間領域は，アルファベットの大きさにもよるが，|Σ| ≤ 256 のときには n バイト，|Σ| ≤ 65536 のとき

Suffix arraylcp array

Suffixes denoted by S[i]には 2n バイト，それ以上の大きさのアルファベット

S[1]

1

lcp[1]

0

ABCABDABEについては，4n バイト必要である．よって，最大 12n

S[2]

4

lcp[2]

2

ABDABE

バイトにより，テキストと接尾辞配列と lcp 配列とを

S[3]

7

lcp[3]

2

ABE

格納できる．

S[4]2

lcp[4]0

BCABDABES[5]5

lcp[5]

1

BDABE

ドが必要となる．これは，もちろん，12n バイトより

S[6]

8

lcp[6]

1

BEも多くの空間領域を必要とする．また，接尾辞トライ

S[7]

3

lcp[7]

0

CABDABEのコンパクトな表現である接尾辞木を格納するには，

S[8]

6

lcp[8]0

DABE

O(|Σ|n) だけの空間領域が必要である☆2 ．そのため，

S[9]

9

lcp[9]

0E

アルファベットとして日本語の文字集合のように大きlcp[10]0

図 2 テキストと接尾辞配列と lcp 配列．
Fig. 2 Text, its suffix array and lcp array.

tS[j]..n よりも，辞書順において，前に位置する．これは，接尾辞トライの葉のみを左から右に一次元配列に格納したものと等しい．
テキスト T の lcp（ longest common prefix ）配列

なお，接尾辞トライを構築するには，O(n2 ) のノーな要素数を持つものを利用するときには，接尾辞木のサイズは非常に大きくなる 9),12),16) ．

3. 接尾辞トライを用いた近似文字列照合による全文検索の概要
本章では，文献 13) に基づいて，接尾辞トライを用いた近似文字列照合による全文検索の概要を述べる．
以下では，まず，近似文字列照合による全文検索を定とは，n + 1 個の整数からなる配列である．lcp[i] は，

義し，次に，動的計画法（ dynamic programming ）に

2 ≤ i ≤ n については，tS[i−1]..n と tS[i]..n との共通す

より二つの文字列間の編集距離（ edit distance，略しる先頭部分の（最長の）長さである．また，アルゴ リて距離とも言う）を求める方法☆3を示し，最後に，接ズムの都合上，lcp[1] = lcp[n + 1] = 0 と定義する．

尾辞トライを用いて近似文字列照合をする方法を示す．

図 2 には，テキスト “ABCABDABE” に対する接3.1 近似文字列照合による全文検索

尾辞配列，および，それに対する lcp 配列を示す．こ

長さ m のパターンとは，文字列 P = p1 p2 . . . pm のの図で ，たとえば ，lcp[2] = 2 であるが ，これは ，ことである．近似文字列照合による全文検索とは，パtS[1]..n = ABCABDABE と tS[2]..n = ABDABE

ターン P とテキスト T と許容値 t(≥ 0) が与えられたとの共通先頭部分の長さである．図では，lcp[i] > 0

とき，W (T ) の要素 X のなかで，パターン P との編集のときには，共通先頭部分に下線を引いてある．
なお，接尾辞配列 S において，S[i] における深さ jの文字とは，tS[i]+j−1 のことである．ただし，S[i] +距離 dist(P, X) が t 以下であるような X 全てを見付けることであると定義する☆4 ．

3.2 動的計画法による編集距離の計算

j − 1 > n のときには “$” とする．たとえば ，図 2 で文字列 X = x1 x2 . . . xu と Y = y1 y2 . . . yv の編集

は，S[4] = 2 について，深さ 1 の文字は tS[4]+1−1 =

距離を dist(X, Y ) とする．この距離は，X を Y に一tS[4] = t2 = B であり，深さ 2 の文字は t3 = C ，深さ致させる操作として，置換・削除・挿入を許し，それら3 の文字は t4 = A である．また，範囲 [u..v] での深さのコストとして，xi と yj の置換コストを sub(xi , yj )，j といったときには，u ≤ i ≤ v について，各 S[i] における深さ j の文字からなる一次元配列を示すこととする．範囲を指定しないときには u = 1, v = n である．
たとえば，図 2 では，範囲 [3..7] の深さ 1 は “ABBBC”
を示し，範囲 [3..7] の深さ 2 は “BCDEA” を示す．

2.4 空 間 領 域
長さ n のテキスト T について，接尾辞配列と lcp 配列の占める空間領域は，テキストへの各ポ インタを

4 バ イトで表現するとすると，それぞれ ，4n バ イト

☆1

実際上は，lcp 配列の要素の最大値が 65536 を越えることはな
いため，lcp 配列は 2(n + 1) バイトで格納可能である．
☆2
なお，これは，それぞれのノード の子ノード をアルファベット
サイズの配列として作成する場合であり，2 分木などで表した場
合には O(n) の空間領域が必要である．
☆3
動的計画法を用いた距離計算については，詳しくは，たとえば，
文献 6) を参照のこと．
☆4
この定義では，X の T 中での出現位置は検索しない．しかし ，
本稿で述べるアルゴ リズムを修正して出現位置も検索するようにすることは容易である．

Vol. 0No. 03

近似文字列照合による全文検索のための接尾辞配列の高速走査法

xi の削除コストを del(xi )，yj の挿入コストを ins(yj )としたとき，X を Y に一致させるために必要な操作
系列のコストの和の最小値として定義される．

dist(X, Y ) を計算するために，x1..i と y1..j との距離を D[i, j] と定義する．このとき，dist(X, Y ) = D[u, v]である．D[i, j] は以下のように定義できる．
D[0, 0] = 0,D[i, 0] = D[i − 1, 0] + del(xi ),D[0, j] = D[0, j − 1] + ins(yj ),

D[i − 1, j − 1] + sub(xi , yj )D[i, j] = min  D[i − 1, j] + del(xi )

0

1

2

3

4

5

6

7

φ

a

c

d

f

b

d

f

0

φ

0

1

2

3

4

5

1

a

1

0

1

2

3

4

2

d

2

1

1

1

2

3

3

f

2

2

1

2

4

d

2

図3



.

D[i, j − 1] + ins(yj )打ち切りを伴なう距離計算．文献 13) Table 2 の一部を若干変更したもの．
Fig. 3 Distance calculation with cut-off. Modification ofa part of Table 2 in 13).

きには，0 行から C[j] + 1 行目までについて，距離を

ただし ，1 ≤ i ≤ u，1 ≤ j ≤ v である．また，計算すれば十分である．なぜなら，C[j] + 2 行目以降

sub(xi , yj ), del(xi ), ins(yj ) ≥ 0 であり，かつ，xi =については，距離が t より大きいことが分かっている

yj のときには，sub(xi , yj ) = 0 である．なお，D のこ

ので，デフォルト値として，t + 1 を与えれば十分でとを距離行列と呼ぶ．

あるからである 14) ．なお，C[0] は，D[i, 0] ≤ t を満これらの式の解釈は以下の通りである．まず，D[0, 0]

す最大の i である．

は，空文字列と空文字列との距離である．次に，D[i, 0]

打ち切りを伴なう距離計算の例として，X = adf dPdel(xk ) と等価であるが，これは，x1..iと Y = acdf bdf に対して，コスト 1 の距離について，と (y1 の前の ）空文字列とを一致させるには ，x1..i

許容値を 1 として，このアルゴ リズムにより距離行列を削除する必要があることを示す．また，D[0, j] は，を計算する過程を次の段落に示し，その結果を図 3 に

ins(yl ) と等価であるが，これは，（ x1 の前の）1≤l≤j示す．なお，図 3 の空白部分には，デフォルト値（ =許

は，

P

1≤k≤i

空文字列と y1..j とを一致させるには，y1..j を x1 の前に挿入する必要があることを示す．

容値+1=2 ）が入っているとする．
まず，j = 0 について ，D[0, 0] = 0, D[1, 0] =次 に ，D[i, j] を 計 算 す る に は ，ま ず，x1..i−1 と

1, D[2, 0] = 2 である．ここで，D[2, 0] > 1 なので，

y1..j−1 等の距離計算が済んでいるとする．この先，計算を打ち切り，C[0] = 1 とする．j = 1 について

距離計算を続けていくとして，xi と yj について可能は，C[0] + 1 = 2 までの値，D[0, 1] = 1, D[1, 1] =な操作は，xi と yj を置換するか，xi を削除するか，yj

0, D[2, 1] = 1 を計算し ，C[1] = 2 とする．同様に，を（ x1..i の後に）挿入するかしかない．従って，距離C[2] = 2, C[3] = 2, C[4] = 3 となる．j = 5 についD[i, j] を求めるには，これらの操作の中で，これまでては，全ての距離が 1 より大きいので，C[5] = 0 となに計算済みの距離とコストの和が最小となる操作を選る．この時点で，D[4, 5] > 1 であるので，D[4, 7] > 1

択すれば良い．

であることが分かる．したがって，この時点で全体のなお，以下では，挿入／削除コストを 1，置換コス

距離計算を打ち切ることができる．

トを同一文字には 0 異なる文字には 1 としたときに計3.4 接尾辞ト ライを用いた近似文字列照合

算される編集距離を「コスト 1 の距離」と呼ぶ．

3.4.1 接尾辞ト ライの性質

3.3 距離計算の打ち切り
二つの文字列間の距離を計算するとき，ある許容値

接尾辞トライの次の二つの性質 13) を利用すると，パターン P とテキスト T と許容値 t が与えられたとき，

t を定めて，それよりも距離が大きくなったら距離計

P と T の全ての接尾辞との距離計算を効率的に実行で算を打ち切ることにすると，距離計算の手間を省くこ

きる．

とができる．これは以下のアルゴ リズムによる 14) ．

性

質

1

距離行列を計算するときに，列 j を 0 から順に大きトライにおけるあるノード を v とすると，根から v

くしながら，D[i, j] を計算するが，その計算のとき，への道は，根から v を通って葉に至るまでの道に対応

D[i, j] ≤ t を満たすような最大の i を C[j] として記録する全ての接尾辞に共有されている．つまり，根からしておく．もし，全ての i について，D[i, j] > t なら，v までの道は，それら接尾辞の共通の先頭部分と対応

C[j] = 0 とする．次に，j + 1 列目の値を計算するとしている．そのため，それら接尾辞とパターンとの

4

1959

情報処理学会論文誌

距離行列については，根から v に至るまでの先頭部分
においては，等しい距離が格納された列が得られる．
たとえば ，図 1 においては，たとえば ，接尾辞 “AB-CABDABE” と “ABDABE” と “ABE” とは，先頭部分の “AB” を共有しているので，これらについての距離行列は，“AB” に関する列を共有する．
そのため，トライを根から先行順に辿り，その際に，大域的に保持される一つの距離行列を一列ずつ更新していけば，あるノードに到達したときには，そのノードに関連する全ての接尾辞について，根からそのノード までの共有する先頭部分について（パターンとの）距離が計算されていることになる．
性質2ある接尾辞の距離行列について，もし，距離行列のj 列において，全ての距離が許容値 t よりも大きいとしたら，j + 1 列目以降まで列を伸ばしていったとしても，やはり，距離は，t よりも大きい．そのため，一旦，距離が t よりも大きくなったら，それ以上，トライを辿る必要はないので探索を打ち切ることができる．

3.4.2 検索アルゴリズム
これら二つの性質を利用した検索アルゴ リズムを C
風の擬似コード として図 4 に示す☆ ．図 4 では，mainにおいて，距離行列の計算のための初期化をし，その後で，根の全ての子供に対して再帰的に search を呼出す．search を再帰的に呼出すことにより，トライ
を先行順に辿ることができる．search は，先行順にトライを巡回する際に，距離行列の値を計算し，その/* 変数などの説明 */D は 3.2 節における距離行列
C は 3.3 節において距離計算の打ち切りに利用した配列
P はパターン．P[i] はパターンの i 番目の文字 (1<=i<=m)T(node) は node とその親ノード を結ぶ辺に対応する文字
t は許容値/* アルゴ リズム */main(){/* 初期化 */C[0] := D[0,0] := 0for(i:=1; i<=m; i++){D[i,0] := D[i-1,0] + del(P[i])if(D[i,0]<=t){C[0]:=i}else{break}}/* 検索 */
foreach child in 根の全子供 {search(child, 1)}}
search(node, j){if (node が葉) returnif (cutp(T(node), j)) returnif (D[m,j]<=t) 検索成功
foreach child in (node の全子供) {search(child, j+1)}}
cutp(textChar, j){/* パターンに対するデフォルト距離 */D[m,j] := t+1/* 距離行列における j 列目の距離を計算する */C[j] := 0D[0,j] := D[0,j-1] + ins(textChar)for(i:=1; i<=min(C[j-1]+1, m); i++){D[i,j] := min(D[i-1,j-1]+sub(P[i],textChar),D[i-1,j]+del(P[i]),D[i,j-1]+ins(textChar))if(D[i,j]<=t){C[j] := i}}/* 打ち切り可能性を判定する */if(C[j]=0){
return true}else{/* j+1 列目の計算に必要なデフォルト値 */if(C[j]>C[j-1]){D[C[j]+1,j] := t+1}
return false}}
図 4 近似文字列照合による全文検索のアルゴ リズム．
Fig. 4 Full-text approximate string matching algorithm.

値に応じて不要な枝を刈り込む．

search(node,j) においては，
(1)

(2)

(1)

まず，node が葉かど うかを調べ，もし葉であるなら，既にパターンと接尾辞との比較は終了

うに，打ち切りを伴なう距離計算の場合には，しているので，探索を打ち切る．

必ずしもD[m,j] が計算されないからである．

次に ，cutp(T(node),j) は ，距離行列の j 列(2)（ true ），そうでないときには偽（ false ）を

(4)

(3)

もし，C[j]=0 なら，全ての距離が許容値より大返す．

きく，距離計算の打ち切りが可能なので，true

もし，パターンと，根から node までの道に対応を返す．そうでないなら，j+1 列目の計算に必する文字列との距離D[m,j] が許容値t 以下なら，

要なデフォルト値を設定してから false を返す．

パターンの検索に成功したことになる．

j+1 列目の 計算に 必要なデ フォルト 値に ついては ，

最後に，node の全ての子供に対して，再帰的に

図 5 に 示 す 距 離 行 列 を 利 用し て 説 明 す る ．ま ず，search を適用する．

C[j]>C[j-1]，つまり，C[j]=C[j-1]+1 の場合を 考

上述の（ 2 ）におけるcutp(T(node),j) での処理は以下のようなものである．

☆

次に，距離行列におけるj 列目の距離を計算する．このとき，同時に，C[j] を計算する．

目の値を計算し ，打ち切り可能なときには真(3)

D[m,j]:=t+1 としてデフォルト値を設定する．
この値を設定する理由は，3.3節で説明したよ

ただし，代入演算子を “ :=” とし，比較演算子の等号を “ =” としている．

える☆☆ ．一般に，D[i,j+1] の計算には，D[i-1,j],D[i-1,j+1], D[i,j] が必要である．j 列までの計算に☆☆

C[j] の取り得る値は， 0 以上 C[j-1]+1 以下の整数値である．

Vol. 0No. 05

近似文字列照合による全文検索のための接尾辞配列の高速走査法

j-1

j

j+1

i-1

i

D[i,j+1]

0

1

2

φ

A

B

0

φ

0

1

2

1

D

1

1

2

2

C

2

2

2

3

A

図 6 “DCA” と “AB” との距離行列（ 探索が打ち切られる場合）．
Fig. 6 Distance matrix between “DCA” and “AB” (cutoff).
C[j-1]

C[j-1]+1 = C[j]C[j]+1a

D[C[j]+1,j+1]

default value
図 5 距離のデフォルト値の取り扱い．
Fig. 5 Handling default values for distances.

よると，図 5 の斜線部の値（ D[0,j],. . . , D[C[j],j] ）は cutp でのfor ループの終了時点で計算済みである．

0

1

2

3

φ

B

C

A

0

φ

0

1

2

3

1

D

1

1

2

3

2

C

2

2

1

2

3

A

1

図 7 “DCA” と “BCA” との距離行列（ 検索に成功した場合）．
Fig. 7 Distance matrix between “DCA” and “BCA”(success in approximate string matching).

そのため，j+1 列目において，0<=i<=C[j] については，D[i,j+1] を問題なく計算できるが，D[C[j]+1,j+1]

らのうちで最初に述べる方法は，従来研究 1),2),12) でを計算するためには，for ループで計算されていない図

用いられている，2 分探索を利用する方法であり，次5 のa の値が必要である．ところで，この値は，3.3節でに述べる方法が，本稿で提案する，lcp 配列を用いても述べたように，許容値t よりも大きいことが分かって

先行順走査をする方法である．それらの方法を述べたいるので，デフォルト値として，t+1 を D[C[j]+1,j]

後で，提案手法による先行順走査を用いた近似文字列に代入すれば良い．なお，C[j]<=C[j-1] のときには，照合による全文検索アルゴ リズムを示す．

j+1 列目の計算は，デフォルト値を使わなくても可能
である．

4.1 2 分探索による接尾辞配列の先行順走査
接尾辞トライの先行順走査を接尾辞配列により模擬

接尾辞トライを用いた近似文字列照合の例として，する方法としては，接尾辞配列を 2 分探索することにテキスト “ABCABDABE” から作られる接尾辞トラより，接尾辞トライにおけるノードと対応する接尾辞イ（ 図 1 ）に対して，パターン “DCA” を検索した場

配列の範囲を見付け，その範囲に基づいて先行順走査合を考える．このとき，根から “AB” までを辿ったとを模擬するというものが考えられる．これは，従来研

きの，コスト 1 の距離による距離行列は，図 6 のよう

究 1),2),12) で用いられている方法である．

になる．そのため，距離の許容値が 1 の場合には，こ接尾辞配列の各要素と接尾辞トライの葉とは一対一の時点でトライの探索を打ち切ることができる．次に，に対応するので，接尾辞配列は接尾辞トライを表現で

たとえば，トライを “BCA” まで辿ったときの距離行

きる．たとえば，図 1 の接尾辞トライと図 2 の接尾辞列を図 7 に示す．このときには，D[3,3]=1 であり，こ配列とは一対一に対応している．

の値は許容値以下であるので，“BCA” はパターンに

また，接尾辞配列は，接尾辞が辞書順にソートされ近似的に一致したとして検索される．なお，図 6 と図ているので，2 分探索することによりトライの走査を

7 において，空欄となっている部分は，距離のデフォ模擬できる．たとえば，図 2 において，“BCA” を，厳ルト値（ 許容値+1=2 ）が入っているものとする．

密一致（ exact match ）で検索したいとする．そのときには，まず，深さ 1 で，“B” を 2 分探索すると，そ4. 接尾辞配列による接尾辞トライの先行順走査の模擬れが，[4..6] の範囲にあることがわかるので，次に，そ本章では，まず，接尾辞トライにおける先行順走査が [4..4] の範囲にあることがわかり，最後に，深さ 3 にを，接尾辞配列で模擬する二つの方法を述べる．それ

おいて，“A” を検索すると，これも [4..4] の範囲にあの範囲で，深さ 2 において，“C” を検索すると，それ6

情報処理学会論文誌

1959

るので，“BCA” が図 2 の接尾辞配列にあることが分接尾辞トライにおいて，S[i − 1] に対応する葉と S[i]かる．これは，図 1 の接尾辞トライにおいて，根から，に対応する葉とについて，それぞれ，根から葉まで

検索文字列が “BCA” となるようにノード を辿っていの道を考えたとき，それら二つの道の共有部分の長くこと同等である．このように，接尾辞配列の範囲とさ（ 辺の数 ）であることが 分かる．たとえば ，図 2

深さを合わせたものは，接尾辞トライの辺に一対一対において，tS[1]...n = t1...n = ABCABDABE と応する（したがって，各辺の子供のノードとも一対一

tS[2]...n = t4...n = ABDABE とは，“AB” を共有し対応する）ことが分かる．

ているが，このことは，図 1 においては，それら接尾上記は，厳密一致における接尾辞配列の探索例であ辞に対応する道において，先頭の “AB” の部分が共有るが，近似文字列照合をするには，接尾辞トライでノーされていることに対応する．そして，このときの共有

ド の子供全てを枚挙していたのと同様なことを，接尾部分の長さは lcp[2] = 2 である．

辞配列でもしなければならない．たとえば，図 1 の接このことを利用すると，次のようなコード 断片（こ尾辞トライの根に相当する，図 2 の接尾辞配列の全範

れをコード 1 と呼ぶ）により，接尾辞トライの全ての囲においては，根の子供（につながる辺）として，深さ辺に対応する文字を，先行順走査に従って印刷できる．

1 の範囲 [1..3] に “A”, 範囲 [4..6] に “B”，範囲 [7..7] に“C”, 範囲 [8..8] に “D”, 範囲 [9..9] に “E” があることが分かる必要がある．もしそのような範囲が分かれば ，for(i:=1; i<=n; i++){for(k:=lcp[i]; S[i]+k<=n; k++){printf("%c", T[S[i]+k]);}}

その各々の範囲に対して，再帰的に探索をすることに

次に，コード 1 に，S や lcp などの値も出力させるようより，接尾辞トライの先行順の走査を模擬できるので，にして，かつ，コード 1 では出力されない文字を “*”

近似文字列照合ができる．

として出力させるようにすると，下記コード となる．

このような範囲を枚挙することは，接尾辞配列の左端（ 先頭）の方から順に 2 分探索することにより可能
である☆ ．まず，上記の例では，S[1] における深さ 1 の文字が “A” であるので，“A” の右端を 2 分探索すると，“A” は深さ 1 で範囲 [1..3] にある．次に，S[4] における
深さ 1 の文字は “B” であるので，“B” の右端を 2 分探索すると，“B” は深さ 1 で範囲 [4..6] にある．同様にして，“C” の範囲は [7..7]，“D” の範囲は [8..8]，“E”の範囲は [9..9] である．このようにして範囲を求めた
ら，後は，各範囲について，再帰的に，同様な手続きをすることにより，接尾辞配列により，接尾辞トライの先行順の走査を模擬できる．そのため，図 4 の検索
アルゴ リズムを利用して，接尾辞配列により近似文字
列照合をすることができる．

for(i:=1; i<=n; i++){printf("S[%d]=%d, lcp[%d]=%d: ",i, S[i],i,lcp[i]);for(k:=0; k<lcp[i]; k++){printf("* ");}
for(k:=lcp[i]; S[i]+k<=n; k++){printf("%c ", T[S[i]+k]);}printf("\n");}これを，図 2 に適用すると以下の結果が得られる．
S[1]=1, lcp[1]=0: A B C A B D A B E
S[2]=4, lcp[2]=2: * * D A B E
S[3]=7, lcp[3]=2: * * E
S[4]=2, lcp[4]=0: B C A B D A B E
S[5]=5, lcp[5]=1: * D A B E
S[6]=8, lcp[6]=1: * E
S[7]=3, lcp[7]=0: C A B D A B E
S[8]=6, lcp[8]=0: D A B E
S[9]=9, lcp[9]=0: E

この結果では，図 2 において下線となっている部分が4.2 lcp 配列を用いた接尾辞配列の先行順走査“*” となっている．つまり，図 2 において下線となっ

本節では，lcp 配列を用いて，接尾辞配列を先行順ている部分は，コード 1 では印刷されない部分である．

に走査する方法を提案し，次節で，それを利用して近つまり，その部分は，コード 1 では評価されていない．

似文字列照合をするアルゴ リズムを示す．

そして，その部分は，接尾辞トライにおいては，既に

まず，図 1 と図 2 とを比較することにより，lcp[i] が，先行順で通っている部分であるので，評価されないのが適切である．

☆

このような範囲を枚挙する方法の他のものとしては，まず，接尾辞配列の中央部分を範囲内に含むような子供（に対応する範囲）
を 2 分探索により探し，その後で，接尾辞配列を，その子供の前の範囲，その子供の範囲，その子供の後の範囲，というように3 分割し ，次に，その子供の前と後の範囲に対して，それぞれ，
再帰的に同様な探索をすることにより子供（に対応する範囲）全てを枚挙するというものがある 12) ．しかし，その方法によっても計算量は同じである．本稿では，左端から探索していく方法の方が実装が容易なため，左端から探索する方法を採用した．

コード 1 を ，図 2 の場合にトレ ースすると以下のようになる．まず，i=1 のときには，lcp[1]=0 であるので，T[S[1]+0]=T[1] から T[n]=T[9] まで，すな
わち，“ABCABDABE” が 内側のfor ループ で 印刷
され る ．次に ，i=2 の と きに は ，lcp[2]=2 で あ る
ので，T[S[2]+2]=T[6] から T[n]=T[9] まで，すなわ
ち，“DABE” が印刷される．また，i=3 のときには，

Vol. 0No. 0

近似文字列照合による全文検索のための接尾辞配列の高速走査法

main(){/* 初期化 */(図 4 の対応部分と同じ )/* 検索 */
for(i:=1; i<=n; i++){cut := false
for(k:=lcp[i]; S[i]+k<=n; k++){j := k + 1
if(cutp(T[S[i]+k], j)){cut := truebreak}
if (D[m,j]<=t) 検索成功}
if(cut){ /* 接尾辞のスキップ */while(lcp[i+1]>=j){i++}
}
}
}
図8

7

によりスキップすることは不利になる可能性がある☆ ．
しかし ，5章の実験で示すように，日本語の文字や英語の単語をアルファベットとするテキストにおいては，

while ループによりスキップされる数は小さいため，
線形探索によりスキップしても十分である．

3.4.2節での例と同じく，コスト 1 の距離について許容値を 1 として，図 2 のテキスト “ABCABDABE” について，パターン “DCA” を検索した場合について，図8 のアルゴ リズムの実行過程の概要を以下に示す．
まず，i=1 の場合には，内側のfor ループでは，パターンと接尾辞 “ABCABDABE” を比較していく．このときには，lcp[1]=0 であるので，k は 0 を初期値とlcp 配列を用いた近似文字列照合による全文検索のアルゴ リ
ズム．
Fig. 8 Full-text approximate string matching algorithm
using a lcp array.

ず，cutp("A",1) を計算する．この場合，距離行列

lcp[3]=2 なので，T[S[3]+2]=T[9] であるので，“E”

は，cutp("B",2) が計算される．そして，距離行列でのみが印刷される．以下，同様にして，コード 1 は，は，図 6 の 2 列目が得られる．この場合には，cutp は接尾辞トライを先行順に走査したのと同じ順番で，接true を返すので，内側のfor ループを抜け出す．この尾辞トライの各辺に対応付けられた文字を印刷する．

時点で，“AB” を先頭部分に持つ接尾辞は，パターン

4.3 lcp 配列を用いた近似文字列照合による全文検とは一致しないことが分かるので，そのような接尾する．また，T[S[1]+0]=T[1] は “A” であるので，までは，図 6 の 1 列目が得られる．次に，k=1 のときに索のアルゴリズム．

辞は，while ループにおいてスキップする．この場合lcp 配列を用いた検索アルゴ リズムは，基本的には，には，j=2 であり，かつ，lcp[2]=lcp[3]=2 であるの

コード 1 における印刷の部分を，近似文字列照合のたで，i=2,3 の場合について，それぞれの接尾辞 “ABD-

めの処理に置き換えたものである．図 8 には，そのア

ABE” と “ABE” とが，先頭部分 “AB” を共有するの

ルゴ リズムを示す．図 8 において明示されていない部

で，スキップする．

分（ cutp など ）は，図 4 のアルゴリズムと同じとする．

そのため，次に内側のfor ループを実行するときに図 8 における 2 重のfor ループの外側のループでは，は，i=4 である．これについては，パターンと接尾辞

接尾辞配列S の先頭から順番に全ての接尾辞について“BCABDABE” とを比較していくと，“BCA” についアクセスする．内側のループでは，k を，（ lcp[i] 未て検索が成功する（図 7 ）が，次に，“BCAB” におい満については距離行列の行の値は計算済みなので ），て，距離計算の打ち切りが起きる．

lcp[i] から順番に増やしながら，S[i] の深さk+1 の

次に ，i=5 に ついて ，内側のfor ル ープ を 実行す

文字T[S[i]+k] について，距離行列のk+1 列目（ j 列る．この場合には ，lcp[5]=1 であるので，k は 1 か目）を計算し，距離計算の打ち切りが可能ならば，ルーら始まる．そのため，既に i=4 のときに計算済みでプを抜け出す．距離計算が打ち切られたときには，距あ るcutp("B",1) に ついては 計算を することな く，

離計算が打ち切られた接尾辞と先頭部分を共有する接cutp("D",2) から計算することができる．

尾辞を while ループによりスキップする．while ルー

以下，同様にして実行していくと，コスト 1 の距離にプにおいて，j は，距離計算が打ち切られた接尾辞のついて許容値を 1 として，テキスト “ABCABDABE”

先頭部分の長さである．一方，lcp[i+1] は，現在距離について，パターン “DCA” を検索した場合には，“B-

計算が打ち切られた接尾辞と，それに（接尾辞配列上CA”，“CA”，“DA” が距離 1 で検索される．

で）後続する接尾辞との先頭部分の共通部分の長さで4.4 計 算 量

ある．そのため，もし，lcp[i+1]>=j であるなら，後パターンの長さを m，テキストの長さを n(À m)，

続する接尾辞は，現在距離計算が打ち切られた接尾辞

許容値を t としたとき，領域計算量，時間計算量，空の先頭部分を，その先頭部分に持つ．そのため，その間領域（ 索引の大きさ）は以下のようになる．

ような接尾辞について距離計算はしなくても良いためスキップする．なお，スキップされる接尾辞の数が非常に大きい場合には，（ while ループによる）線形探索☆

その場合には，線形探索以外の方法，例えば文献 9) の方法でスキップする接尾辞の右端を探索した方が良い．

8

1959

情報処理学会論文誌

4.4.1 領域計算量のではなく，その他にも，単語列の頻度などの統計量4.1節で述べた従来手法，および，4.3節で述べた提を得るのに役立つ 7),10),16) ．また，lcp 配列を利用する

案手法ともに，支配的な領域を占めるのは距離行列でことにより，厳密な一致による検索も高速にできる 9) ．

ある．図 4 におけるcutp をみると，1 ≤ i ≤ m であつまり，近似文字列照合という文脈以外からも lcp 配

り，1 ≤ j ≤ m + t + 1 である．ここで，j ≤ m + t + 1

列の有効性は確認されている．そのため，lcp 配列をである理由は，j = m + t + 1 のときには，パターンと索引として持つ意義はあると考える．

の距離が必ず t を越えるからである．そのため，距離行列の占める領域は O(m(m + t)) である．このオーダは，従来手法と提案手法で同じである．

4.4.2 時間計算量

5. 実

験

本章では，4章で述べた二つの走査法を用いた場合について，検索速度を比較する．

提案手法では，図 8 において，1 ≤ i ≤ n であり，

5.1 実 験 材 料

0 ≤ k ≤ m + t である．また，cutp では，1 ≤ i ≤ m

5.1.1 コ ー パ ス

である．よって，O(n(m + t)m) が最悪時の時間計算

検索対象のコーパス☆は，日本語と英語のコーパス量となる．一方，従来手法では，トライを辿る深さのが一つずつである．日本語のコーパスとしては，CD 毎

最大値が m + t + 1 であるので，訪問されるトライの日新聞 98,99 年度版を用い，英語のコーパスとしては，

ノード 数のオーダは O(|Σ|m+t ) である．また，各訪問

BNC（ British National Corpus ）を用いた☆☆ ．これされたノードで，cutp を呼ぶので，その時間計算量がらのコーパスからは，生のテキストに相当する部分のO(m) である．更に，子供のノードを 2 分探索するのにみを抽出し，記事番号などのメタ情報は除去した．

O(log n) かかる．よって，O(m|Σ|m+t log n) が最悪時

日本語コーパスの最小単位は文字とし，英語コーパの時間計算量となる．

スの最小単位は単語とした．このような単位を設定し平均時の時間計算量は 以下のよ うである．まず，た理由は，我々が近似文字列照合による全文検索をす探索され るト ラ イの ノード の平均の深さは O(t) でるときの主要な目的が類似用例の検索であり，そのた

あり，cutp の平均的な 時間計算量は O(t) であるの

めには，これらの単位が有効である 3),4) からである．

で，O(t|Σ|t ) が接尾辞トライを用いた場合の時間計

それぞれのコーパスは，まず，1 番目から 6 番目まで

算量である

13)

．したがって，従来手法の時間計算量はの部分コーパスに分割した．その分割の方法は，コーO(t|Σ|t log n) である．一方，提案手法においては，訪パスの i 番目の行が，i を 6 で割ったときの余り+1 番

問されるノード の数は従来手法と同じだが，ノード の目の部分コーパスに含まれるようにするというもの

探索（ 図 8 のwhile ループでの接尾辞のスキップ ）がである．そのあと，検索対象のコーパスとして，部生じるのは，距離計算の打ち切りが発生した場合のみ

分コーパス 1 からなるもの，部分コーパス 1 と 2 からである．打ち切りが起きるノード 数のオーダは O(|Σ|t )なるもの，. . . , 部分コーパス 1,2,3,4,5 からなるもの，であるので，スキップされる接尾辞数の平均を s とすという五つのコーパスを作った．これらのコーパスをると，スキップにより生じ る計算量は O(s|Σ|t ) であ

Size-1,Size-2,...,Size-5 と呼ぶことにする．なお，部分tる．この計算量が加算された O((t + s)|Σ| ) が全体のコーパス 6 は，パターンの抽出に利用した．

計算量となる．ここで，s については，もし線形探索

表 1 には，毎日新聞と BNC について，Size-1 からでなく，文献 9) の探索方法を使うと，O(log n + t) とSize-5 について，異なり単位数と延べ単位数を示す．

なるので，全体の計算量は O((t + log n)|Σ|t ) である．

なお，14.9M などの M は，10 の 6 乗のことである．

従来手法と提案手法の平均時の時間計算量を比べると，従来手法においては，ノード の探索のための計算量が乗算されるが，提案手法では，それが加算される．
そのため，提案手法の方が計算量が少なくて済む．

4.4.3 空 間 領 域
提案手法の空間領域は 2.4節で述べたように 12n バ
イトである．一方，従来手法では，lcp 配列を使わないので，8n バイトである．そのため，空間領域は検索速度とトレード オフの関係にあると言える．
ただし ，lcp 配列は，近似文字列照合だけに役立つ☆

これまでの説明では「テキスト」という言葉により検索対象を表現したが，本章では「コーパス」という言葉により検索対象を表現する．コーパスは，文字からなるという点で，テキストの一種であるので，そのまま本章でも「テキスト 」という言葉を使っても良いのだが，毎日新聞や British National Corpus など
は，著者らが主な研究領域としている自然言語処理においては「コーパス」と呼ばれるため「コーパス」という言葉を使う．
☆☆
BNC には，新聞や小説などの書き言葉からなるテキストが 90%あり，残りの 10%は話し言葉を書き起こしたテキストである．本
実験では，BNC の書き言葉の部分のみを用いている．

Vol. 0No. 09

近似文字列照合による全文検索のための接尾辞配列の高速走査法

Table 1表 1 異なり単位数と延べ単位数．
Number of different units (types) and the number of total units (tokens).

毎日新聞

異なり文字数
延べ文字数

BNC

異なり単語数
延べ単語数

Size-1
4,296
14.9 M
251,491
16.7M

Size-2
4,608
29.8M
362,443
33.5M

Size-3
4,783
44.8M
449,288
50.2M

160

パターンは部分コーパス 6 からランダムサンプリン

140

グした．このとき，毎日新聞については，6,12,18 の120

Av. of search time (CPU sec.)

5.1.2 パターンと距離関数

長さの文字列を，それぞれ 100 ずつ抽出し ，BNC に

Size-44,880
59.7M
523,408
66.9M

Size-5
4,965
74.6M
588,082
83.6M

binsearch-18-6

lcp-18-6

100

ついては，3,6,9 の長さの単語列を，それぞれ 100 ずつ抽出した．なお，これらの文字列や単語列としては，句読点等を含まないものを選んだ．

80
binsearch-18-4
60
lcp-18-440

距離としては，コスト 1 の距離を利用した．また，許20

容値としては，毎日新聞については，長さ 6 の文字列

0binsearch-18-2
lcp-18-20については 2，長さ 12 の文字列については 2 と 4，長さ 18 の文字列については 2,4,6 を試した．BNC につ

許容値

いては，長さ 3 の単語列については 1，長さ 6 の単語

長さ

列については 1 と 2，長さ 9 の単語列については 1,2,3
を試した．

1

2

3
Size (Mainichi)

4

2

5

4

6

6

6

12

18

12

18

18

binsearch

13.7

13.8

13.7

61.3

61.3

153

lcp

6.6

6.5

6.7

45.3

45.3

131

図9

5.1.3 プログラム
検索用のプログラムは C 言語で記述した．4.1節で説明した 2 分探索を利用する手法（ これを binsearch

毎日新聞での平均検索 CPU 時間（ 秒）（ Size-1〜5 のグラフと Size-5 における表）．
Fig. 9 Average search CPU time (seconds) on Mainichi(graphs of Size-1 to 5 and the table of Size-5).

法と呼ぶ）と 4.3節で説明した提案手法（これを lcp 法と呼ぶ）とを実装するにあたり，共有できるコードは5.2 実 験 結 果

共有し，二つの実装の違いは，接尾辞配列の走査法のまず，平均検索時間を比較する．次に，lcp 法にお違いだけになるように努めた．また，図 4 や図 8 のア

いて探索打ち切り時にスキップされる接尾辞の数を調

ルゴ リズムにおける「検索成功」の時点では，通常は，べる．

検索された文字列を印刷するなどの処理をするのだが，本実験では，検索時間を測定するのが目的であるので，

5.2.1 平均検索時間
図 9 と図 10 には，毎日新聞と BNC についての 1 パ
ターンあたりの平均検索 CPU 時間（秒）を示す．これ

この部分では何の処理もしていない．

5.1.4 計算機環境

らの図では，各線のパターンの性質を，“検索方法-パ実験に用いた計算機環境は以下の通りである．

ターンの長さ-許容値” のように示している．たとえば，

CPU Alpha 21264 （ クロック速度 750MHz ） x 2

binsearch-18-6 は，binsearch 法により，パターンの長

メモリ

2048MB

さが 18，許容値が 6 で検索した場合の平均検索時間で

OS Linux 2.2.14 （ Kondara MNU/Linux release
1.1 ）ある．また，これらの図では，Size-5 における検索時
間を表に示してある．これらの表において，binsearch

なお，本実験での検索時間は CPU 時間 により計測さや lcp の行にある数字は，それぞれ，binsearch 法や lcp

れている．

法における平均検索時間である．

☆

これらの図では，最長のパターン（図 9 では長さ 18，☆

一般に，CPU 時間は，ユーザプロセスにより消費された時間とシステム（ OS ）により消費された時間の和，つまり，

CPU 時間 = ユーザ CPU 時間 + システム CPU 時間のようになっているが，本実験で計測した CPU 時間は，ユーザ
CPU 時間のみである．つまり，本実験では，ユーザ CPU 時間のことを CPU 時間と言っている．

図 10 では長さ 9 ）についてしか平均検索時間のグラフを示していないが，その理由は，平均検索時間が，パターンの長さに関らず，ほとんど 変化しないからである．ただし ，
「ほとんど 変化しない」とは，それぞれのコーパスにおいて，検索法と許容値が同じで長さの10

情報処理学会論文誌

1959

さいときに，その差は，顕著である．たとえば，図 9120では，許容値が 2 のときには，lcp 法は binsearch 法のAv. of search time (CPU sec.)

100

約 2 倍の検索速度（ 1/2 の検索時間）である．なお，許容値が大きくなると，両者の検索速度の比は小さくな

80
binsearch-9-3
60

るが，検索時間の差は無視できない程の大きさである．

lcp-9-3

たとえば，図 9 の表では，binsearch 法と lcp 法の検索

binsearch-9-240

lcp-9-2

時間の差は，許容値 2,4,6 に対して，7, 16, 22 秒であり，図 10 の表では，許容値 1,2,3 に対して，検索時間

binsearch-9-1

20

lcp-9-1の差は，22, 34, 36 秒となっている．また，図 9 と図

0
0

1

2

3
Size (BNC)

4

5

1

許容値

2

6

3

10 のグラフから，コーパスの大きさが大きくなってい
くと，検索時間の差も大きくなっていくことが分かる．

3

6

9

6

9

9

これらより，lcp 法は，検索速度の向上に役立つと言binsearch

31.3

31.3

31.3

68.9

69.4

114

える．

lcp

9.2

9.1

9.2

35.3

35.6

78.3

長さ

図 10

（ Size-1〜5 のグラフとBNC での平均検索 CPU 時間（秒）Size-5 における表）．
Fig. 10 Average search CPU time (seconds) on BNC(graphs of Size-1 to 5 and the table of Size-5).

これらの検索速度差の絶対的な値は，コーディング
やコーパスにより変わると考えられるが，相対的な速度の順位，つまり，lcp 法の方が binsearch 法よりも速いということは，4.4節で述べた計算量の観点から言っても，コーディングやコーパスに影響されないのではみが違うパターンの組（たとえば，binsearch-18-6 とないかと考える☆ ．

binsearch-12-6 ）について，平均検索時間を t1 ,t2 とす

5.2.2 スキップされた接尾辞の数

ると，4.3節で述べたように，lcp 法において，図 8 におけ

検索時間の差の全体に= 100 ×占めるパーセンテージ|t1 − t2 |(t1 + t2 ) ∗ 0.5

るwhile ループによりスキップされる接尾辞の数が非常に大きいときには，線形探索によりスキップするのは不利である．しかし ，図 11 と図 12 に示すように，としたとき，このようなパターンの組全てに対して，

毎日新聞においても BNC においても，スキップされ検索時間の差の全体に占めるパーセンテージの平均をる接尾辞の数は小さいため，線形探索によりスキップ

求めると，それが，毎日新聞については 0.49%になり，しても問題ないと言える．

BNC については 1.08%になるということである．

なお，これら二つの図では，前節と同様に，最長のこのように，検索時間がパターンの長さに依存しなパターンについてしかスキップされた接尾辞数の平均

いということは，接尾辞トライにおいて訪問されるをグラフとして示していないが，その理由は，前節とノード の数がパターンの長さに依存しないということ同様に，スキップされた接尾辞数の平均がパターン長を示している（なぜなら検索時間は訪問したノード 数に依存しないからである．なぜ，依存しないかというに比例するから）．実際，3.3節で述べた距離計算の打と，スキップされた接尾辞数というのは，図 1 のようち切り法を利用した場合には，許容値 t に対して，探な接尾辞トライにおいて，先行順に探索したときに，索されるトライのノード の平均の深さは，O(t) であ探索が打ち切られたノードにおける子供の数（から 1

り，パターンの長さには依存しない

13)．そのため，訪を引いた数）に等しく，かつ，探索の打ち切りが起き問されるノード の数，したがって，検索時間も t のみる深さが，前節で述べたように，パターン長には依存に依存し，パターンの長さには依存しない．

しない（ 許容値のみに依存する）からである．

また，探索されるノードの平均の深さが O(t) である
ことから，検索時間は t に指数的に増加すると言える．
なぜなら，訪問されるノード の数は，一般に，ノードの深さに指数的に増加するからである．このことは，
図 9 と図 10 の中にあるそれぞれの表からも分かる．
最後に，lcp 法と binsearch 法の検索速度を比べると，lcp 法の方が速いこと（ lcp 法の方が検索時間が短かいこと）が図 9 と図 10 とから分かる．特に，許容値が小☆

ただし，lcp 法では，lcp 配列を索引に使用するため，その分だ
けのメモリが必要である．そのため，テキストに加えて，接尾辞配列と lcp 配列とをメモリ上に格納できるような計算機でなければ，lcp 法での速度向上はないのではないかと予想する．しかし，現在では，数 GB 程度のメモリをもつ計算機は普通のものとなってきているので，本稿では，メモリの大きさを変えて速度を比較するということはしなかった．

Vol. 0No. 0

近似文字列照合による全文検索のための接尾辞配列の高速走査法

法による距離計算法とを比べると，彼等の距離計算法

14はコスト 1 の距離に特化した方法であるので，コスト

lcp-18-2
12
Av. of the number of skipped suffixes

11

1 の距離に関しては，彼等の方法の方がずっと短時間

10で距離計算が可能である☆ ．しかし，自然言語処理に
8

おいて，用例間の距離を計算するためには，コスト 16の距離だけでなく，もっと一般的な距離を使う必要があると考える．そして，そのような場合でも，動的計

4
lcp-18-4

画法による距離計算は，適切な距離関数を定義するこ2
lcp-18-6とにより，柔軟に対処できる．そのため，動的計画法

0
0

1

2

3
Size (Mainichi)

4

5

2

許容値
長さ
平均スキップ数64

6

により距離計算をすることは有意義であると考える．

6.2 接尾辞配列の走査

6

12

18

12

18

18

接尾辞トライあるいは接尾辞木の後行順の走査を接

12.4

12.4

12.4

2.3

2.3

1.4

尾辞配列で（ lcp 配列を利用して ）高速に模擬する方図 11

毎日新聞でのスキップされた接尾辞数の平均（ Size-1〜5 のグラフと Size-5 における表）．
Fig. 11 Average of the number of skipped suffixes on
Mainichi (graphs of Size-1 to 5 and the table ofSize-5).

法は既に提案されている 8),16) ．ただし ，これらの研究においては，接尾辞配列と lcp 配列とを使う目的は，
単語列の頻度などの統計量を得るためである．それに対して，本稿では，先行順の走査を lcp 配列を利用して模擬する方法を新規に示すとともに，その方法が，近似文字列照合の高速化に有効であることを実証した．

8

なお，従来の接尾辞配列の走査法 8),16) と提案手法

lcp-9-1
7
Av. of the number of skipped suffixesとの主要な違いは，従来の走査法がスタックを利用し6て接尾辞配列を走査しているのに対して，提案手法は

5

スタックを利用していないことである．ここで，従来4の走査法を先行順に修正し，それを利用して近似文字列照合することも可能であると考えるが，我々が 4.2節

3
lcp-9-2で提案した走査法の方が，本質的な部分が（ 4.2節で2
lcp-9-3示した ）コード 1 という 2 重のfor ループで尽くされ

1
0

1

2

3
Size (BNC)46

ることからも分かるように，実装が容易である．

1

許容値

5

2

3

長さ

3

6

9

6

9

9

平均スキップ数

7.9

8.0

7.9

2.2

2.2

1.3

図 12

BNC でのスキップされた接尾辞数の平均（ Size-1〜5 のグ
ラフと Size-5 における表）．
Fig. 12 Average of the number of skipped suffixes on BNC(graphs of Size-1 to 5 and the table of Size-5).

7. お わ り に
本稿では，近似文字列照合による全文検索のための索引としての接尾辞配列を高速に走査する方法を提案
するとともに，その有効性を実験により示した．
提案手法は，高速化のために補助的な配列を利用しているが，その配列は，近似文字列照合による全文検6. 関 連 研 究
6.1 近似文字列照合による全文検索

索だけでなく，その他にも，単語列の頻度などの統計量を得るのに役立つものである．したがって，提案手法は，その配列の別の有効性を示したとも言える．

文献 12) では，文字列間の距離を計算するときに，電子化されたテキストが大量に蓄積されている現在，

本稿 3.2節で説明した動的計画法とは異なる方法を用

自然言語処理が対象とするテキストも大規模になっていている．しかし，彼等も，テキストからパターンをいる．また，自然言語処理だけでなく，言語学，ある

検索するときには，テキストの接尾辞配列を（ 2 分探いは，外国語学習などにおいても，そのような大規模

索により）先行順に走査している．そのため，彼等のなテキストにおける言語現象を観察することによる利距離計算法と，本稿 4.2節で説明した接尾辞配列の走査法とを組合せることは可能である．
なお，彼等の距離計算法と，本稿で述べた動的計画☆

その他にも，コスト 1 の距離については，高速な距離計算法がある 11) ．

12

1959

情報処理学会論文誌

益は大きいと考える．
そのような大規模テキストを取り扱うためには，そのための適切なツールが必要である．我々は，そのためのツールを継続的に開発中であり，提案手法も，その一つに組込まれている．我々は，そのようなツールの有効性を，今後，定量的に調べたいと考えている．

参 考 文 献1) Baeza-Yates, R. and Gonnet, G.: All-AgainstAll Sequence Matching, Technical report, Department of Computer Science, University ofChile (1990).
2) Baeza-Yates, R. and Gonnet, G.: A Fast Algorithm on Average for All-Against-All Sequence Matching, Proc. of the 6th Symposiumon String Processing and Information Retrieval(SPIRE’99), pp. 16–23 (1999).
3) Baldwin, T.: Low-cost, High-performance
Translation Retrieval: Dumber is Better, Proc.
of the 39th Annual Meeting and 10th Conference of the Europena Chapter of the Association for Computational Linguistics (ACLEACL’2001), pp. 18–25 (2001).
4) Baldwin, T. and Tanaka, H.: The Effects ofWord Order and Segmentation on Translation
Retrieval Performance, Proc. of the 18th International Conference on Computational Linguistics (COLING’2000), pp. 35–41 (2000).
5) Cobbs, A.: Fast Approximate Matching using
Suffix Trees, Proc. of the 6th Annual Symposium on Combinatorial Pattern Matching (CPM’95), pp. 41–54 (1995).
6) Gusfield, D.: Algorithms on Strings, Trees,
and Sequences, Cambridge University Press(1997).
7) Ikehara, S., Shirai, S. and Uchino, H.: A Statistical Method for Extracting Uninterrupted
and Interrupted Collocations form Very Large
Corpora, Proc. of the 16th International Conference on Computational Linguistics (COLING’96), pp. 574–579 (1996).
8) 笠井透, 有村博紀, 有川節夫: 部分語計数問題の接尾辞配列を用いた高速アルゴ リズム, 1999 年冬のLA シンポジウム (1999). http://www.i.kyushuu.ac.jp/~arim/jtalks.shtml.
9) Manber, U. and Myers, G.: Suffix Arrays: A
new method for on-line string searches, SIAM
Journal on Computing, Vol. 22, No. 5, pp. 935–
948 (1993).
10) Nagao, M. and Mori, S.: A New Method ofN-gram Statistics for Large Number of n andAutomatic Extraction of Words and Phrases
from Large Text Data of Japanese, Proc. of

the 15th International Conference on Computational Linguistics (COLING’94), pp.611–615(1994).
11) Navarro, G.: A Guided Tour to Approximate
String Matching, ACM Computing Surveys,
Vol. 33, No. 1, pp. 31–88 (2001).
12) Navarro, G. and Baeza-Yates, R.: A Hybrid Indexing Method for Approximate String
Matching, Journal of Discrete Algorithms, Vol.
1, No. 1, pp. 205–239 (2000).
13) Shang, H. and Merrettal, T. H.: Tries for Approximate String Matching, IEE Transactions
on Knowledge and Data Engineering, Vol. 8,
No. 4, pp. 540–547 (1996).
14) Ukkonen, E.: Finding Approxmate Patternsin Strings, Journal of Algorithms, Vol. 6, pp.
132–137 (1985).
15) Ukkonen, E.: Approximate String-Matchingover Suffix Trees, Proc. of the 4th Annual
Symposium on Combinatorial Pattern Matching (CPM’93), pp. 228–242 (1993).
16) Yamamoto, M. and Church, K. W.: Using Suffix Arrays to Compute Term Frequency andDocument Frequency for All Substrings in a
Corpus, Computational Linguistics, Vol. 27,
No. 1, pp. 1–30 (2001).
17) 長尾真, 石田晴久, 稲垣康善, 田中英彦, 辻井潤
一, 所真理雄, 中田育男, 米澤明憲 (編): 岩波情報
科学辞典, 岩波書店 (1990).
(平成 0 年 0 月 0 日受付)
(平成 0 年 0 月 0 日採録)
（ 担当編集委員 通信 太郎）
内山 将夫（ 正会員）

1992 年筑波大学第三学群情報学類
卒業．1997 年筑波大学大学院工学研究科博士課程修了. 博士（ 工学）．

1997 年信州大学工学部電気電子工学科助手．1999 年郵政省通信総合研究所非常勤職員．2001 年独立行政法人通信総合研究所任期付き研究員．言語処理学会，情報処理学会，ACL，
人工知能学会，日本音響学会，各会員．

Vol. 0No. 0

近似文字列照合による全文検索のための接尾辞配列の高速走査法

井佐原 均（ 正会員）

1978 年京都大学工学部電気工学第二学科卒業．1980 年同大学院修士課
程修了．博士（工学）．1980 年通商産業省電子技術総合研究所入所．1995
年郵政省通信総合研究所．現在，独立行政法人通信総合研究所けいはんな情報通信融合
研究センター自然言語グループリーダー．言語処理学会，情報処理学会，人工知能学会，日本認知科学会，
各会員．

13