文字列検索のアルゴリズム

予備知識

• アルゴリズムとは？
• 文章構成

はじめに

この記事では文字列検索のアルゴリズムを３つ紹介します。

• 力まかせ法
• ＫＭＰ法
• ＢＭ法

文字列検索のアルゴリズムで出来ること

ある文字列の中に指定された文字列が含まれるか調べる
※以降は「ある文字列」のことを「テキスト」と呼ぶ
※同様に「指定文字列」のことを「パターン」と呼ぶ

計算対象選別

判定	計算対象	関係	数値
○	データの比較回数	>	1
	データの交換回数	=	0
	関数の呼び出し回数	=	0

共通変数定義

変数にする対象	変数	関係	値
テキストの文字数	$n$	>	$m$
パターンの文字数	$m$	>	1

※パターンは文字列なので１より大きい

力まかせ法

テキストの先頭からパターンと一致する部分があるか
パターンを１文字ずつずらして確認していく
力技との意味合いで力まかせ法と呼ばれる

動作順序

①テキストとパターンを左揃えにする
②テキストの比較開始位置をテキストの先頭の文字とする
③テキストとパターンを各文字列の左側から順番に比較する
④パターンが見つかれば終了し不一致の時点でパターンを１文字ずらして③へ戻る

変数定義

変数にする対象	変数	関係	値
パターンの比較繰り返し回数	$k$	=	$n-m+1$
文字列一致の組み合わせの総数	$S_1$
すべての組み合わせにおける計算量の総和	$S_2$

一般化

最善の計算量

最善の計算量となるのは
テキストの最初でパターン全文字が一致したときである
このときのデータの比較回数は
$T(n)=m$
漸近計算量は $O(m)$ である

---

最悪の計算量

最悪の計算量となるのは
テキストの末尾文字手前までおなじ文字がつづき
テキストの末尾文字確認時にようやくパターンとの一致が確認できるときである

比較した文字が不一致のとき
テキストの比較開始位置とパターンの位置を右にずらす必要があり
そのたびにパターンの文字数分の比較が必要になるため計算量が多くなる

合計で何回ずらすかというと
テキストの文字数からパターンの文字数を引いた数なので

$$n-m$$

このうち１文字ずらす度にパターンの文字数分の比較を行うので
その比較回数の合計は

$$m(n-m)$$

一番最初のパターンをずらす前の比較を加味すると

$$m(n-m+1)$$

よって
$T(n)=nm-m^2+m$
漸近計算量は $O(nm)$ である

確かめ算

$m$	$T(n)$
5	15
4	16
3	15
2	12

※ｎが７のとき

---

平均の計算量

最悪の計算量においては
パターンをずらす前も含めて
$n-m$ のうち１文字ずらす度にパターンの文字数分の比較を行う必要があった

平均の計算量においては
この文字数分の比較のいずれかの段階で一致する場合が想定できる

そこでそれぞれの場合がどういった形で一致するのか調べる必要があるので

• まずは文字列一致の組み合わせの総数を求める
• 次にすべての組み合わせにおける計算量の総和を求める
• 最後に総和を総数で割り算して平均の計算量を求める
  ※以降はそれぞれを「総数」「総和」と呼ぶこととする

ずらし過程は行列の行追加と似ているので行列と同様に扱うものとして
テキストの文字数が５でパターンの文字数が３の例を表にすると

1	2	3	4	5	組み合わせ
○	○	○	○	○
a	b	c			1
○	○	○	○	○
a	b	c
	a	b	c		$1×3$
○	○	○	○	○
a	b	c
	a	b	c
		a	b	c	$1×3×3$

このようにテキストとパターンの文字列によって行数に違いが生じる
これは行数が増えると計算量が増えることを意味している
また各行での比較回数もテキストの文字列によって異なり１～３のいずれかになる
※何文字目で不一致となるかが異なるから
ということは行が追加されるたびに組み合わせが３倍されることになる

一般化した組み合わせを数列で表にすると

項	1	2	3	…	k
組み合わせ	$m^0$	$m^1$	$m^2$	…	$m^{k-1}$

※この表での数列の「項」が前述の「行」と同値である
※「行」は「パターンの比較繰り返し回数」のことである

総数はこの等比数列の和なので

$$S_1=\frac {m^k-1} {m-1}$$

前述の例の場合における計算量を表にすると

項	1	2	3
組み合わせ	$3^0$	$3^1$	$3^2$
計算量	$3$	$4,5,6$	$5,6,6,7,7,7,8,8,9$

数列の第１項の計算量は３であり
数列の第２項の計算量は第１項の計算量のひとつに対して１～３のいずれかが足された数値となり
数列の第３項の計算量は第２項の計算量それぞれに対して１～３のいずれかが足された数値となる

すべての組み合わせにおける計算量を一般化して表にすると

項	1	2	3	…	k
組み合わせ	$m^0$	$m^1$	$m^2$	…	$m^{k-1}$
計算量	$m$	$(m+1)～2m$	$(m+2)～3m$	…	$[m+(k-1)]～km$

