Web教材一覧>
アルゴリズム
(BOK大区分:1 基礎理論、中区分:2 アルゴリズムとプログラミング、中区分:2 アルゴリズム)
キーワードによる全文検索など、テキストtの文字列のなかに、パターンpと同じ文字列が存在するかどうかを調べて、存在したらその位置を知らせるといった処理は、多様な場面で必要になります。
そのため、多くのプログラミング言語では、文字列探索の機能を標準関数として提供していますが、ここでは、それを自作することをとおして、アルゴリズムを習得することを目的にします。
文字列探索の基本的方法として単純比較法と力任せ法、高速探索の代表的な方法として、KMP法とBM法を取り上げます。
なお、文字列探索では「正規表現」が重要なのですが、かなり高度になるので、ここでは対象外とします。
アルゴリズム、文字列の検索、KMP法、BM法
文字列検索とは、テキストの文字列内に、パターンの文字列と一致する部分文字列が存在するかどうかを調べ、存在したならば、その位置を求めるという操作です。例えば、
テキストの文字列が「dabdabcabcba」
パターンの文字列が「abcb」
の場合
11
012345678901
テキスト: dabdabcabcba
パターン: abcb
となるので7を戻し、パターンが「abcx」の場合は、テキストに一致する部分文字列が存在しないので、-1を戻す関数を考えます。
以下、テキストは配列t、パターンは配列pに入っており、テキストの文字列長さをn、パターンの文字列長さをmとします。上の例では、
t[0]="d", t[1]="a", … , t[11]="a" n=12
p[0]="a", p[1]="b", … , p[3]="b" m=4
となります。(t、pは0から始まり、n、mは個数であることに注意)
なお、プログラムでは、これらの値はグローバル変数として定義されているものとします。
単純比較法は、テキストとパターンを1文字ずつ比較していく方法です。わかりやすいのですが、最悪の場合、m×n回の比較を行う(計算量オーダーが O(n×m) になる)ため、非効率な方法です。
ア function simple() {
イ var i, j;
ウ for (i=0; i<=n-m; i++) {
エ for (j= 0; j<m; j++) {
オ if (t[i+j] != p[j]) break;
カ }
キ if (j == m) return i;
ク }
ケ return -1;
コ }
t[i]以降とpが一致しているかを調べるには、pのj番目の文字p[j]とt[i+j]を比較することが基本になります(オでの比較)。
下表では、i=3、j=2(i+j=5)のとき、t[5]=bとp[2]=cを比較しています。
i i+j n-m n
↓ ↓ ↓ ↓
0123456789101112
t: dabdabcabcba
p: abcb
↑
j
一致していないならば、それ以上この位置で比較する必要はないので、p全体を右に一つ移動させ(iに1を加えて)pの先頭から(j=0として)比較します(オのbreak)。
一致していれば(図では一致していないが)、jに1を加えて、t[6]=cとp[3]=bと比較します。
キで j=m のときに打ち切っているのは、パターンのすべての文字が一致したときは、j=m-1であり、それがj=mになったときにエ~カのループから出てキへ行くからです。
ウで i≦n-m(12-4=8)としたのは、i=9になると、pが最期までいったとき(j=3になったとき)に、i+j=12となり、オで t[i+j] がtの配列上限を超えてしまう(オーバーフローする)からです。
i j i+j 0123456789011
dabdabcabcba
0 0 0 abcb 赤字は不一致を示す→iに1を加えjを0にする
1 0 1 abcb 青字は一致を示す→jに1を加える
1 1 2 bacb
1 1 3 abcb
2 0 2 abcb
3 0 3 abcb
4 0 4 abcb
4 1 5 abcb
4 2 6 abcb
4 3 7 abcb
5 0 5 abcb
5 1 6 abcb
7 0 7 abcb
7 1 8 abcb
7 2 9 abcb
7 3 10 abc すべて一致
└ 一致位置(戻す値)
この方法も単純比較法と同じように1文字ずつ比較する方法で、計算量もほぼ同じですが、「力任せ法」と名前がついているように、よく知られたアルゴリズムです。以降のKMP法やBM法と構造が似ているので、これを理解しておくと、それらの方法の理解に役立ちます。
ア function bf() {
イ var i, j;
ウ i = 0;
エ j = 0;
オ while (i <= n-m) {
カ while ( (i < n) && (j < m) ) {
キ if (t[i] == p[j]) {
ク i++;
ケ j++;
コ }
サ else {
シ i = i - j + 1;
ス j = 0;
セ }
ソ }
タ if (j == m) return i-j;
チ }
ツ return -1;
テ }
単純比較法では、p[j]とt[i+j]とを比較していました。すなわち、iは配列tのi番目という意味で用いていました。それに対して力任せ法では、キからわかるように、iは、比較を行う位置を示しています。
一致したとき(キ~コ):次の文字の比較をするために、iとjに1を加えます。
不一致のとき(サ~セ):j=0とするのは、単純比較法と同じです。シで、i=i-j+1としているのは次の理由です。
下図の「現在」において、i=7、j=3のときに、t[i]=a、p[j]=cで不一致になりました。「現在」でのpの先頭位置は4(=i-j)にあるので、「次」では1だけ移動させて5にする必要があります。すなわち、次のjはi-j+1になります。
現在 i-j i
│ │
i: 0123456789101112
t: dabdabcabcba
p: abcb
j: 0123
│
j
次 i-j+1
│
i: 0123456789101112
t: dabdabcabcba
p: abcb
j: 0123
タで、一致したことがわかり、その戻す値がi-jなのは、次の理由です。
現在 i-j i
│ │
i: 0123456789101112
t: dabdabcabcba
p: abcb
j: 0123
│
j
すべての文字が一致したのは、j=3(=m-1)のときに、キが成立したときです。クでi=10+1=11、ケによりj=4(=m)になり、タに到達します。そして、戻す値は7(「現在」でのi-j)になります。タに達したときのiとjは、「現在」よりも1多いので、戻す値は「(i-1)-(j-1)」なのですが、これを計算すると、i-jになります。
力任せ法では、無駄な比較をしています。例えば、
現在 i-j i
│ │
i: 0123456789101112
t: dabdabcabcba
p: abcb
j: 0123
│
j
で、t[7]≠p[3]となったときを考えます。力任せ法では、
i: 0123456789101112
t: dabdabcabcba
p: abcb
p: abcb
のように、pの位置を1つずつ右にずらして、再度比較をしていきます。
しかし、「現在」の時点で、t[i-j+1]=t[5]=b、t[i-j+2]=t[6]=cであることがわかっているのですから、p[0]=aとt[5]=bやt[6]=bを比較する必要はなく、次のように、t[7]から比較をすればよいことになります。
i: 0123456789101112
t: dabdabcabcba
p: abcb
ここで重要なことは、pの先頭位置はi-jなのですから、pの位置をk個右にずらすということは、i-jの値をi-j+kにするということです。
力任せ法で「t[i]≠p[j] になったら、pの位置を1つ右にずらす」のは、シで「i=i-j+1」としたからです。
あらかじめ、pの文字列を調べて、「i=i-j+f[j]から比較を行う」というような配列fを作成しておけば(上の例で、f[3]=2となっていれば、i=i-j+f[j]=7-3+3=7なので、次は t[7] から比較する)、比較回数を減少させることができます。
その代表的な方法に後述のKMP法とBM法があります。
KMP法では、「p[j] の位置で不一致になったとき、何文字ずらして再開するか」に着目して、それをあらかじめ表(配列next)にしておきます。
KMP法の特徴は、力任せ法と異なり、テキストの比較で後戻りをしない(t[i] のiを小さくするステップがない)ことです。すなわち、最悪の場合でもn回の比較ですみます。それで計算量のオーダーは O(n) となります(next を設定するための比較回数がかかりますが、mはnに対して非常に小さいのが通常ですから、無視することができます)。
テキストの比較で後戻りしないために、テキストが非常に大きく、メモリに格納できず、ファイルから読み込んで処理をすることができます。
ア function kmp() {
イ var i, j;
/* ずらす表 next[j] の作成 */
ウ next = new Array(11);
エ next[0] = 1;
オ for (j=1; j<m; j++) {
カ for (k=1; k<j; k++) {
キ jj=k;
ク while ( (jj<j) && (p[jj] == p[jj-k]) ) jj++;
ケ }
コ next[j] = k;
サ }
/* tとpの比較 */
シ i = 0;
ス j = 0;
セ while ( (i < n) && (j < m) ) {
ソ if (t[i] == p[j]) {
タ i++;
チ j++;
ツ }
テ else {
ト j = j - next[j];
ナ if (j < 0) {
ニ i++;
ヌ j++;
ネ }
ノ }
ハ }
ヒ if (j == m) return i - m;
フ else return -1;
ヘ }
前半(ウ~サ)は、next[j] を設定するプロセスです。これに関しては、かなり複雑なので後述することにして、ともかく、次のように設定されたこととします。
next[0]=1,next[1]=1,next[2]=2,next[3]=3
後半(セ~ホ)は、tとpとの比較をするプロセスです。
ここでのセ~ハは、力任せ法のカ~ソとよく似ています。
t[i]=p[j] の場合はまったく同じです。
t[i]≠p[j] の場合は、
力任せ法:i= i - j + 1; j = 0;
KMP法:j=j-next[j];
(j<0のときは、i,jに1を加える)
が異なるだけです。
先に「pの位置をk個右にずらすには、i-jをi-j+kにする」といいました。トでjの値をj-next[j] にすることは、i-jをi-j+next[j] にすることですから、これは、pの先頭位置を next[j] だけ右に移動せよということになります。
例えば、
現在 i-j i
│ │
i: 0123456789101112
t: dabdabcabcba
p: abcb
j: 0123
│
j
次のj: abcb
で、現在のpの先頭位置は4です。i=7、j=3で不一致になったとき、next[3]=3であるとすれば、j=j-next[j]=3-3=0 になります。そして、次にソで比較するのは、t[7]=aとp[0] です。すなわち、pをnext[3]=3だけ右に移動したことになります。
なお、ナ~ネでの、「j<0のとき」は、p[0] との比較で不一致になったとき、次にp[-1]とt[i-1] を比較することを避けるためです。
力任せ法では、while のループが2重になっていました。それで、O(n×m) の計算量になったのです。
それに対して、KMP法では1つのループになっており、次のトレースのように、比較位置が減少することがありません。それで、計算量は O(n×m) になります。
i j next[j] 01234567891011
dabdabcabcba
0 0 1 abcb j=0-1<0なので、i+1=1、j+1=0
1 0 1 abcb
2 1 1 abcb
3 2 2 abcb j=2-next[2]=0≧0、next[2]=2だけ右へ
3 0 1 abcb j=0-1<0→i=4、j=0
4 0 1 abcb
5 1 1 abcb
6 2 2 abcb
7 3 3 abcb
7 0 1 abcb
8 1 1 abcb
9 2 2 abcb
10 3 3 abcb
└ 一致位置=7
p=abcbの場合に、next[0]=1,next[1]=1,next[2]=2,next[3]=3と設定した理由は、上の説明で理解できたと思います。
以降、それを設定するアルゴリズムの説明をします。
上の例では、pが短く同じ文字が少なくわかりにくいので、
p=abcabbc
とします。
next は次のようになります。
j : 0 1 2 3 4 5 6
p[j]: a b c a b b c
next[j]: 1 1 2 3 3 3 6
ここで、どこのaかbかわかりにくいので、必要に応じて、a0, b1, c2, a4, …, c6 と表記します。
●a0:
i: 0 1 2 3 4 5 …
t: - - x ? ? ? …
p: a0 b1 c2 …
└ここで不一致
先頭位置で不一致のときは、無条件で1つ右へ移動し、a0から比較を再開します。→next[0]=1
i: 0 1 2 3 4 5 …
t: - - x ? ? ? …
p: a0 b1 c2 …
└ここから比較
●b1:
i: 0 1 2 3 4 5 …
t: - - a x ? ? …
p: a0 b1 c2 …
└ここで不一致
xがaかも知れないので、1つ右へ移動し、a0から比較を再開します。→next[1]=1
i: 0 1 2 3 4 5 …
t: - - a x ? ? …
p: a0 b1 c2 …
└ここから比較
●c2:
i: 0 1 2 3 4 5 …
t: - - a b x ? …
p: a0 b1 c2 …
└ここで不一致
xがaかも知れないので、2つ右へ移動し、a0から比較を再開します。→next[2]=2
i: 0 1 2 3 4 5 …
t: - - a b x ? …
p: a0 b1 c2 …
└ここから比較
●a3:
i: 0 1 2 3 4 5 6 …
t: - - a b c x ? …
p: a0 b1 c2 a3 b4 …
└ここで不一致
xがaかも知れないので、3つ右へ移動し、a0から比較を再開します。→next[3]=3
i: 0 1 2 3 4 5 6 …
t: - - a b c x ? …
p: a0 b1 c2 a3 b4 …
└ここから比較→next[2]=2
ここまでで、p[1]~p[j-1] にp[k]=p[j] となる文字が存在しないときは、next[j]=jとればよいことがわかります。
また、比較を再開するtの位置は、不一致が発生したところからであることもわかります。
●b4:
i: 0 1 2 3 4 5 6 7 …
t: - - a b c a ? ? …
p: a0 b1 c2 a3 b4 b5 …
└ここで不一致
このときには、単純に4つずらすと、次のようになります。
i: 0 1 2 3 4 5 6 7 …
t: - - a b c a x ? …
p: a0 b1 c2 a3 b4 b5 …
ところがtの5がaですから、a0をそこに合わせる必要があります。そして、そこでは既に一致していることがわかっているので、b1から(すなわち、tの現在位置(6)から)比較を再開することになります。→next[4]=3
i: 0 1 2 3 4 5 6 7 …
t: - - a b c a x ? …
p: a0 b1 c2 a3 b4 b5 …
└ここから比較
この next[4]=3を探すには、次のように考えます。
p[4] で不一致だということは、p[0]~p[3] はtと一致していたことになります。
比較位置の一つ手前(5)p[3]=aですから、a0を5の位置まで移動させることになります。
●b5:
i: 0 1 2 3 4 5 6 7 8 …
t: - - a b c a b x ? …
p: a0 b1 c2 a3 b4 b5 c6
└ここで不一致
p[5] で不一致だということは、p[0]~p[4] はtと一致していたことになります。
比較位置の一つ手前(6)のpはb4、その前(5)はa3です。すなわち、位置5~6にa0とb1がくるように移動させる必要があります。→next[5]=3
i: 0 1 2 3 4 5 6 7 8 …
t: - - a b c a b x ? …
p: a0 b1 c2 a3 b4 b5 c6
└ここから比較
b4とb5の場合を一般化すると次のようになります。
「t[i]≠p[j] になったとき、pをkだけ右に移動するとします。
jjをkからj-1まで変化させ、すべてのjjでp[jj]=p[jj-k]になれば、そのkがnext[j]になります。
もし、途中でp[jj]≠p[jj-k]になれば、kを1ふやして繰り返します。」
ここで、p[jj]とは、ある比較位置iiでの移動前でのpの文字であり、その位置でのt[ii]の文字でもあります。そして、p[jj-k]とは、pをkだけ移動したときの、位置iiに対応するpの文字です。そのため、p[jj]≠p[jj-k]になるならば、k個の移動では、tとpを比較するまでもなく不一致になります。それで、kを増加する(さらに右に移動させる)のです。
具体的に、b5のときを考えましょう。i=7、j=5で、t[7](=x)≠p[5] (=b5)になりました。
k=1のとき(pを右に1つ移動させたとき)
jj=1~4に変化させますが、
jj=1のとき、p[jj]=p[1]=b1、p[jj-k]=p[0]=a0で不一致
これは、位置ii=3で、t[3]=bなのに、pがa0なので不一致だったという意味です。
k=2のとき(pを右に2つ移動させたとき)
jj=2~4に変化させますが、
jj=2のとき、p[jj]=p[2]=c2、p[jj-k]=p[0]=a0で不一致
これは、位置ii=4で、t[4]=cなのに、pがa0なので不一致だったという意味です。
k=3のとき(pを右に3つ移動させたとき)
jj=2~4に変化させます。
jj=3のとき、p[jj]=p[3]=a3、p[jj-k]=p[0]=a0で一致
jj=4のとき、p[jj]=p[4]=b4、p[jj-k]=p[1]=b1で一致
t[5]=a、t[6]=bが移動後のa0とb1に一致しているという意味です。
この後は、t[6]=?と移動後のb2を比較することになります。
●C6:
i: 0 1 2 3 4 5 6 7 8 9 …
t: - - a b c a b b x ? …
p: a0 b1 c2 a3 b4 b5 c6
└ここで不一致
c6のときは、次のように6個移動させる必要があります。→next[6]=6
i: 0 1 2 3 4 5 6 7 8 9 …
t: - - a b c a b b x ? …
p: a0 b1 c2 a3 b4 b5 c6
└ここから比較
j k jj jj-k p[jj] p[jj-k] next[j]
0 1 ルール1
1 1 ルール3
2 1 1 0 b a 2 ルール3
3 1 1 0 b a
3 2 2 0 c a 3 ルール3
4 1 1 0 b a
4 2 2 0 c a
4 3 3 0 a = a 3 ルール2
5 1 1 0 b a
5 2 2 0 c a
5 3 3 0 a = a
5 3 4 1 b = b 3 ルール2
6 1 1 0 b a
6 2 2 0 c a
6 3 3 0 a = a
6 3 4 1 b = b
6 3 5 2 b c
6 4 4 0 b a
6 5 5 0 b a 6 ルール3
BM法は、pとtを比較するのに、pの末尾から順に前へと比較することにより、一挙に大きくpを右に移動させる工夫をしています。
例えば、tとpが下図の位置関係にあるとき、pの末尾bとtのxが不一致になったとします。
0123456789
t: --???x????
p: abcb
ア: │abcb
イ: │ abcb
ウ: │ abcb
エ: │ abcb
└───┘
このとき、xがpに存在しない文字であれば、ア~ウでは、いずれもxと一致しないのですから、他のtやpを比較するまでもなく、エのように、pをm(pの文字数)だけ移動することができます。
また、xがpに存在する文字、例えばcであれば、pの比較した個所から直前のcのところが比較位置にくるように移動すればよいことになります。
0123456789
t: --???c????
p: abcb
ア: abcb
このように、tの文字が、pに存在しない文字ならm、存在する文字なら、その文字に対応した移動量(例えばcならば1のように)の表を作っておけば、比較して不一致になったときに、tの文字により、pを移動させることができます。下のプログラムでは、その表を skip としています。
ア function bm() {
イ var i, j, k;
/* skip[j] の設定 */
ウ skip = new Array();
エ skip["a"] = m; skip["b"] = m; … , skip["z"] = m;
オ for (j=0; j<m; j++) skip[p[j]] = m-j-1;
/* tとpの比較 */
カ i = 0;
キ while (i <= n-m) {
ク j = m - 1;
ケ while ((j >= 0) && (t[i+j] == p[j]) ) j--;
コ if (j < 0) return i;
サ k = skip[t[i+j]] - (m-j-1);
シ if (k > 0) i = i + k;
ス else i = i + 1;
セ }
ソ return -1;
タ }
●ウ~オ:skip の設定
Javascriptでは(C言語も)、skip["a"] や skip["BM法"] のように、配列の添字を文字リテラルで与えることができます(詳細は文法書を参照してください)。
エでは、tで出現するであろうすべての文字種について、値をmに設定しておきます。これは、pに存在しない文字で不一致になったとき、pの文字数(m=4)だけ、pを右に移動させるためです。
オは、pに存在する文字についての設定です。
オを実行すると次のようになります。
j p[j] skip[p[j]]
0 a skip["a"]=3
1 b skip["b"]=2 ①
2 a skip["c"]=1
3 b skip["b"]=0 ②
①と②が重複しますが、後のもので上書きされるので、末尾のほうが優先され②が残り、skip["b"]=0となります。
結果として、オが終了した段階では、skip の値は次のようになっています。
aのとき3
bのとき0
cのとき1
その他のとき4
●キ~ス:tとpの比較
ここではtを次の文字列だとします。n=12です。
i: 0123456789101112
t: dbcbbdbabcba
i=0のとき
01234567891011
t: dbcbbdbabcba
p: abcb
先に skip[t[i+j]] とは、t[i+j]とp[j]が一致しなかったときに、t[i+j]の文字種により、pを移動させる距離だといいました。それならば、サは k=skip[t[i+j]] でよいのではないかと考えられます。どうして、(m-j-1) を引く必要があるのでしょうか?
ここまでで比較した(文字がわかっている)のは、
01234567891011
t: dbcb????????
p: abcb
だけです(?の部分はわかっていない)。
しかも、BM法(簡易BM法)では、先に比較した結果は忘れています【注3】ので、
01234567891011
t: d???????????
p: a???
となります。
k=skip[t[i+j]](=4) としたのでは、
01234567891011
t: d??????????
p: a???
になってしまいます。あるいはtが、
01234567891011
t: ?abcd??????
p: abcb
となっていたら、一致しているのを見逃すことになります。
これを回避するには、下図のように、m-j-1個だけ戻す必要があるのです。
01234567891011
t: ?a?????????
p: a???
jの値─┘ └─mの値
└─┬┘
m-j-1 = 4-0-1 = 3
i=1のとき
01234567891011
t: dbcbbdbabcba
p: abcb
どうして、シではなく、スにするのでしょうか?
i=1のときは、次のようになっていました。
01234567891011
t: dbcbbdbabcba
p: abcb
シを採用すると、kが負なので、i=i+k=1-1=0になり、
01234567891011
t: dbcbbdbabcba
p: abcb
i=2のとき
01234567891011
t: dbcbbdbabcba
p: abcb
i=6のとき
i=7のとき
pの位置は、下のようになっています。
01234567891011
t: dbcbbdbabcba
p: abcb