論文

DBSJ

近似文字列照合のための効率的なアルゴリズム

1aa位置
テキストパターン

An Efficient Algorithm for String
Matching with Mismatches

中藤 哲也

†

馬場 謙介

Tetsuya NAKATOH‡

Kensuke BABA

文字列中に存在する特定のパターンを見つけ出す問題は，文字列照合問題と呼ばれ，Web 上の情報からの検索や DNA 配列の特定パターンの検索に用いられるなど，幅広い応用範囲を持つ．
近似文字列照合問題の一種である不一致を許す文字列照合問題
は，単なる文字列照合問題より応用範囲が広く，また難易度も高い．我々は，高速フーリエ変換 (FFT) を利用してこの問題の解を高速に計算する効率的なアルゴリズムを提案する．本アルゴリズムは，k 個のサンプルを用いた確率アルゴリズムで，計算量は O(kn log m) である．この k は 1 ≤ k ≤ |Σ| の範囲を持ち，k = |Σ| においては常に正しいスコアが得られる．すなわち，精度と計算量の兼ね合いを自由に選ぶ事が可能である．

The problem to find out a pattern from the string iscalled String matching problem. That has a wide application range, such as text search, search form thedatabase and an information extraction from Web.
Specially, String matching with mismatches problem
is more difficult problem than String matching problem. We propose a new efficient algorithm to solve
String matching with mismatches problem fast by
utilizing fast Fourier transformation (FFT). That is
a randomized algorithm, and its time complexity isO(kn log m), where k is the number of randomly sampled estimations and its value is in the range of 1
to |Σ|. We can compute an exact score vector withk = |Σ|. We can choose a balance of time complexityand precision freely.

1. はじめに
文字列照合問題は，T = t1 · · · tn と P = p1 · · · pm をそれぞれテキストとパターンと呼ばれるアルファベット Σ 上の文字列とする時，テキスト T に現れるパターン P の出現位置を全て見つける問題である．この問題の解は O(n) で得られる事が知られている．これに対し，パターン P を編集したものをテキスト T 中に見つける問題を近似文字列照合問題と言い，単なる文字列照合問題より難易度は高い．編集の種類としては，代入や挿入，削除なとがあり，その違いは編集距離として定義される．
これらと関連する問題として，編集に代入のみを許した不一致を許す文字列照合問題があり，その距離はハミング距離として定義される．パターン長とハミング距離の差がマッチングのスコアとなる．スコアはテキスト T 上の全ての位置で得られるので，この問題はテキスト T 上の全ての位置におけるパターン P とのマッチングのスコアのベクトル C(T, P ) = (c1 , . . . , cn−m+1 ) を† 正会員 九州大学情報基盤センター

nakatoh@cc.kyushu-u.ac.jp
baba@i.kyushu-u.ac.jp‡ 科学技術振興事業団

1

スコアベクトル

32cba3bbba

1

14aabba55bcabba2

Le t t e r s

V o l . 2,No . 1

6b7a8c9c10bcabba0cabbcabcac

図 1: テキスト acbabbaccb とパターン abbac の間のスコアベクトル求める問題とみなす事ができる．ここで各 ci は，T の部分文字列 ti · · · ti+m−1 と P の間のシンボルの一致の数であり，ci = mは，テキスト中の i 番目の位置にパターンそのものが現れている場合である．
図 1 はスコアベクトルの例である．このスコアベクトルを求めるには，例えば単純にシンボルの比較を m 回ずつ n − m +1 個の i について行なえば良く，この素朴なアルゴリズムの計算量はO(mn) であることが容易に分かる．この問題に関しては，これまでに多くの研究が行なわれている [5][7]．Fischer ら [6] は，文字列の比較に畳み込みが使えることを見いだした．その原理に基づき高速フーリエ変換 (FFT) を用いた計算量 O(|Σ|n log m)のアルゴリズム [7] が示されている．また，Abrahamson [1]√は，一般化された文字列照合を O(n m log m) で得るアルゴリズムを示した．ハミング距離の近似を得る方法としては，
Karloff [8] が O( ²n2 logc m) のアルゴリズムを示している．c は定数項，² は近似の良さを表している．不一致数を k に制限した k-mismatch 問題にもさまざまな解決が図られており，Amir√3
ら [3] は O(n k log k) と O((n + nkm ) log k) の二つのアルゴリズムを示した．近年，Atallar らはスコアベクトルを求めるためのモンテカルロ型確率アルゴリズムを提案した [2]．これは，スコアベクトルをテキストとパターンに対応する二つの写像関数の畳み込みで表し，FFT を利用して計算する方法である．この時，正確な値を求めるために必要となる非常に多くの写像についてその全てを計算する代わりに，ランダムに選んだ k 個の写像標本の平均によってスコアベクトルの推定を確率的に行なう事で，計算量を O(kn log m) に抑えている．また，馬場ら [4] はAtallar らと同様の手法において写像数をより少なくする写像の改良を行なっている．
本研究では，馬場ら [4] と同様の手法において，写像の数を大きく削減する手法を示す．計算量は k 個の標本について同じくO(kn log m) であるが，標本の元となる総写像空間は充分に小さく 1 ≤ k ≤ |Σ| である．k = |Σ| とする事で決定性アルゴリズムとして扱うことも可能である．k の取り方で計算量と精度を自由にコントロールできるので，入力の状況に応じた処理が可能である．