行が増えるごとに最低でも１回は余分に比較しないと次の行に移動できないので各項の最小値は１ずつ増加する
各項の最大値は各行までの最大の計算量と見立てることができるのでパターンの文字数ずつ増加する
各項は組み合わせから行追加ごとｍ倍の分布になり均一に並ぶ
※例の計算量の表の通りである
よって中央値が各組み合わせの数だけ配されていることと同じである

数列の一般項の最小値と最大値から中央値を求めると

$$\frac {mk+m+k-1} 2=\frac {(m+1)(k+1)} 2-1$$

さきほどの表に中央値を追記すると

項	1	2	3	…	k
組み合わせ	$m^0$	$m^1$	$m^2$	…	$m^{k-1}$
計算量	$m$	$(m+1)～2m$	$(m+2)～3m$	…	$[m+(k-1)]～km$
中央値	$\frac {m+1} 2(1+1)-1$	$\frac {m+1} 2(2+1)-1$	$\frac {m+1} 2(3+1)-1$	…	$\frac {m+1} 2(k+1)-1$

組み合わせと中央値から総和を求める
その前に各中央値の式の末項に注目するとそれぞれ $-1$ しており
これらを組み合わせと掛け算して合計すると総数を引くことに等しいので総和は

$$S_2=\frac {m+1} 2[2m^0+3m^1+4m^2+…+(k+1)m^{k-1}]-\frac {m^k-1} {m-1}$$

右辺の中括弧内は等差等比数列の和なので解いていくと

$$S_2=\frac {(m+1)(m^k-1)} {2(m-1)}[k+\frac k {m^k-1}+1-\frac 1 {m-1}]-\frac {m^k-1} {m-1}$$

よってｋをｎとｍの式に戻して総和を総数で割り算すると
$T(n)=[(n-m+1)(1+\frac 1 {m^{n-m+1}-1})+(1-\frac 1 {m-1})]\frac {m+1} 2-1$
漸近計算量は $O(nm)$ である

---

一般式の一覧表

種類	漸近記法	実際記法	条件
最善	$O(m)$	$m$	$n>m>1$
最悪	$O(nm)$	$nm-m^2+m$	同上
平均	同上	$[(n-m+1)(1+\frac 1 {m^{n-m+1}-1})+(1-\frac 1 {m-1})]\frac {m+1} 2-1$	同上

---

ＫＭＰ法

力まかせ法より計算量を減らすために効率化したアルゴリズム
パターンの文字列を記憶することで文字ずらし分の計算量を削減している
アルゴリズム開発者３名の名前が由来である

動作順序

①テキストとパターンを左揃えにする
②テキストの比較開始位置をテキストの先頭の文字とする
③テキストとパターンを各文字列の左側から順番に比較する
④パターンが見つかれば終了し不一致の時点でパターンを適量ずらして③へ戻る

一般化

テキストとパターンがどういった文字列かによって変わるためここでは省略する
そのかわりに得意な文字列の組み合わせを記載する

ＫＭＰ法が得意な文字列の組み合わせ

ＫＭＰ法が得意なのはパターンの文字数が３文字以上で
パターンの末尾で不一致となる場合である

そのなかでも２種類の得意な文字列の組み合わせがある

不一致文字がパターンに含まれない文字であるとき

不一致文字がパターンの先頭の文字であるとき

ＢＭ法

ＫＭＰ法よりも計算量を減らすため効率化したアルゴリズム
パターンの文字列を記憶することで文字ずらし分の計算量を削減
さらにパターンの末尾から比較することで計算量を削減している
アルゴリズム開発者２名の名前が由来である

動作順序

①テキストとパターンを左揃えにする
②テキストの比較開始位置をパターンの末尾の位置とする
③テキストとパターンをパターンの右側から逆順に比較する
④パターンが見つかれば終了し不一致の時点でパターンをずらし表をもとにずらして③へ戻る

ずらし表の使い方

パターンの文字に重複がないとき

パターンの文字に重複があるとき

例えば下表のようなパターンの文字重複のときには
最終比較位置２までにａとｂの２つの文字が一致して
そのうえａとｂはパターンの末尾から３文字目以降に含まれる
そこでずらし量が最小になるａの値を適用する形になる

3	2	1	0
a	c	a	b	a	a	b
b	a	a	b
a	c	a	b	a	a	b
	b	a	a	b

具体的には
最終比較位置以降でずらし表に対応する位置から
最終比較位置以前で最後にａを発見した位置を引くので
この文字列比較における最初のずらし量は
$2-1=1$

一般化

テキストとパターンがどういった文字列かによって変わるためここでは省略する
そのかわりに得意な文字列の組み合わせを記載する

ＢＭ法が得意な文字列の組み合わせ

ＢＭ法が得意なのは文字数でテキストがパターンの２倍以上のときで
パターンの末尾の文字がパターンの他文字に含まれない文字の場合である

そのなかでも２種類の得意な文字列の組み合わせがある

パターンの末尾が不一致したとき

パターンの末尾のみ一致したとき