アルゴリズムと データ構造

アルゴリズムと
データ構造
第１３回
文字列の照合
塩浦昭義
情報科学研究科 准教授
[email protected]
http://www.dais.is.tohoku.ac.jp/~shioura/teaching
期末試験について
• 日時：2月8日（水）13:00～14:30（確定）
• 受験資格：
– 中間試験に合格
– 中間試験以降にレポートを一回以上提出
• 教科書，ノート等の持ち込みは一切不可
• 座席はこちらで指定
• 試験内容：第７回（アルゴリズムの設計）～第13回（今回）の講義
で教えたところ
• ５０点満点，２９点以下は追試レポートもしくは単位不可
※ 期末試験の出来が悪く，かつ救済を希望する場合は
2月10日（金）12：00までに問い合わせること
（救済できない可能性もあり）
文字列の照合
• 与えられた文書の中に，検索したいキーワードが入っているか
どうか調べたい
– Web検索，ファイル検索において基本的な技術
• キーワード：p= a b a a
パターン
• 文書：t= b a b c a b a a b a a c a a b a a テキスト
• パターンが含まれているかどうか，判定
– 含まれている場合には，一番左側の場所を計算
• テキストn文字，パターンm文字，配列で与えられていると仮定
– t=t[0],t[1],…,t[n-1], p=p[0]p[1]…p[m-1]
素朴なアルゴリズム
• テキストの長さ n の全ての部分列をパターンと比較する
babcabaabaacaabaa
abaa
時間計算量はO(mn)
x x x x o
ステップ１: h:=0
（パターンの0文字目をテキストの0文字目に合わせる）
ステップ2: p[j]=t[h+j] が j=0,1,…,m-1に対して成り立つか
チェック（テキストのh文字目からテキストと比較する）．
成り立つh を出力，停止
成り立たないh:=h+1 とおき，h>n-m なら 停止（パターンなし）
n≦n-m なら ステップ2を繰り返す
Boyer-Moore法
• BM法: 1977年にBoyerとMooreが提案
• 時間計算量は O(m+n), 実用的にはもっと速い
• 特徴：
– パターンとテキストを比較するとき，パターンの右側から始める
– 過去の計算により得られた情報を最大限利用
BM法の基本的な考え方：
典型的な例
a l g o r i t hm a n d
da t a
s t ruc ture
c c cbbbbb c c cbbbbb c c cbbbbb c c cbbbbb
• パターンの最右文字p[m-1]とテキストt[7]を比較
– 一致しないのでパターンを右に移動させる
• 文字 t[7]=h はパターンのどこにも現れない
パターンを少し右に移動させても，一致しないのは明らか
7つ移動させても良い
• これを繰り返すと，あっという間に検索終了
BM法の基本的な考え方
babcabaabaac
baabaacaabaa
abaa
abaa
• パターンの最右文字p[3]と
テキストt[3]を比較
一致しない
• 文字 t[3]=c はパターンのど
こにも現れない
パターンを4つ移動
• パターンを検出
• パターンの最右文字p[3]と
テキストt[3]を比較
一致しない
• 文字 t[3]=b はパターンの
p[1]に出現する
p[1]とt[3]がマッチするよう
に，パターンを移動
• パターンを検出
パターン移動の方針１
• テキストで不一致文字t[i]=xが見つかった
– “x”はパターンに存在しない
babcabaabaac
t[i+1]とp[0]がマッチするように
abaa
パターンを移動
– “x”はパターンに存在する
baabaacaabaa
パターンの最右の“x”とt[i]が
マッチするようにパターンを移動
abaa
• 不一致文字発見後の移動幅は事前に計算することが可能
– これを使って移動幅を単位時間で計算
方針1に基づく移動幅の計算方法
（その１）
• 移動幅計算に使うデータを配列 d に格納
• 文字 “x” がパターンに含まれない
d(x):=-1 移動幅は j–d(x) = j+1
例
• パターンの最右文字p[3](j=3)
とテキストt[3]=cを比較
一致しない
• “c”はパターンに現れない
d(c)=-1
• パターンを j-d(c)=3-(-1)=4 移
動
babcabaabaac
abaa
方針1に基づく移動幅の計算方法
（その２）
• 移動幅計算に使うデータを配列 d に格納
• 文字 “x” がパターンに含まれる
d(x):=k (パターン内で最右の “x” が p[k]に現れるとき）
移動幅は j–d(x) = j-k
例
• パターンの最右文字p[3](j=3)
とテキストt[3]=bを比較
一致しない
• “b”はパターンに現れる
d(b)=1
• パターンを j-d(b)=3-1=2 移動
baabaacaabaa
abaa
方針1に基づく移動幅の計算方法
（その３）
• 文字 “x” がパターンに含まれる
d(x):=k (パターン内で最右の “x” が p[k]に現れるとき）
移動幅は j–d(x) = j-k
ただし，j-d(x)≦0 のときは １ 移動（左への移動を禁止）
例
• パターンの最右文字p[1](j=1)
bbbaaa c aabaa
とテキストt[1]=bを比較
acba
一致しない
• “b”はパターンに現れる
d(b)=2
左に移動は禁止
• j-d(b)=1-2≦0パターンを 1 移動
方針1に基づく移動幅の計算方法
（まとめ）
• d(x)の計算
– 文字 “x” がパターンに含まれない d(x):=-1
– 文字 “x” がパターンに含まれる
d(x):=k (パターン内で最右の “x” が p[k]に現れるとき）
• 移動幅は s=max{1, j–d(x)}
例
• 右のパターンの場合，
d(a)=3, d(b)=2, d(c)=1,
その他の文字 x に対して d(x)=-1
bbba c a f aabaa
acba
acba
acba
acba
acba
方針1の問題点
• 方針1の移動幅を使っても，O(mn) 時間が必要な例が存在
例:次のパターンの場合，
d(a)=m-1(=5), d(b)=0,
その他の文字 x に対して d(x)=-1
p[0]=bとt[0]=aで不一致
移動幅はmax{1,0-5}=1
aaaaaaaaaaaaaaa
次はp[0]=bとt[1]=aで不一致
baaaaa
移動幅はmax{1,0-5}=1
baaaaa
次はp[0]=bとt[2]=aで不一致
baaaaa
移動幅はmax{1,0-5}=1
baaaaa
（以降，繰り返し）パターン全部の
文字との比較を n-m+1 回行う  O(mn) 時間
パターン移動の方針２
• 前回のテキストとパターンの比較で，いくつかの文字が一致して
いた場合，パターン移動後にも一致するように，移動幅を決める
例： t[3]=p[3]=a, t[2]=p[2]=b,
bbaaaac aabaa
t[1]≠p[1] となりパターン不一致
パターンの移動
acaa
• 移動幅1の場合：p[2]=a=p[3]だが，
acaa
p[1]=c≠a=p[2]なので，
acaa
テキストと不一致は自明
acaa
• 移動幅2の場合：p[1]=c≠a=p[3]なので，
テキストと不一致は自明
• 移動幅3の場合：p[0]=a=p[3]なので，
テキストと一致の可能性あり３移動させてもよい
方針２に基づく移動幅の計算方法
（その１）
• パターンの右側の文字p[j+1],p[j+2],…,p[m-1]がテキストと
一致，p[j]が不一致と仮定
• パターンを幅 s だけ右に移動させたとき，
テキストと一致するためには，
移動前の p[j+1],p[j+2],…,p[m-1]と重なる部分
p[j-s+1],p[j-s+2],…,p[m-s-1]がそれぞれ等しい必要あり
かつ，移動前の p[j+1]と重なるp[j-s]について
p[j+1]≠p[j-s] となる必要あり（p[j+1]はテキストと異なるので）
babbaabc abaa
aaacaa
幅3
aaacaa
j=3, s=3
p[4], p[5] と p[1], p[2] が
それぞれ等しい
p[3] と p[0] は異なる
テキストと一致の可能性あり
方針２に基づく移動幅の計算方法
（その２）
• パターンの右側の文字p[j+1],p[j+2],…,p[m-1]がテキストと
一致，p[j]が不一致と仮定
• パターンを幅 s だけ右に移動させたとき，
j-s<0のときは，テキストと一致するためには
p[s],p[s+1],…,p[m-1]と
p[0],p[1],…,p[m-s-1] がそれぞれ等しい必要あり
（とくに，s=m のときは条件なし）
babbaabc abaa
aaacaa
幅5
幅m=6
aaacaa
aaacaa
j=3, s=5, j-s=-2<0
p[5] と p[1] が等しい
テキストと一致の可能性あり
j=3, s=6, j-s=-2<0
無条件で
テキストと一致の可能性あり
方針２に基づく移動幅の計算方法
（その３）
• パターンの右側の文字p[j+1],p[j+2],…,p[m-1]がテキストと
一致，p[j]が不一致と仮定
• テキストとの一致が期待できる移動幅 s が複数存在
一番小さな s を選択，これを移動幅 e(j) とする
（常に1≦e(j)≦m）
j=3のとき
aaacaa
幅3
幅4
幅5
幅6
e(3)=3
aaacaa
aaacaa
aaacaa
aaacaa
j=4のとき
e(4)=1
aaacaa
幅1
aaacaa
幅5
幅6
aaacaa
aaacaa
BM法の流れ
•
•
•
•
前処理：d(x)とe(j)の計算を事前に行う
各反復では，テキストのある一部分とパターンを比較
テキストの一部分がパターンと一致その位置を出力して終了
パターンと不一致，p[j]とt[i]が異なっていたと仮定
パターンを幅ｓだけ右に移動させる
s = max{j-d(t[i]), e(j)}
方針1
方針2
特徴
• 理論的な時間計算量は O(m+n)
（前処理の時間も含む．解析はやや面倒）
• 実用的には高速，実装は比較的簡単
BM法の実行例
例：前処理：右のパターンの場合，
bbbac a f aabaa
d(a)=3, d(b)=2, d(c)=1,
その他の文字 x に対して d(x)=-1 a c b a
e(0)=3, e(1)=3, e(2)=3, e(3)=1
acba
第1反復：t[0],…,t[3]と比較，
acba
t[1]=b≠c=p[1]より不一致
acba
移動幅 max{1-d(b), e(1)}=max{-1,3}=3
第2反復：t[3],…,t[6]と比較，t[6]=f≠a=p[3]より不一致
移動幅 max{3-d(f), e(3)}=max{4,1}=4
第3反復：t[7],…,t[10]と比較，t[8]=a≠c=p[1]より不一致
移動幅 max{1-d(a), e(1)}=max{-2,3}=3
テキストからはみ出るので，終了（パターンは見つからなかった）
方針1のみでうまくいかなかった例
例:次のパターンの場合，
d(a)=m-1(=5), d(b)=0, その他の文字 x は d(x)=-1
e(0)=m(=6), e(1)=…=e(6)=1
p[0]=bとt[0]=aで不一致
移動幅はmax{0-d(a),e(0)}=max{-5,6}=6
次はp[0]=bとt[6]=aで不一致
aaaaaaaaaaaaaaa
移動幅はmax{-5,6}=6
（以降，繰り返し）
計算時間は O(m + n) に減少
baaaaa
baaaaa
baaa