2. 準備
Σ を有限のアルファベットとし，Σ∗ の要素を文字列と呼ぶ．
文字列 w の長さを |w| で表す．また集合 S の要素数を |S| によって表す．
シンボルの一致を表す関数 δ:Σ × Σ → {0, 1} を次式のように定義する．

½
δ(a, b) =10（a = b のとき）
（a 6= b のとき）

但し，a, b ∈ Σ である．

日本データベース学会 Le t t e r s Vol . 2,No. 1

論文

DBSJ

テキスト T = t1 t2 · · · tn ∈ Σ∗ とパターン P = p1 p2 · · · pm ∈Σ について，∗

ci =mXδ(ti+j−1 , pj )(1 ≤ i ≤ n − m + 1)

(1)

j=1として得られるベクトル C(T, P ) = (c1 , c2 , . . . , cn−m+1 ) を Tと P の間のスコアベクトルと呼ぶ．つまり，ci は P の先頭のシンボルが T の i 番目の位置にあるときの一致の数である．

3. FFT を使うための条件

Pm
ci は式（1）の定義より j=1 δ(ti+j−1 , pj ) である．この δ 関数を何らかの方法で，t の関数と p の関数の積へ変換することができれば，ベクトル C(T, P ) の計算は，T と P の畳み込み(convolution) に変換可能である．畳み込みで表現されたベクトル C(T, P ) は高速フーリエ変換 (FFT) によって，O(n log n) で計算できる．
更に，計算量を O(n log m) に落とすために，[2] と同様に [5]の技法を用いる事ができる．テキスト T を重なった部分を持つ
長さ (1 + α)m ずつの塊に分割し，そのそれぞれについて別々に操作を行なう．ひとつの塊についての操作によって，C の成分のうち αm 個が求められる．塊の数は n/(αm) であり，それぞれの塊は FFT によって O((1 + α)m log((1 + α)m)) で計算nされるので，α = O(m) ととると全体の計算量は， αmO((1 +α)m log((1 + α)m)) = O( (1+α)α n log((1 + α)m)) = O(n log m)である．
シンボルの一致を表す δ 関数を，t の関数と p の関数の積で直接表現する方法は無い．次に紹介する Atallar らの方法 [2]，馬場らの方法 [4]，本稿で提案する方法はいずれも，アルファベッ
トの集合をまず複数の写像に変換し，各写像に対する結果の総和が δ 関数と一致するような関数を導入して，δ 関数を間接的に表現している．

アルファベット Σ を |Σ| 乗根からなる複素数空間に写像し，ある写像の複素数とその共役複素数との積を用いることで，シンボルが一致する場合の δ 関数を 1 にしている．しかし，この方法によって不一致の場合に 0 を得るためには，複素平面の単位円上に均一に散らばるように複数の写像を設定し，その積の総和を計算する必要がある．これには個々のシンボルの |Σ| 乗根からなる複素数空間への全ての写像の総和が必要であり，その写像総数は |Σ||Σ| にのぼる．この計算量は現実的でない．そのため，Atallar らは |Σ||Σ| 個の写像集合からランダムに k 個の写像を取り出して計算を行なう事で，近似的に δ 関数を実現している．
計算量は O(kn log m) であり，期待値はスコアベクトル C に等しく，分散は (m − ci )2 /k に押さえられる事が示されている．

4.2 馬場らの方法 [4]Atallar らの方法を改良し，アルファベット Σ を {−1, 1} に写像する．シンボルが一致する場合の積は，そのシンボルが{−1, 1} どちらに写像されていても 1 である．不一致の場合は，積が {−1, 1} の両方に均等に散らばるように複数の写像を行なうことで，その総和を 0 としている．必要な全写像の数は 2|Σ|であり，Atallar らによる写像集合より小さい．しかしながら，
2|Σ| 個の全ての写像に関して FFT を計算する事は困難である．
計算量，期待値，分散とも，Atallar らの方法と同じである事が示されている．

2V o l . 2,No . 1

5. 効率的なアルゴリズム
本節では，我々の提案する新しい効率的なアルゴリズムについて示す．始めに準備として，|Σ| 個の写像を用いた決定性アルゴリズムについて説明した上で，k 個のサンプルを用いる確率アルゴリズムへと発展させる．

5.1 決定性アルゴリズム
アルファベット Σ のある一つのシンボルのみを 1 とし，その他のシンボルを −1 とする {1, −1} への写像の集合を ΨΣ とする．このとき，明らかに |ΨΣ | = |Σ| である．文脈から明らかな場合，ΨΣ を Ψ と略記する．
あるシンボル x ∈ Σ を 1 に変換する写像 ψx ∈ Ψ は次式のように定義される．

½
ψx (a) =1−1a = x のとき
a 6= x のとき

このとき，次の補題が得られる．
補題 1 二つのシンボル a, b ∈ Σ について，それらの一致を表す
δ 関数は，次式で表される．

δ(a, b) =|Σ|1 X
ψx (a)ψx (b) −+144ψx ∈Ψ

証明 1 写像の積 ψx (a)ψx (b) から得られる値を，a = b である場合と a 6= b である場合に分けて考える．
I）a = b の場合½

ψx (a)ψx (b) = 1 · 1 = 1
ψx (a)ψx (b) = −1 · −1 = 1x = a = b のとき
x 6= a = b のとき

すなわち，a = b の場合は ψx に関わらずその積は 1 となる．
よって a = b の場合の写像の合計 Fa=b は，X

Fa=b =4. 従来の確率アルゴリズム
4.1 Atallar らの方法 [2]Le t t e r s

ψx (a)ψx (b) =ψx ∈ΨX

1 = |Ψ| = |Σ|(2)ψx ∈ΨII）a 6= b の場合
x = a である場合，x = b である場合，x 6= a でかつ x 6= b である場合の３通りに分類でき，写像の積の合計 Fa6=b は，これらの和である．

Fa6=b =Xψx (a)ψx (b)ψx ∈Ψ= ψa (a)ψa (b) + ψb (a)ψb (b) +X= 1 · (−1) + (−1) · 1 +X

ψx (a)ψx (b)ψx ∈Ψ
x6=a,x6=b(−1) · (−1)ψx ∈Ψx6=a,x6=b|Ψ|−2= (−1) + (−1) +X1= |Ψ| − 4= |Σ| − 4(3)

ここで，δ 関数は，Fa=b を 1 に，Fa6=b を 0 に変換する事で得られる．そのような線形変換 δ(a, b) = αF + β を求める．
連立一次方程式½αFa=b + β = 1
αFa6=b + β = 0を解くと，次式が得られる．

日本データベース学会 Le t t e r s Vol . 2,

No. 1

論文

DBSJ

14 − |Σ|
F+441 X
4 − |Σ|ψx (a)ψx (b) +=44

δ(a, b) =(4)ψx ∈Ψこの δ 関数により，スコア ci に関して次の補題が得られる．
補題 2 1 ≤ i ≤ n − m + 1 である，あらゆる i について，mci =m|Σ|1 XX
ψx (ti+j−1 )ψx (pj ) −+m4
4
j=1

X2 =

δ(ti+j−1 , pj )¶j=1の計算を |Σ| 回行ない，線形変換を行なうことで計算できる事が分かる．よって，次の定理を得る．

X1

ψa と ψb の両方が Ψk に含まれる確率 p2 は，
p2 =

2 C2 · (|Σ|−2) C(k−2)|Σ| Ckψx ∈Ψk= ψa (a)ψa (b) +5.2 確率アルゴリズム= 1 · (−1) +補題 3 二つのシンボル a, b ∈ Σ について，それらの一致を表す
δ 関数は，写像 ΨΣ から k 個を取り出して作った部分集合 Ψk を用いて次の期待値で表される．

4 − |Σ||Σ| X
ψx (a)ψx (b) +δk (a, b) =4k4
ψx ∈Ψk証明 3 ２つの写像の積 Ψx (a) · Ψx (b) の合計の期待値 E を，a = b の場合と a 6= b の場合に分けて求める．
I）a = b の場合
期待値 Ea=b は，Xψx ∈Ψk3

ψx (a)ψx (b) =X

1 = |Ψk | = k=k(k − 1)|Σ|(|Σ| − 1)II-b）ψa と ψb のどちらか一方が Ψk に含まれる場合含まれる一方の写像を仮に ψa とすると，写像の積の合計値
X1 は，
X
X1 =ψx (a)ψx (b)定理 1 スコアベクトル C(T, P ) は O(|Σ|n log m) で正確に計算できる．

前節のアルゴリズムは効率的ではあるが，それでもなお，アルファベットサイズ |Σ| と同じ回数の FFT 計算が必要であるので確率化を試みる．
写像集合 ΨΣ より，一様に無作為に k 個を取り出した部分集合 Ψk について考える．|Ψk | = k である．この部分集合 Ψk についての δ 関数が求まれば，前節の決定性アルゴリズムから確率アルゴリズムが得られる．

(−1) · (−1)= |Ψk | − 4=k−4

スコアベクトル C(T, P ) は，［補題 2］より，

ψx (ti+j−1 )ψx (pj )ψx (a)ψx (b)ψx ∈Ψkx6=a,x6=b|Ψk |−2= (−2) +ψx ∈Ψ

Ea=b =Xψx ∈Ψkx6=a,x6=bψx ∈Ψm

1 X X
m(4 − |Σ|)=
ψx (a)ψx (b) +.
44j=1mX

X= 1 · (−1) + (−1) · 1 +j=1m µXNo . 1

ψx (a)ψx (b)= ψa (a)ψa (b) + ψb (a)ψb (b) +4 − |Σ|1 X
ψx (a)ψx (b) +44
j=1
ψx ∈Ψµ¶mm
X 4 − |Σ|X 1 X
ψx (a)ψx (b) +
=
4
4
j=1
j=1=X
ψx ∈Ψk証明 2 式（1）に式（4）を代入すると，ci =V o l . 2,である．これは，k = |Σ| において，式（2）と一致する．
II）a 6= b の場合
ψa と ψb が Ψk に含まれるかどうかによって，２つの写像の積の値は異なるので，それぞれの場合における写像の積の合計値
Xi とその確率 pi ∗ を求め，期待値 E を計算する．
また各 Xi について，x = a である場合，x = b である場合，x 6= a でかつ x 6= b である場合の 3 通りに分類できるのは，前節と同様である．
II-a）ψa ∈ Ψk でかつ ψb ∈ Ψk の場合
写像の積の合計値 X2 は，x∈ΨmXLe t t e r sX

ψx (a)ψx (b)ψx ∈Ψk ,x6=aX(−1) · (−1)ψx ∈Ψk ,x6=a|Ψk |−1= (−1) +X

1= |Ψk | − 2=k−2
確率 p1 は，ψa ∈ Ψk と ψb ∈ Ψk の両方の場合があるので，

p1 =1 C1 · (|Σ|−2) C(k−1)|Σ| Ck×2=2k(|Σ| − k)|Σ|(|Σ| − 1)II-c）ψa ∈/ Ψk でかつ ψb ∈/ Ψk である場合
写像の積の合計値 X0 は，X
ψx (a)ψx (b)X0 =ψx ∈Ψk∗n 個の集合に m 個の特別な要素が入っているとする．そこから無作為にk の要素を取り出すとすると，m 個の要素のうち，x 個がそれに含まれる
確率は，次の式で求められる．

px =m Cx · (n−m) C(k−x)
n Ck

ψx ∈Ψk日本データベース学会 Le t t e r s Vol . 2,No. 1

論文

DBSJ

X=mX

|Ψk |

=1|Σ| Ck

定理 2 スコアベクトル C(T, P ) は k 個のサンプルを用いて確率的に計算できる．得られた値の期待値は正しい値と一致する．
計算量は，O(kn log m) である．

=(|Σ| − k)(|Σ| − k − 1)|Σ|(|Σ| − 1)

以上より期待値 Ea6=b は，Ea6=b =X

6. まとめXi · pi不一致を許す文字列照合のための効率的なアルゴリズムを与えた．Atallar ら [2] や馬場ら [4] によるアルゴリズムと同様，FFT による畳み込みを用いるものであるが，本アルゴリズムは少ない写像をベースとした確率アルゴリズムであり，正確なスコアを求める決定性アルゴリズムとしての動作を含め，精度と計算量を自由に設定できる．計算量は O(kn log m)(1 ≤ k ≤ |Σ|) である．

i= X2 · p2 + X1 · p1 + X0 · p0
k(k − 1)2k(|Σ| − k)= (k − 4) ·+ (k − 2) ·|Σ|(|Σ| − 1)|Σ|(|Σ| − 1)(|Σ| − k)(|Σ| − k − 1)
+k ·|Σ|(|Σ| − 1)k(|Σ| − 4)
=|Σ|

［謝辞］
本研究に対して議論に参加して頂き，多くのアドバイスを頂き

これは，k = |Σ| において式（3）と一致する事が分かる．
以上により，k 個のサンプルによる写像の積の合計値として，次の期待値 E を得た．

½

E=kk(|Σ|−4)|Σ|

αEa=b + β = 1
αEa6=b + β = 0

この連立一次方程式を解く事により，次式が得られる．

|Σ|4 − |Σ|E+4k4|Σ| X
4 − |Σ|=ψx (a)ψx (b) +4k4

δk (a, b) =(5)ψx ∈Ψk

この式は k = |Σ| において，式（4）と一致する事が分かる．
得られた δ 関数により，スコア ci に関して次の補題が得られる．
補題 4 1 ≤ i ≤ n − m + 1 である，あらゆる i について，ci =mm(4 − |Σ|)|Σ| X Xψx (ti+j−1 )ψx (pj ) +4k
4j=1
ψx ∈Ψk

証明 4 式（1）に式（5）を代入すると，

ci ==mXδk (ti+j−1 , pj )
j=1
m µ
XX
j=1

=

4

ψx (ti+j−1 )ψx (pj ) +ψx ∈Ψm µX|Σ| X
j=1

=|Σ|
4k|Σ|
4k4k

ψx ∈Ψ
mX X

¶¶ X
m
4 − |Σ|ψx (ti+j−1 )ψx (pj ) +4
j=1

ψx (ti+j−1 )ψx (pj ) +ψx ∈Ψ j=1

4 − |Σ|4ました九州大学情報基盤センターの廣川佐千男教授，池田大輔講師，システム情報学府の山田泰寛君に感謝致します．

［文献］

a = b のとき
a 6= b のとき

前節と同様に，δ 関数を得るため線形変換 δ(a, b) = αE + β を求める．

½

ψx (ti+j−1 )ψx (pj )の計算を k 回行ない，一度の線形変換を行なうことで確率的に求まる．
よって，次の定理を得る．

ψa と ψb の両方が，Ψk に含まれない確率 p0 は，
2 C0 · (|Σ|−2) Ck

No . 1j=1= |Ψk |=kp0 =V o l . 2,

スコアベクトル C(T, P ) は，
［補題 4］より，(−1) · (−1)ψx ∈Ψk ,x6=a,x6=bX

Le t t e r sm(4 − |Σ|).
4[1] Abrahamson, K.: Generalized string matching.
SIAM Journal on Computing 16, 6, 1039-1051. 1987.
[2] Atallah, M. J., Chyzak, F., and Dumas, P.: A Randomized Algorithm for Approximate String Matching. Algorithmica 29, 468-486. 2001.
[3] Amir, A., Lewenstein, M. and Porat, E.: Faster algorithms
for string matching with k mismatches. Symposium onDiscrete Algorithms, pp.794-803, 2000.
[4] Baba, K., Shinohara, A., Takeda, M., Inenaga, S., andArikawa, S.: A Note on Randomized Algorithm for String
Matching with Mismatches. Proceedings of the Prague
Stringology Conference ’02, 9–17, 2002.
[5] Crochemore, M. and Rytter, W.: Text Algorithms. Oxford
University Press, New York. 1994.
[6] Fischer, M. J. and Paterson, M. S.: String-matching andother products. In Complexity of Computation (Proceedings of the SIAM-AMS Applied Mathematics Symposium,
New York, 1973), 113-125. 1974.
[7] Gusfield, D.: Algorithms on Strings, Trees, and Sequences.
Cambridge University Press, New York. 1997.
[8] Karloff, H.: Fast algorithms for approximately counting
mismatches. Information Processing Letters 48, 2, 53-60.
1993.

中藤 哲也

Tetsuya NAKATOH

九州大学情報基盤センター助手．1992 九州大学総合理工学研究科修士課程修了．Web マイニング・文字列処理の研究に従事．
日本データベース学会正会員．情報処理学会正会員.

馬場 謙介

Kensuke BABA

科学技術振興事業団グループメンバー. 2002 九州大学大学院システム情報科学研究科博士課程修了．文字列処理の研究に従事.
情報処理学会正会員.

日本データベース学会 Le t t e r s Vol . 2,

No. 1