文字列照合 BM 法
山崎浩一
理工学部 電子情報理工学科
アルゴリズム II, Autumn 2015
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
1 / 30
1
文字列照合
Boyer-Moore のアルゴリズム (P.182)
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
2 / 30
1
文字列照合
Boyer-Moore のアルゴリズム (P.182)
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
3 / 30
Boyer-Moore のアルゴリズムの概要
この節で説明する Boyer-Moore のアルゴリズム (BM 法) は KMP 法よりさらに高速である.
BM 法の時間計算量は，KMP 法と同じ最悪の場合で O(m + n) であるが，
実用上の性能は KMP 法より優れており, 最も速い文字列照合アルゴリズムといわれている.
BM 法の高速性は， テキスト中の多くの文字を調べないで済む可能性による.
KMP 法ではテキスト中のすべての文字を 1 回は調べなければならないため，比較は少なくとも n 回必要である.
これに対して， BM 法では n/m 回比較すればよいことがある.
このため，特に，パターンの長さが大きいときに計算時間を減らすことが期待できる.
前に述べたように，
BM 法の最悪の場合の時間計算量は O(m + n) であり，漸近的には KMP 法と同じであるが，
実際の文書処理などの場面では，多くの文字を調べないで済むことがよく起きる.
そのため，経験的にも BM 法が KMP 法に比べてかなり速いといわれている.
BM 法がこれまでのアルゴリズムと大きく違う点は,
BM 法は， KMP 法と同様に，パターンをテキストの左端から順に重ね合わせて比較していく.
しかし，パターンをテキスト上に重ね合わせた後，バターンの右端から比較を行う.
この方法により，不一致が見つかったときに大きくパターンをずらすことができる. BM 法はこのようにし
て高速化を図っている.
BM 法は高速化のために二つの工夫を行っている. それぞれについて説明する.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
4 / 30
Boyer-Moore のアルゴリズムの概要
この節で説明する Boyer-Moore のアルゴリズム (BM 法) は KMP 法よりさらに高速である.
BM 法の時間計算量は，KMP 法と同じ最悪の場合で O(m + n) であるが，
実用上の性能は KMP 法より優れており, 最も速い文字列照合アルゴリズムといわれている.
BM 法の高速性は， テキスト中の多くの文字を調べないで済む可能性による.
KMP 法ではテキスト中のすべての文字を 1 回は調べなければならないため，比較は少なくとも n 回必要である.
これに対して， BM 法では n/m 回比較すればよいことがある.
このため，特に，パターンの長さが大きいときに計算時間を減らすことが期待できる.
前に述べたように，
BM 法の最悪の場合の時間計算量は O(m + n) であり，漸近的には KMP 法と同じであるが，
実際の文書処理などの場面では，多くの文字を調べないで済むことがよく起きる.
そのため，経験的にも BM 法が KMP 法に比べてかなり速いといわれている.
BM 法がこれまでのアルゴリズムと大きく違う点は,
BM 法は， KMP 法と同様に，パターンをテキストの左端から順に重ね合わせて比較していく.
しかし，パターンをテキスト上に重ね合わせた後，バターンの右端から比較を行う.
この方法により，不一致が見つかったときに大きくパターンをずらすことができる. BM 法はこのようにし
て高速化を図っている.
BM 法は高速化のために二つの工夫を行っている. それぞれについて説明する.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
4 / 30
Boyer-Moore のアルゴリズムの概要
この節で説明する Boyer-Moore のアルゴリズム (BM 法) は KMP 法よりさらに高速である.
BM 法の時間計算量は，KMP 法と同じ最悪の場合で O(m + n) であるが，
実用上の性能は KMP 法より優れており, 最も速い文字列照合アルゴリズムといわれている.
BM 法の高速性は， テキスト中の多くの文字を調べないで済む可能性による.
KMP 法ではテキスト中のすべての文字を 1 回は調べなければならないため，比較は少なくとも n 回必要である.
これに対して， BM 法では n/m 回比較すればよいことがある.
このため，特に，パターンの長さが大きいときに計算時間を減らすことが期待できる.
前に述べたように，
BM 法の最悪の場合の時間計算量は O(m + n) であり，漸近的には KMP 法と同じであるが，
実際の文書処理などの場面では，多くの文字を調べないで済むことがよく起きる.
そのため，経験的にも BM 法が KMP 法に比べてかなり速いといわれている.
BM 法がこれまでのアルゴリズムと大きく違う点は,
BM 法は， KMP 法と同様に，パターンをテキストの左端から順に重ね合わせて比較していく.
しかし，パターンをテキスト上に重ね合わせた後，バターンの右端から比較を行う.
この方法により，不一致が見つかったときに大きくパターンをずらすことができる. BM 法はこのようにし
て高速化を図っている.
BM 法は高速化のために二つの工夫を行っている. それぞれについて説明する.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
4 / 30
Boyer-Moore のアルゴリズムの概要
この節で説明する Boyer-Moore のアルゴリズム (BM 法) は KMP 法よりさらに高速である.
BM 法の時間計算量は，KMP 法と同じ最悪の場合で O(m + n) であるが，
実用上の性能は KMP 法より優れており, 最も速い文字列照合アルゴリズムといわれている.
BM 法の高速性は， テキスト中の多くの文字を調べないで済む可能性による.
KMP 法ではテキスト中のすべての文字を 1 回は調べなければならないため，比較は少なくとも n 回必要である.
これに対して， BM 法では n/m 回比較すればよいことがある.
このため，特に，パターンの長さが大きいときに計算時間を減らすことが期待できる.
前に述べたように，
BM 法の最悪の場合の時間計算量は O(m + n) であり，漸近的には KMP 法と同じであるが，
実際の文書処理などの場面では，多くの文字を調べないで済むことがよく起きる.
そのため，経験的にも BM 法が KMP 法に比べてかなり速いといわれている.
BM 法がこれまでのアルゴリズムと大きく違う点は,
BM 法は， KMP 法と同様に，パターンをテキストの左端から順に重ね合わせて比較していく.
しかし，パターンをテキスト上に重ね合わせた後，バターンの右端から比較を行う.
この方法により，不一致が見つかったときに大きくパターンをずらすことができる. BM 法はこのようにし
て高速化を図っている.
BM 法は高速化のために二つの工夫を行っている. それぞれについて説明する.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
4 / 30
Boyer-Moore のアルゴリズムの概要
この節で説明する Boyer-Moore のアルゴリズム (BM 法) は KMP 法よりさらに高速である.
BM 法の時間計算量は，KMP 法と同じ最悪の場合で O(m + n) であるが，
実用上の性能は KMP 法より優れており, 最も速い文字列照合アルゴリズムといわれている.
BM 法の高速性は， テキスト中の多くの文字を調べないで済む可能性による.
KMP 法ではテキスト中のすべての文字を 1 回は調べなければならないため，比較は少なくとも n 回必要である.
これに対して， BM 法では n/m 回比較すればよいことがある.
このため，特に，パターンの長さが大きいときに計算時間を減らすことが期待できる.
前に述べたように，
BM 法の最悪の場合の時間計算量は O(m + n) であり，漸近的には KMP 法と同じであるが，
実際の文書処理などの場面では，多くの文字を調べないで済むことがよく起きる.
そのため，経験的にも BM 法が KMP 法に比べてかなり速いといわれている.
BM 法がこれまでのアルゴリズムと大きく違う点は,
BM 法は， KMP 法と同様に，パターンをテキストの左端から順に重ね合わせて比較していく.
しかし，パターンをテキスト上に重ね合わせた後，バターンの右端から比較を行う.
この方法により，不一致が見つかったときに大きくパターンをずらすことができる. BM 法はこのようにし
て高速化を図っている.
BM 法は高速化のために二つの工夫を行っている. それぞれについて説明する.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
4 / 30
Boyer-Moore のアルゴリズムの概要
この節で説明する Boyer-Moore のアルゴリズム (BM 法) は KMP 法よりさらに高速である.
BM 法の時間計算量は，KMP 法と同じ最悪の場合で O(m + n) であるが，
実用上の性能は KMP 法より優れており, 最も速い文字列照合アルゴリズムといわれている.
BM 法の高速性は， テキスト中の多くの文字を調べないで済む可能性による.
KMP 法ではテキスト中のすべての文字を 1 回は調べなければならないため，比較は少なくとも n 回必要である.
これに対して， BM 法では n/m 回比較すればよいことがある.
このため，特に，パターンの長さが大きいときに計算時間を減らすことが期待できる.
前に述べたように，
BM 法の最悪の場合の時間計算量は O(m + n) であり，漸近的には KMP 法と同じであるが，
実際の文書処理などの場面では，多くの文字を調べないで済むことがよく起きる.
そのため，経験的にも BM 法が KMP 法に比べてかなり速いといわれている.
BM 法がこれまでのアルゴリズムと大きく違う点は,
BM 法は， KMP 法と同様に，パターンをテキストの左端から順に重ね合わせて比較していく.
しかし，パターンをテキスト上に重ね合わせた後，バターンの右端から比較を行う.
この方法により，不一致が見つかったときに大きくパターンをずらすことができる. BM 法はこのようにし
て高速化を図っている.
BM 法は高速化のために二つの工夫を行っている. それぞれについて説明する.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
4 / 30
1 つめの工夫の具体例による説明
一つめの工夫は，不一致となった位置のテキストの文字によってパターンをずらす幅を決めるものである.
まず， つぎの例を考えてみる.
【例題 9.2】
【一致しなかった テキストの文字が パターンに存在しない場合】
テキストとパターンが下図左のような位置にある場合を考える. 最初の比較はパターンの右端の文字’e’ とテキストの’a’
である. これはー致しないので，パターンを右にずらす.
このとき， テキスト上の文字’a’ はパターンに存在しないので，この’a’ の位置を含むような位置にパターンをずらして
も照合する可能性はない. この場合，パターンの長さ m = 10 だけ右にずらすことができる.
【一致しなかった テキストの文字が パターンのほかの位置にある場合】
テキストとパターンが下図右のような位置にある場合を考える. つまり，パターンの右端からの比較が進み，文字’r’
と’y’ の比較で不一致になったとする.
この場合は，パターン中の’y’ の位置を揃えるようにずらすことができる.
どちらの場合も，不一致がわかった時点で大幅にパターンを右にずらすことができる.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
5 / 30
1 つめの工夫の具体例による説明
一つめの工夫は，不一致となった位置のテキストの文字によってパターンをずらす幅を決めるものである.
まず， つぎの例を考えてみる.
【例題 9.2】
【一致しなかった テキストの文字が パターンに存在しない場合】
テキストとパターンが下図左のような位置にある場合を考える. 最初の比較はパターンの右端の文字’e’ とテキストの’a’
である. これはー致しないので，パターンを右にずらす.
このとき， テキスト上の文字’a’ はパターンに存在しないので，この’a’ の位置を含むような位置にパターンをずらして
も照合する可能性はない. この場合，パターンの長さ m = 10 だけ右にずらすことができる.
【一致しなかった テキストの文字が パターンのほかの位置にある場合】
テキストとパターンが下図右のような位置にある場合を考える. つまり，パターンの右端からの比較が進み，文字’r’
と’y’ の比較で不一致になったとする.
この場合は，パターン中の’y’ の位置を揃えるようにずらすことができる.
どちらの場合も，不一致がわかった時点で大幅にパターンを右にずらすことができる.
s ? ? ? ? ? ? ? ? ? ? a ? ? ? ? ? ? ? ? ? ? ? ?
p b o y e r m o o r e 不一致
p b o y e r m o o r e 不一致
.
.
.
p b o y e r m o o r e 不一致
p b o y e r m o o r e
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
5 / 30
1 つめの工夫の具体例による説明
一つめの工夫は，不一致となった位置のテキストの文字によってパターンをずらす幅を決めるものである.
まず， つぎの例を考えてみる.
【例題 9.2】
【一致しなかった テキストの文字が パターンに存在しない場合】
テキストとパターンが下図左のような位置にある場合を考える. 最初の比較はパターンの右端の文字’e’ とテキストの’a’
である. これはー致しないので，パターンを右にずらす.
このとき， テキスト上の文字’a’ はパターンに存在しないので，この’a’ の位置を含むような位置にパターンをずらして
も照合する可能性はない. この場合，パターンの長さ m = 10 だけ右にずらすことができる.
【一致しなかった テキストの文字が パターンのほかの位置にある場合】
テキストとパターンが下図右のような位置にある場合を考える. つまり，パターンの右端からの比較が進み，文字’r’
と’y’ の比較で不一致になったとする.
この場合は，パターン中の’y’ の位置を揃えるようにずらすことができる.
どちらの場合も，不一致がわかった時点で大幅にパターンを右にずらすことができる.
s ? ? ? ? ? ? ? ? ? ? y ? ? ? ? ? ? ? ? ? ? ? ?
p b o y e r m o o r e 不一致
p b o y e r m o o r e 不一致
.
.
.
p b o y e r m o o r e 不一致
p b o y e r m o o r e
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
5 / 30
1 つめの工夫の具体例による説明
一つめの工夫は，不一致となった位置のテキストの文字によってパターンをずらす幅を決めるものである.
まず， つぎの例を考えてみる.
【例題 9.2】
【一致しなかった テキストの文字が パターンに存在しない場合】
テキストとパターンが下図左のような位置にある場合を考える. 最初の比較はパターンの右端の文字’e’ とテキストの’a’
である. これはー致しないので，パターンを右にずらす.
このとき， テキスト上の文字’a’ はパターンに存在しないので，この’a’ の位置を含むような位置にパターンをずらして
も照合する可能性はない. この場合，パターンの長さ m = 10 だけ右にずらすことができる.
【一致しなかった テキストの文字が パターンのほかの位置にある場合】
テキストとパターンが下図右のような位置にある場合を考える. つまり，パターンの右端からの比較が進み，文字’r’
と’y’ の比較で不一致になったとする.
この場合は，パターン中の’y’ の位置を揃えるようにずらすことができる.
どちらの場合も，不一致がわかった時点で大幅にパターンを右にずらすことができる.
s ? ? ? ? ? ? ? ? ? ? a ? ? ? ? ? ? ? ? ? ? ? ?
p b o y e r m o o r e 不一致
p b o y e r m o o r e 不一致
s ? ? ? ? ? ? ? ? ? ? y ? ? ? ? ? ? ? ? ? ? ? ?
p b o y e r m o o r e 不一致
p b o y e r m o o r e 不一致
.
.
.
.
.
.
p b o y e r m o o r e 不一致
p b o y e r m o o r e
山崎浩一 (理工学部 電子情報理工学科)
p b o y e r m o o r e 不一致
p b o y e r m o o r e
文字列照合
Gunma Univ. 2015
5 / 30
1 つめの工夫の一般化した説明
テキストのi 番目の文字が’c’ であった (s[i] =’c’) として, 上述したことを一般化して考えてみる.
文字’c’ がパターン p の中に現れない場合 (i ≤ pos ≤ i + m − 1):
テキストの i 番目を含む長さ m の部分列はパターンと一致することはない.
pos−m+1
↓
s
pos
↓
i
i+m
↓
c
p
|
{z
m
p
}
m ずらす
文字’c’ がパターンの中に現れる場合 (その 1) (i ≤ pos ≤ i + m − j − 1):
パターンの最も右に現れる’c’ の位置を j とすると，テキストの i 番目を含む
長さ m − j の右からの部分列はパターンと一致することはない.
pos−m+1
↓
s
p
文字’c’ がパターンの中に現れる場合 (その 2) (i + m − j ≤ pos):
c
↑
j
p
pos−m+1
↓
s
このときはパターンを一つしかずらすことができない.
pos
↓
i
i+m−j
↙
c
c
i
|
{z
m−j
}
m − j ずらす
i+m−j pos
↙ ↙
c
p
c
p
c
p
後戻りさせない ×
c
一つずらす ⃝
以上の考察は，パターン p をテキストの s[pos − m + 1..pos] に置いて右端から比較していくとき，不一致があった時点で
パターンを大幅に右にずらす可能性を示唆している.
すなわち，不一致があったテキスト上の位置を i とすると. i に m あるいは m − j を加えた位置 にパターンの右端をずらし
て照合を再開できることを示している.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
6 / 30
1 つめの工夫の一般化した説明
テキストのi 番目の文字が’c’ であった (s[i] =’c’) として, 上述したことを一般化して考えてみる.
文字’c’ がパターン p の中に現れない場合 (i ≤ pos ≤ i + m − 1):
テキストの i 番目を含む長さ m の部分列はパターンと一致することはない.
pos−m+1
↓
s
pos
↓
i
i+m
↓
c
p
|
{z
m
p
}
m ずらす
文字’c’ がパターンの中に現れる場合 (その 1) (i ≤ pos ≤ i + m − j − 1):
パターンの最も右に現れる’c’ の位置を j とすると，テキストの i 番目を含む
長さ m − j の右からの部分列はパターンと一致することはない.
pos−m+1
↓
s
p
文字’c’ がパターンの中に現れる場合 (その 2) (i + m − j ≤ pos):
c
↑
j
p
pos−m+1
↓
s
このときはパターンを一つしかずらすことができない.
pos
↓
i
i+m−j
↙
c
c
i
|
{z
m−j
}
m − j ずらす
i+m−j pos
↙ ↙
c
p
c
p
c
p
後戻りさせない ×
c
一つずらす ⃝
以上の考察は，パターン p をテキストの s[pos − m + 1..pos] に置いて右端から比較していくとき，不一致があった時点で
パターンを大幅に右にずらす可能性を示唆している.
すなわち，不一致があったテキスト上の位置を i とすると. i に m あるいは m − j を加えた位置 にパターンの右端をずらし
て照合を再開できることを示している.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
6 / 30
1 つめの工夫の一般化した説明
テキストのi 番目の文字が’c’ であった (s[i] =’c’) として, 上述したことを一般化して考えてみる.
文字’c’ がパターン p の中に現れない場合 (i ≤ pos ≤ i + m − 1):
テキストの i 番目を含む長さ m の部分列はパターンと一致することはない.
pos−m+1
↓
s
pos
↓
i
i+m
↓
c
p
|
{z
m
p
}
m ずらす
文字’c’ がパターンの中に現れる場合 (その 1) (i ≤ pos ≤ i + m − j − 1):
パターンの最も右に現れる’c’ の位置を j とすると，テキストの i 番目を含む
長さ m − j の右からの部分列はパターンと一致することはない.
pos−m+1
↓
s
p
文字’c’ がパターンの中に現れる場合 (その 2) (i + m − j ≤ pos):
c
↑
j
p
pos−m+1
↓
s
このときはパターンを一つしかずらすことができない.
pos
↓
i
i+m−j
↙
c
c
i
|
{z
m−j
}
m − j ずらす
i+m−j pos
↙ ↙
c
p
c
p
c
p
後戻りさせない ×
c
一つずらす ⃝
以上の考察は，パターン p をテキストの s[pos − m + 1..pos] に置いて右端から比較していくとき，不一致があった時点で
パターンを大幅に右にずらす可能性を示唆している.
すなわち，不一致があったテキスト上の位置を i とすると. i に m あるいは m − j を加えた位置 にパターンの右端をずらし
て照合を再開できることを示している.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
6 / 30
1 つめの工夫の一般化した説明
テキストのi 番目の文字が’c’ であった (s[i] =’c’) として, 上述したことを一般化して考えてみる.
文字’c’ がパターン p の中に現れない場合 (i ≤ pos ≤ i + m − 1):
テキストの i 番目を含む長さ m の部分列はパターンと一致することはない.
pos−m+1
↓
s
pos
↓
i
i+m
↓
c
p
|
{z
m
p
}
m ずらす
文字’c’ がパターンの中に現れる場合 (その 1) (i ≤ pos ≤ i + m − j − 1):
パターンの最も右に現れる’c’ の位置を j とすると，テキストの i 番目を含む
長さ m − j の右からの部分列はパターンと一致することはない.
pos−m+1
↓
s
p
文字’c’ がパターンの中に現れる場合 (その 2) (i + m − j ≤ pos):
c
↑
j
p
pos−m+1
↓
s
このときはパターンを一つしかずらすことができない.
pos
↓
i
i+m−j
↙
c
c
i
|
{z
m−j
}
m − j ずらす
i+m−j pos
↙ ↙
c
p
c
p
c
p
後戻りさせない ×
c
一つずらす ⃝
以上の考察は，パターン p をテキストの s[pos − m + 1..pos] に置いて右端から比較していくとき，不一致があった時点で
パターンを大幅に右にずらす可能性を示唆している.
すなわち，不一致があったテキスト上の位置を i とすると. i に m あるいは m − j を加えた位置 にパターンの右端をずらし
て照合を再開できることを示している.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
6 / 30
1 つめの工夫の一般化した説明
テキストのi 番目の文字が’c’ であった (s[i] =’c’) として, 上述したことを一般化して考えてみる.
文字’c’ がパターン p の中に現れない場合 (i ≤ pos ≤ i + m − 1):
テキストの i 番目を含む長さ m の部分列はパターンと一致することはない.
pos−m+1
↓
s
pos
↓
i
i+m
↓
c
p
|
{z
m
p
}
m ずらす
文字’c’ がパターンの中に現れる場合 (その 1) (i ≤ pos ≤ i + m − j − 1):
パターンの最も右に現れる’c’ の位置を j とすると，テキストの i 番目を含む
長さ m − j の右からの部分列はパターンと一致することはない.
pos−m+1
↓
s
p
文字’c’ がパターンの中に現れる場合 (その 2) (i + m − j ≤ pos):
c
↑
j
p
pos−m+1
↓
s
このときはパターンを一つしかずらすことができない.
pos
↓
i
i+m−j
↙
c
c
i
|
{z
m−j
}
m − j ずらす
i+m−j pos
↙ ↙
c
p
c
p
c
p
後戻りさせない ×
c
一つずらす ⃝
以上の考察は，パターン p をテキストの s[pos − m + 1..pos] に置いて右端から比較していくとき，不一致があった時点で
パターンを大幅に右にずらす可能性を示唆している.
すなわち，不一致があったテキスト上の位置を i とすると. i に m あるいは m − j を加えた位置 にパターンの右端をずらし
て照合を再開できることを示している.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
6 / 30
BM 法での表 f
i に加える m あるいは m − j は, テキストに現れうる文字の集合とパターンによって定まる.
そこで，この値をすべての文字についてあらかじめ計算して表にしておくことができる.
この表を f {
とするとつぎのように定義できる. f の添字 c }は文字である.
f [c] = min {m} ∪ {j | 1 ≤ j ≤ m − 1, p[m − j] = c}
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
7 / 30
BM 法での表 f
i に加える m あるいは m − j は, テキストに現れうる文字の集合とパターンによって定まる.
そこで，この値をすべての文字についてあらかじめ計算して表にしておくことができる.
この表を f {
とするとつぎのように定義できる. f の添字 c }は文字である.
f [c] = min {m} ∪ {j | 1 ≤ j ≤ m − 1, p[m − j] = c}
【例題 9.3】
パターンを’boyermoore’ としたときの表 f を示す (e に注意).
c
f [c]
b
9
o
2
y
7
e
6
i+f [m]
i
↓
↓
s ? ? ? ? ? ? ? ? ? ? m ? ? ? ? ? ? ? ? ?
r
1
m
4
i+f [m]
i
↓
↓
s ? ? ? ? ? ? ? ? ? ? e ? ? ? ? ? ? ? ? ?
p b o y e r m o o r e
p b o y e r m o o r e
p b o y e r m o o r e
|
{z
}
p b o y e r m o o r e
|
{z
}
f [m]=4
山崎浩一 (理工学部 電子情報理工学科)
それ以外の文字
10
f [e]=6
文字列照合
Gunma Univ. 2015
7 / 30
BM 法での表 f
i に加える m あるいは m − j は, テキストに現れうる文字の集合とパターンによって定まる.
そこで，この値をすべての文字についてあらかじめ計算して表にしておくことができる.
この表を f {
とするとつぎのように定義できる. f の添字 c }は文字である.
f [c] = min {m} ∪ {j | 1 ≤ j ≤ m − 1, p[m − j] = c}
【例題 9.3】
パターンを’boyermoore’ としたときの表 f を示す (e に注意).
c
f [c]
b
9
o
2
y
7
e
6
i+f [m]
i
↓
↓
s ? ? ? ? ? ? ? ? ? ? m ? ? ? ? ? ? ? ? ?
r
1
m
4
それ以外の文字
10
i+f [m]
i
↓
↓
s ? ? ? ? ? ? ? ? ? ? e ? ? ? ? ? ? ? ? ?
p b o y e r m o o r e
p b o y e r m o o r e
p b o y e r m o o r e
|
{z
}
p b o y e r m o o r e
|
{z
}
f [m]=4
f [e]=6
bm-init-f
for テキスト中に現れうるすべての文字 c について do
f [c] := m;
for k := 1 to m − 1 do
f [p[k ]] = m − k ;
山崎浩一 (理工学部 電子情報理工学科)
/* p[k1 ] = p[k2 ] = · · · = p[kℓ ] のとき m − kℓ 方を採用 */
文字列照合
Gunma Univ. 2015
7 / 30
表 f を使った BM 法
表 f の計算法 (bm-init-f) と f を使った照合アルゴリズム (bm-simple-match) を示す. これまでの説
明でアルゴリズムの意味は明らかであろう.
bm-simple-match
i := m;
while i ≤ n do
k := m;
while (k > 0) and (p[k ] = s[i]) do
k := k − 1; i := i − 1;
if k = 0 then
return i + 1
/* 照合成功 */
else
i := i + max(f [s[i]], m − k + 1)
/* 後戻りしないよう大きい方を採用 */
/* テキスト中にパターンは存在しない */
return 0
i i+f [o]
↓
↓
s ? ? ? ? ? ? ? ? ? ? o ? ? ? ? ? ? ? ? ?
i
m−k +1
↓
↓
s ? ? ? ? ? ? ? ? ? ? o ? ? ? ? ? ? ? ? ?
k =6
↓
p b o y e r m o o r e
p b o y e r m o o r e
k =9
↓
p b o y e r m o o r e
p b o y e r m o o r e
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
8 / 30
表作成の計算量
表作成の手続き bm-init-f の時間計算量は，文字集合の大きさを σ とすると O(σ + m) である.
対象とする文字集合は固定されているので，理論的には σ は定数として扱われ，表 f の作成に要する時間
は O(m) ということができる.
実際，ASCII コードなど 1 バイト系の文字集合を対象としているときは，σ = 256(= 28 ) であり，σ は無
視できる. また，表 f の大きさも O(σ) であり，問題はない.
表 f を使った高速化は，パターンの右側で不一致があったとき，そして，パターンの長さが大きいときに効
果がある. 例えば，パターンの右端の比較でパターン中に存在しない文字が見つかれば，パターンを m だけ
右へずらすことができ，全体として n/m 回の比較しかしないこともありうる.
しかし，手続き bm-simple-match の
最悪の場合の時間計算量は，素朴なアルゴリズム simple-match と同じ O(mn) である.
テキストが’aa...a’ でパターンが’baa...a’ であるような場合に，比較の回数は m(n − m + 1) となり，最悪
の場合となる.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
9 / 30
二つめの工夫
高速化のための二つめの工夫について説明する. これは，
不一致が見つかるまでに一致していた部分の情報
を利用して高速化しようというものであり，考え方は KMP 法と同じである.
p[k ] と s[i] の比較で不一致があったとする. もちろん，パターンの右端から比較しているので，
p[k + 1..m] = s[i + 1..i + m − k ] である.
不一致があったのでパターンを j(j ≥ 1) だけ右へずらすとする.
すなわち，p = s[i − k + j + 1..i + m − k + j] であるかどうかを調べることになる.
i
↓
i+m−k
↓
k
↓
m
↓
s
p
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
10 / 30
二つめの工夫
高速化のための二つめの工夫について説明する. これは，
不一致が見つかるまでに一致していた部分の情報
を利用して高速化しようというものであり，考え方は KMP 法と同じである.
p[k ] と s[i] の比較で不一致があったとする. もちろん，パターンの右端から比較しているので，
p[k + 1..m] = s[i + 1..i + m − k ] である.
不一致があったのでパターンを j(j ≥ 1) だけ右へずらすとする.
すなわち，p = s[i − k + j + 1..i + m − k + j] であるかどうかを調べることになる.
i
↓
i+m−k
↓
k
↓
m
↓
s
p
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
10 / 30
二つめの工夫
高速化のための二つめの工夫について説明する. これは，
不一致が見つかるまでに一致していた部分の情報
を利用して高速化しようというものであり，考え方は KMP 法と同じである.
p[k ] と s[i] の比較で不一致があったとする. もちろん，パターンの右端から比較しているので，
p[k + 1..m] = s[i + 1..i + m − k ] である.
不一致があったのでパターンを j(j ≥ 1) だけ右へずらすとする.
すなわち，p = s[i − k + j + 1..i + m − k + j] であるかどうかを調べることになる.
i
↓
i+m−k
↓
k
↓
m
↓
s
p
j
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
10 / 30
二つめの工夫
高速化のための二つめの工夫について説明する. これは，
不一致が見つかるまでに一致していた部分の情報
を利用して高速化しようというものであり，考え方は KMP 法と同じである.
p[k ] と s[i] の比較で不一致があったとする. もちろん，パターンの右端から比較しているので，
p[k + 1..m] = s[i + 1..i + m − k ] である.
不一致があったのでパターンを j(j ≥ 1) だけ右へずらすとする.
すなわち，p = s[i − k + j + 1..i + m − k + j] であるかどうかを調べることになる.
i−k +j+1
↓
i
↓
i+m−k
↓
k
↓
m
↓
i+m−k +j
↓
s
p
k −j
↓
p
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
10 / 30
二つめの工夫 (続き)
このとき，ずらす幅によっては，絶対にパターンが照合しない場合がある.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
11 / 30
二つめの工夫 (続き)
このとき，ずらす幅によっては，絶対にパターンが照合しない場合がある.
m ≤ j の場合 (後の G3 (k )) は, 当然照合する必要がある (ずらしたパターンがそれまでに調べたテキストの
部分と重ならないので照合する可能性がある).
s
k
m
p
j
j
j (必ず照合が必要)
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
11 / 30
二つめの工夫 (続き)
このとき，ずらす幅によっては，絶対にパターンが照合しない場合がある.
m ≤ j の場合 (後の G3 (k )) は, 当然照合する必要がある (ずらしたパターンがそれまでに調べたテキストの
部分と重ならないので照合する可能性がある).
s
m
k
p
j
j
j (必ず照合が必要)
j < m の場合は，“1 ≤ j < k ” と “k ≤ j < m” の二つの場合に分けて考える.
s
s
k
↓
k
↓
p
p
j
山崎浩一 (理工学部 電子情報理工学科)
j
文字列照合
Gunma Univ. 2015
11 / 30
二つめの工夫 (続き:照合の必要がない場合)
1 ≤ j < k (後の G1 (k )) の場合: テキストの i 番目に置かれるのは p[k − j] である.
したがって，パターンを見て, 以下であれば 照合することはない (下図参照).
s[i + 1..i + m − k ] = p[k + 1..m] ̸= p[k − j + 1..m − j] または
s[i] ̸= p[k ] = p[k − j]
i
↓
i+m−k
↓
s
k
↓
p
k −j
j
山崎浩一 (理工学部 電子情報理工学科)
k −j+1 m−j
↘ ↓
↙
文字列照合
パターンだけで
計算できる
Gunma Univ. 2015
12 / 30
二つめの工夫 (続き:照合の必要がない場合)
1 ≤ j < k (後の G1 (k )) の場合: テキストの i 番目に置かれるのは p[k − j] である.
したがって，パターンを見て, 以下であれば 照合することはない (下図参照).
s[i + 1..i + m − k ] = p[k + 1..m] ̸= p[k − j + 1..m − j] または
s[i] ̸= p[k ] = p[k − j]
i
↓
i+m−k
↓
s
k
↓
p
k −j
j
k −j+1 m−j
↘ ↓
↙
パターンだけで
計算できる
k ≤ j < m(後の G2 (k )) の場合: パターンの先頭 p[1] が置かれるのはテキストの i + j − k + 1 番目である
(下図参照).
このとき，パターンを見て, 以下であれば 照合することはない.
s[i + j − k + 1..i + m − k ] = p[j + 1..m] ̸= p[1..m − j]
i i−k +j+1i+m−k
↓
↓ ↙
s
k
↓
p
m−j
↓
j
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
12 / 30
二つめの工夫 (続き:照合が必要となる可能性がある場合)
先程の考察から, 照合が必要となる可能性がある場合については, 先程の式の否定を考えればよい.
したがって, (パターンの k 番目で失敗したときに) j だけパターンをずらしたとすると，照合の可能性があ
るのはつぎのような集合 G(k ) に j が属するときである.
G(k ) = G1 (k ) ∪ G2 (k ) ∪ G3 (k )
G1 (k ) = {j | 1 ≤ j < k , p[k − j + 1..m − j] = p[k + 1..m], p[k − j] ̸= p[k ]} (下図左参照)
G2 (k ) = {j | k ≤ j < m, p[1..m − j] = p[j + 1..m]} (下図右参照)
G3 (k ) = {j | m ≤ j}
s
k
↓
m
↓
k −j
↓
m−j
↓
p
G1 (k )
G2 (k )
G3 (k )
j
m−j
↓
j
j (必ず照合が必要)
言い換えれば, G(k ) に属する j だけに気を配ればよい.
特に G(k ) の中の最小の要素 min(G(k)) に関心があり, min(G(k )) 分だけパターンを右にずらすことになる.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
13 / 30
表 g[1..m]
先の議論では, (パターンの k 番目で失敗したときに) パターンをどれだけずらせばよいか のずらすべき値
min(G(k)) = j について述べた.
ここでは, (パターンの k 番目での失敗に) テキストのヘッダ (ポインタ) をどれだけずらせばよいか のずら
すべき値 (それを g[k ] で表す) について述べる.
g[k ] は min(G(k )) = j と m − k の和なので,
g[k ] = m − k + min(G(k )) = m − k + min(G1 (k ) ∪ G2 (k ) ∪ G3 (k ))
つまり, 各 k に対して, パターンの k 番目で失敗したときに, テキストのヘッダ (ポインタ) をどれだけずら
せばよいかの値が表 g[1..m] に格納されている.
i
↓
i
↓
s
s
k
↓
k
↓
p
p
m
↓
m
↓
図: min(G(k )) = j と g[k ] の関係
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
14 / 30
表 g[1..m]
先の議論では, (パターンの k 番目で失敗したときに) パターンをどれだけずらせばよいか のずらすべき値
min(G(k)) = j について述べた.
ここでは, (パターンの k 番目での失敗に) テキストのヘッダ (ポインタ) をどれだけずらせばよいか のずら
すべき値 (それを g[k ] で表す) について述べる.
g[k ] は min(G(k )) = j と m − k の和なので,
g[k ] = m − k + min(G(k )) = m − k + min(G1 (k ) ∪ G2 (k ) ∪ G3 (k ))
つまり, 各 k に対して, パターンの k 番目で失敗したときに, テキストのヘッダ (ポインタ) をどれだけずら
せばよいかの値が表 g[1..m] に格納されている.
i
↓
i
↓
s
s
k
↓
k
↓
p
p
min(G(k ))
=j
m
↓
min(G(k ))
=j
m
↓
図: min(G(k )) = j と g[k ] の関係
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
14 / 30
表 g[1..m]
先の議論では, (パターンの k 番目で失敗したときに) パターンをどれだけずらせばよいか のずらすべき値
min(G(k)) = j について述べた.
ここでは, (パターンの k 番目での失敗に) テキストのヘッダ (ポインタ) をどれだけずらせばよいか のずら
すべき値 (それを g[k ] で表す) について述べる.
g[k ] は min(G(k )) = j と m − k の和なので,
g[k ] = m − k + min(G(k )) = m − k + min(G1 (k ) ∪ G2 (k ) ∪ G3 (k ))
つまり, 各 k に対して, パターンの k 番目で失敗したときに, テキストのヘッダ (ポインタ) をどれだけずら
せばよいかの値が表 g[1..m] に格納されている.
i
↓
i
↓
s
s
k
↓
k
↓
p
p
min(G(k ))
=j
m
↓
min(G(k ))
=j
m
↓
図: min(G(k )) = j と g[k ] の関係
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
14 / 30
表 g[1..m]
先の議論では, (パターンの k 番目で失敗したときに) パターンをどれだけずらせばよいか のずらすべき値
min(G(k)) = j について述べた.
ここでは, (パターンの k 番目での失敗に) テキストのヘッダ (ポインタ) をどれだけずらせばよいか のずら
すべき値 (それを g[k ] で表す) について述べる.
g[k ] は min(G(k )) = j と m − k の和なので,
g[k ] = m − k + min(G(k )) = m − k + min(G1 (k ) ∪ G2 (k ) ∪ G3 (k ))
つまり, 各 k に対して, パターンの k 番目で失敗したときに, テキストのヘッダ (ポインタ) をどれだけずら
せばよいかの値が表 g[1..m] に格納されている.
z
i
↓
g[k ]
}|
{
z
i+g[k ]=
i+m−k +j
↓
s
i
↓
g[k ]
}|
{
i+g[k ]=
i+m−k +j
↓
s
k
↓
k
↓
p
p
min(G(k ))
=j
m
↓
min(G(k ))
=j
m
↓
図: min(G(k )) = j と g[k ] の関係
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
14 / 30
表 g[1..m]
先の議論では, (パターンの k 番目で失敗したときに) パターンをどれだけずらせばよいか のずらすべき値
min(G(k)) = j について述べた.
ここでは, (パターンの k 番目での失敗に) テキストのヘッダ (ポインタ) をどれだけずらせばよいか のずら
すべき値 (それを g[k ] で表す) について述べる.
g[k ] は min(G(k )) = j と m − k の和なので,
g[k ] = m − k + min(G(k )) = m − k + min(G1 (k ) ∪ G2 (k ) ∪ G3 (k ))
つまり, 各 k に対して, パターンの k 番目で失敗したときに, テキストのヘッダ (ポインタ) をどれだけずら
せばよいかの値が表 g[1..m] に格納されている.
z
i
↓
g[k ]
}|
{
z
i+g[k ]=
i+m−k +j
↓
s
i
↓
g[k ]
}|
{
i+g[k ]=
i+m−k +j
↓
s
k
↓
k
↓
p
p
min(G(k ))
=j
m
↓
min(G(k ))
=j
m
↓
図: min(G(k )) = j と g[k ] の関係
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
14 / 30
表 g[1..m]
先の議論では, (パターンの k 番目で失敗したときに) パターンをどれだけずらせばよいか のずらすべき値
min(G(k)) = j について述べた.
ここでは, (パターンの k 番目での失敗に) テキストのヘッダ (ポインタ) をどれだけずらせばよいか のずら
すべき値 (それを g[k ] で表す) について述べる.
g[k ] は min(G(k )) = j と m − k の和なので,
g[k ] = m − k + min(G(k )) = m − k + min(G1 (k ) ∪ G2 (k ) ∪ G3 (k ))
つまり, 各 k に対して, パターンの k 番目で失敗したときに, テキストのヘッダ (ポインタ) をどれだけずら
せばよいかの値が表 g[1..m] に格納されている.
g[k ]
}|
z
{
i+g[k ]=
i+m−k +j
↓
i
↓
s
g[k ]
}|
z
{
i+g[k ]=
i+m−k +j
↓
i
↓
s
k
↓
p
min(G(k ))
=j
k
↓
min(G(k ))
=j
| {z }
m−k
p
m
↓
min(G(k ))
=j
min(G(k ))
=j
| {z }
m−k
m
↓
図: min(G(k )) = j と g[k ] の関係
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
14 / 30
表 g[1..m]
先の議論では, (パターンの k 番目で失敗したときに) パターンをどれだけずらせばよいか のずらすべき値
min(G(k)) = j について述べた.
ここでは, (パターンの k 番目での失敗に) テキストのヘッダ (ポインタ) をどれだけずらせばよいか のずら
すべき値 (それを g[k ] で表す) について述べる.
g[k ] は min(G(k )) = j と m − k の和なので,
g[k ] = m − k + min(G(k )) = m − k + min(G1 (k ) ∪ G2 (k ) ∪ G3 (k ))
つまり, 各 k に対して, パターンの k 番目で失敗したときに, テキストのヘッダ (ポインタ) をどれだけずら
せばよいかの値が表 g[1..m] に格納されている.
g[k ]
}|
z
{
i+g[k ]=
i+m−k +j
↓
i
↓
s
g[k ]
}|
z
{
i+g[k ]=
i+m−k +j
↓
i
↓
s
k
↓
p
min(G(k ))
=j
k
↓
min(G(k ))
=j
| {z }
m−k
p
m
↓
min(G(k ))
=j
min(G(k ))
=j
| {z }
m−k
m
↓
図: min(G(k )) = j と g[k ] の関係
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
14 / 30
表 g も用いた BM 法
直前に説明した表 g がすでに計算されているとすると，BM 法の照合アルゴリズムはつぎのようになる.
このアルゴリズムは，表 f を使った照合アルゴリズム bm-simple-match で
i := i + max(f [s[i]], m − k + 1) のところを i := i + max(f [s[i]], g[k]) に変更しただけである.
bm-match
i := m;
while i ≤ n do
k := m;
while (k > m) and (s[i] = p[k ]) do
k := k − 1; i := i − 1;
if k = 0 then
return i + 1
else
i := i + max(f [s[i]], g[k ])
/* 照合成功 */
/* bm-simple-match のこの部分を変更しただけ */
/* テキスト中にパターンは存在しない */
return 0
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
15 / 30
BM 法の処理時間
bm-match
i := m;
while i ≤ n do
k := m;
while (k > m) and (s[i] = p[k ]) do
k := k − 1; i := i − 1;
if k = 0 then
return i + 1
/* 照合成功 */
else
/* bm-simple-match のこの部分を変更しただけ */
i := i + max(f [s[i]], g[k ])
/* テキスト中にパターンは存在しない */
return 0
この照合アルゴリズムの計算時間は，最悪の場合でも n に比例することが知られている.
正確には，高々4n 回の比較で十分であるという証明が与えられている (文献 [B・14]). この計算時間の解析
は複雑であり，ここでは省略する.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
16 / 30
表 g[1..m] の作成方法
表 g の作成法は KMP 法の表 h の計算と似ている. そのアルゴリズムを以下に示す.
アルゴリズムでは，表 g の定義で述べた G(k ) を G3 (k ), G1 (k ), G2 (k ) に分けて計算している.
最初の for 文は 2m − k すなわち m − k + min(G3 (k )) を g[k] の初期値として代入している.
2 番目の for 文で min(G1 (k )) に対応する値を計算し，
最後の for 文で min(G2 (k )) に対応する値を計算している.
BM 法表 g の作成アルゴリズム
for k := 1 to m do
g[k ] := 2m − k;
{A1 : g[k ] := m − k + min(G3 (k ))};
k := m + 1;
for j := m downto 1 do
{I2 : ∀j ′ (j < j ′ ≤ m) g ′ [j ′ ] = g ′ (j ′ ) ∧ k = g ′ (j)};
{k = g ′ (k )};
g ′ [j] := k ;
while (k ≤ m) and (p[j] ̸= p[k ]) do
{I(k ) : (k = m + 1 ∨ k ∈ G′ (j)) ∧ ∀k ′ (k ′ < k )k ′ − 1 ̸∈ G′ (j − 1)};
g[k ] := min{g[k ], m − j} ;
k := g ′ [k ];
{k − 1 = g ′ (j − 1)};
k := k − 1 ;
/* 最小値の更新処理 */
/* 次の 1 つ小さい j に移るための準備 */
{A2 : g[k ] := m − k + min(G1 (k ) ∪ G3 (k ))};
l := k ;
for k := 1 to m do
{I3 : l = min(G2 (k ))};
g[k ] := min{g[k ], l + m − k};
if k ≥ l then l := g ′ [l];
{A3 : g[k ] := m − k + min(G2 (k ) ∪ G1 (k ) ∪ G3 (k ))};
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
17 / 30
最初の for 文
最初の for 文は 2m − k すなわち m − k + min(G3 (k)) を g[k ] の初期値として代入している.
m − k + min(G3 (k )) = 2m − k
∵ G3 (k ) = {j | m ≤ j} → min G3 (k ) = m
BM 法表 g の作成アルゴリズムの最初のループ
for k := 1 to m do
g[k ] := 2m − k;
i+(2m−k )
↓
i
↓
s
k
↓
p
min(G3 (k )) = m
| {z }
m−k
図: m − k + min(G3 (k )) = 2m − k の説明図
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
18 / 30
G′ , g ′
このアルゴリズムを理解する上で重要なのは, 補助表 g ′ [1..m] である. g ′ は次で定義される.
′
G (j) = {k | j < k ≤ m, p[k + 1..m] = p[j + 1..j + m − k ]}
′
′
g (j) = min(G (j) ∪ {m + 1})
j < m であれば m は必ず G′ (j) に含まれる. 実際定義の k のところに m を当てはめるてみると,
j < m ≤ m, p[m + 1..m] = 空の配列 = p[j + 1..j]
後に使うのでこの事実を性質 1 という呼び方で参照する.
j = m のときは G′ (j) は空集合なので g ′ (m) = m + 1 としている. 実際 j = m を定義に当てはめると,
′
G (m) = {k | m < k ≤ m, p[k + 1..m] = p[j + 1..j + m − k ]}
|
{z
}
空集合
j
↓
p
j+m−k2 j+m−k1
↙
↙
a a b a a b a a
p
k1 −j
z }| {
k1
↓
a a b a a b a a
k2 −j
k2
}|
{
↓
a a b a a b a a
k3 −j
k3
}|
{
↓
a a b a a b a a
k4 −j
k4 =m
}|
{
↓
a a b a a b a a
p
z
p
z
p
z
p
a a b a a b a a
↑
j
⇒
右詰め
a a b a a b a a
| {z }↖
k1
k1 −j
a a b a a b a a
|
{z
}↖
k2
k2 −j
a a b a a b a a
|
{z
}↖
k3
k3 −j
a a b a a b a a
|
{z
}↖
k4 =m
k4 −j
図: G′ (j) = {k1 , k2 , k3 , . . .} のイメージ
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
19 / 30
G′ , g ′
このアルゴリズムを理解する上で重要なのは, 補助表 g ′ [1..m] である. g ′ は次で定義される.
′
G (j) = {k | j < k ≤ m, p[k + 1..m] = p[j + 1..j + m − k ]}
′
′
g (j) = min(G (j) ∪ {m + 1})
j < m であれば m は必ず G′ (j) に含まれる. 実際定義の k のところに m を当てはめるてみると,
j < m ≤ m, p[m + 1..m] = 空の配列 = p[j + 1..j]
後に使うのでこの事実を性質 1 という呼び方で参照する.
j = m のときは G′ (j) は空集合なので g ′ (m) = m + 1 としている. 実際 j = m を定義に当てはめると,
′
G (m) = {k | m < k ≤ m, p[k + 1..m] = p[j + 1..j + m − k ]}
|
{z
}
空集合
j
↓
p
j+m−k2 j+m−k1
↙
↙
a a b a a b a a
p
k1 −j
z }| {
k1
↓
a a b a a b a a
k2 −j
k2
}|
{
↓
a a b a a b a a
k3 −j
k3
}|
{
↓
a a b a a b a a
k4 −j
k4 =m
}|
{
↓
a a b a a b a a
p
z
p
z
p
z
p
a a b a a b a a
↑
j
⇒
右詰め
a a b a a b a a
| {z }↖
k1
k1 −j
a a b a a b a a
|
{z
}↖
k2
k2 −j
a a b a a b a a
|
{z
}↖
k3
k3 −j
a a b a a b a a
|
{z
}↖
k4 =m
k4 −j
図: G′ (j) = {k1 , k2 , k3 , . . .} のイメージ
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
19 / 30
G′ , g ′
このアルゴリズムを理解する上で重要なのは, 補助表 g ′ [1..m] である. g ′ は次で定義される.
′
G (j) = {k | j < k ≤ m, p[k + 1..m] = p[j + 1..j + m − k ]}
′
′
g (j) = min(G (j) ∪ {m + 1})
j < m であれば m は必ず G′ (j) に含まれる. 実際定義の k のところに m を当てはめるてみると,
j < m ≤ m, p[m + 1..m] = 空の配列 = p[j + 1..j]
後に使うのでこの事実を性質 1 という呼び方で参照する.
j = m のときは G′ (j) は空集合なので g ′ (m) = m + 1 としている. 実際 j = m を定義に当てはめると,
′
G (m) = {k | m < k ≤ m, p[k + 1..m] = p[j + 1..j + m − k ]}
|
{z
}
空集合
j
↓
p
j+m−k2 j+m−k1
↙
↙
a a b a a b a a
p
k1 −j
z }| {
k1
↓
a a b a a b a a
k2 −j
k2
}|
{
↓
a a b a a b a a
k3 −j
k3
}|
{
↓
a a b a a b a a
k4 −j
k4 =m
}|
{
↓
a a b a a b a a
p
z
p
z
p
z
p
a a b a a b a a
↑
j
⇒
右詰め
a a b a a b a a
| {z }↖
k1
k1 −j
a a b a a b a a
|
{z
}↖
k2
k2 −j
a a b a a b a a
|
{z
}↖
k3
k3 −j
a a b a a b a a
|
{z
}↖
k4 =m
k4 −j
図: G′ (j) = {k1 , k2 , k3 , . . .} のイメージ
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
19 / 30
G′ , g ′ (続き)
G′ (j) の定義は G1 (k ) と似ている.
右端が j 個前と等しい
}|
{
z
G1 (k ) = {j | 1 ≤ j < k , p[k + 1 − j..m − j] = p[k + 1..m], p[k − j] ̸= p[k ]}
G′ (j) = {k | j < k ≤ m, p[k + 1..m] = p[j + 1..j + m − k ]}
g ′ (j) = min(G′ (j) ∪ {m + 1})
実際, 今は j < k を考えているので, k − j を考える事ができ, j を k − j だと思い G1 (k ) を書き直すと,
G1 (k ) = {k − j | 1 ≤ k − j < k , p[1 + j..m − k + j] = p[k + 1..m], p[j] ̸= p[k ]}
|
{z
}
G′ (j) の条件
故に, k − j ∈ G1 (k ) である必要十分条件は (k ∈ G′ (j) ∧ p[k ] ̸= p[j]) が成り立つこと1 である.
パターンの k1 番目 p[k] で失敗したので, p[k ] = p[j] ならパターンの j 番目 p[j] でも失敗することになる.
よって p[k ] ̸= p[j] でばければならない.
上図より, 「G′ (j) から k を求める」という視点と「G1 (k) から k − j を求める」という視点がある.
1
後に使うので, 後に参照するため事実 1 とする.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
20 / 30
G′ , g ′ (続き)
G′ (j) の定義は G1 (k ) と似ている.
右端が j 個前と等しい
}|
{
z
G1 (k ) = {j | 1 ≤ j < k , p[k + 1 − j..m − j] = p[k + 1..m], p[k − j] ̸= p[k ]}
G′ (j) = {k | j < k ≤ m, p[k + 1..m] = p[j + 1..j + m − k ]}
g ′ (j) = min(G′ (j) ∪ {m + 1})
実際, 今は j < k を考えているので, k − j を考える事ができ, j を k − j だと思い G1 (k ) を書き直すと,
G1 (k ) = {k − j | 1 ≤ k − j < k , p[1 + j..m − k + j] = p[k + 1..m], p[j] ̸= p[k ]}
|
{z
}
G′ (j) の条件
故に, k − j ∈ G1 (k ) である必要十分条件は (k ∈ G′ (j) ∧ p[k ] ̸= p[j]) が成り立つこと1 である.
パターンの k1 番目 p[k] で失敗したので, p[k ] = p[j] ならパターンの j 番目 p[j] でも失敗することになる.
よって p[k ] ̸= p[j] でばければならない.
上図より, 「G′ (j) から k を求める」という視点と「G1 (k) から k − j を求める」という視点がある.
1
後に使うので, 後に参照するため事実 1 とする.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
20 / 30
G′ , g ′ (続き)
G′ (j) の定義は G1 (k ) と似ている.
右端が j 個前と等しい
}|
{
z
G1 (k ) = {j | 1 ≤ j < k , p[k + 1 − j..m − j] = p[k + 1..m], p[k − j] ̸= p[k ]}
G′ (j) = {k | j < k ≤ m, p[k + 1..m] = p[j + 1..j + m − k ]}
g ′ (j) = min(G′ (j) ∪ {m + 1})
実際, 今は j < k を考えているので, k − j を考える事ができ, j を k − j だと思い G1 (k ) を書き直すと,
G1 (k ) = {k − j | 1 ≤ k − j < k , p[1 + j..m − k + j] = p[k + 1..m], p[j] ̸= p[k ]}
|
{z
}
G′ (j) の条件
故に, k − j ∈ G1 (k ) である必要十分条件は (k ∈ G′ (j) ∧ p[k ] ̸= p[j]) が成り立つこと1 である.
s ? ? ? ? ? ? ? ? ? x a a b a a b a a ? ? ? ?
k −j
↓
p
j
z }| {
p
s ? ? ? ? ? ? ? ? ? x a a b a a b a a ? ? ? ?
m−j j
↓ z }| {
a a b a a b a a
j
↓
p
k −j
z }| {
k
↓
a a b a a b a a
p
j+m−k
↓
a a b a a b a a
k
↓
a a b a a b a a
図: G′ (j) の視点
図: G1 (k ) の視点
パターンの k1 番目 p[k] で失敗したので, p[k ] = p[j] ならパターンの j 番目 p[j] でも失敗することになる.
よって p[k ] ̸= p[j] でばければならない.
上図より, 「G′ (j) から k を求める」という視点と「G1 (k) から k − j を求める」という視点がある.
1
後に使うので, 後に参照するため事実 1 とする.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
20 / 30
G′ , g ′ (続き)
G′ (j) の定義は G1 (k ) と似ている.
右端が j 個前と等しい
}|
{
z
G1 (k ) = {j | 1 ≤ j < k , p[k + 1 − j..m − j] = p[k + 1..m], p[k − j] ̸= p[k ]}
G′ (j) = {k | j < k ≤ m, p[k + 1..m] = p[j + 1..j + m − k ]}
g ′ (j) = min(G′ (j) ∪ {m + 1})
実際, 今は j < k を考えているので, k − j を考える事ができ, j を k − j だと思い G1 (k ) を書き直すと,
G1 (k ) = {k − j | 1 ≤ k − j < k , p[1 + j..m − k + j] = p[k + 1..m], p[j] ̸= p[k ]}
|
{z
}
G′ (j) の条件
故に, k − j ∈ G1 (k ) である必要十分条件は (k ∈ G′ (j) ∧ p[k ] ̸= p[j]) が成り立つこと1 である.
s ? ? ? ? ? ? ? ? ? x a a b a a b a a ? ? ? ?
k −j
↓
p
j
z }| {
p
s ? ? ? ? ? ? ? ? ? x a a b a a b a a ? ? ? ?
m−j j
↓ z }| {
a a b a a b a a
j
↓
p
k −j
z }| {
k
↓
a a b a a b a a
p
j+m−k
↓
a a b a a b a a
k
↓
a a b a a b a a
図: G′ (j) の視点
図: G1 (k ) の視点
パターンの k1 番目 p[k] で失敗したので, p[k ] = p[j] ならパターンの j 番目 p[j] でも失敗することになる.
よって p[k ] ̸= p[j] でばければならない.
上図より, 「G′ (j) から k を求める」という視点と「G1 (k) から k − j を求める」という視点がある.
1
後に使うので, 後に参照するため事実 1 とする.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
20 / 30
G′ , g ′ (続き)
G′ (j) の定義は G1 (k ) と似ている.
右端が j 個前と等しい
}|
{
z
G1 (k ) = {j | 1 ≤ j < k , p[k + 1 − j..m − j] = p[k + 1..m], p[k − j] ̸= p[k ]}
G′ (j) = {k | j < k ≤ m, p[k + 1..m] = p[j + 1..j + m − k ]}
g ′ (j) = min(G′ (j) ∪ {m + 1})
実際, 今は j < k を考えているので, k − j を考える事ができ, j を k − j だと思い G1 (k ) を書き直すと,
G1 (k ) = {k − j | 1 ≤ k − j < k , p[1 + j..m − k + j] = p[k + 1..m], p[j] ̸= p[k ]}
|
{z
}
G′ (j) の条件
故に, k − j ∈ G1 (k ) である必要十分条件は (k ∈ G′ (j) ∧ p[k ] ̸= p[j]) が成り立つこと1 である.
s ? ? ? ? ? ? ? ? ? x a a b a a b a a ? ? ? ?
k −j
↓
p
j
z }| {
p
s ? ? ? ? ? ? ? ? ? x a a b a a b a a ? ? ? ?
m−j j
↓ z }| {
a a b a a b a a
j
↓
p
k −j
z }| {
k
↓
a a b a a b a a
p
j+m−k
↓
a a b a a b a a
k
↓
a a b a a b a a
図: G′ (j) の視点
図: G1 (k ) の視点
パターンの k1 番目 p[k] で失敗したので, p[k ] = p[j] ならパターンの j 番目 p[j] でも失敗することになる.
よって p[k ] ̸= p[j] でばければならない.
上図より, 「G′ (j) から k を求める」という視点と「G1 (k) から k − j を求める」という視点がある.
1
後に使うので, 後に参照するため事実 1 とする.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
20 / 30
G′ , g ′ (続き)
k ∈ G′ (j) の例を下図に示す.
図からわかるように，g ′ (k) = g ′ (g ′ (j)) ∈ G′ (j) である.
一般に
′
′
′
′
G (j) = {k | k = g (g (· · · (g (j)) · · · )), k ̸= m + 1}
であることは帰納法で簡単に確かめられる 2 .
p
a a b a a b a a
↑
j
a a b a a b a
↑
k1
a a b a a b a
↑
k2
a a b a a b a
↑
k3
a a b a a b a
a
a
a
a
↑
k4 =m
図: G′ (j) の例
2
後に使うので, 後に参照するため事実 2 とする.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
21 / 30
2 回目の for 文 (m − j の意味)
g[k ] = m − k + min(G(k)) が最終目標だが, 2 回目の for 文の目標は,
g[k ] = m − k + min(G1 (k ) ∪ G3 (k)) を求めている.
[
]
2 回目の for 文では, k ∈ G′ (j) ∧ (p[k ] ̸= p[j]) を満たすすべての組 (k , j) である計算をしている.
事実 1 の k ∈ G′ (j) ∧ (p[k ] ̸= p[j]) ⇐⇒ k − j ∈ G1 (k ) に注意すると, 2 回目の for 文では実際に,
[
]
k − j ∈ G1 (k ) を満たすすべての組 (k , j) に対して m − j の最小値を計算している.
m − k + (k − j) = m − j に注意すると, while 文の min{g[k ], m − j} は以下から来ている:
g[k]
=
=
=
=
=
m − k + min(G1 (k ) ∪ G3 (k ))
(
)
′
′
′′
′′
min m − k + min{j : j ∈ G1 (k )}, m − k + min{j : j ∈ G3 (k )}
(
) ′
min m − k + min{k − j : k − j ∈ G1 (k)}, 2m − k
j を k からの相対位置で表現
(
)
min {m − j : k − j ∈ G1 (k )} ∪ {2m − k }
(
)
′
min {m − j : k ∈ G (j) ∧ (p[k ] ̸= p[j])} ∪ {2m − k }
BM 法表 g の作成アルゴリズム (2 回目の for 文)
k := m + 1;
for j := m downto 1 do
{I2 : ∀j ′ (j < j ′ ≤ m) g ′ [j ′ ] = g ′ (j ′ ) ∧ k = g ′ (j)};
g ′ [j] := k ;
while (k ≤ m) and (p[j] ̸= p[k ]) do
{I(k ) : (k = m + 1 ∨ k ∈ G′ (j)) ∧ ∀k ′ (k ′ < k )k ′ − 1 ̸∈ G′ (j − 1)};
g[k ] := min{g[k ], m − j};
k := g ′ [k ];
{k − 1 = g ′ (j − 1)};
k := k − 1
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
22 / 30
2 回目の for 文 (m − j の意味)
g[k ] = m − k + min(G(k)) が最終目標だが, 2 回目の for 文の目標は,
g[k ] = m − k + min(G1 (k ) ∪ G3 (k)) を求めている.
[
]
2 回目の for 文では, k ∈ G′ (j) ∧ (p[k ] ̸= p[j]) を満たすすべての組 (k , j) である計算をしている.
事実 1 の k ∈ G′ (j) ∧ (p[k ] ̸= p[j]) ⇐⇒ k − j ∈ G1 (k ) に注意すると, 2 回目の for 文では実際に,
[
]
k − j ∈ G1 (k ) を満たすすべての組 (k , j) に対して m − j の最小値を計算している.
m − k + (k − j) = m − j に注意すると, while 文の min{g[k ], m − j} は以下から来ている:
g[k]
=
=
=
=
=
m − k + min(G1 (k ) ∪ G3 (k ))
(
)
′
′
′′
′′
min m − k + min{j : j ∈ G1 (k )}, m − k + min{j : j ∈ G3 (k )}
(
) ′
min m − k + min{k − j : k − j ∈ G1 (k)}, 2m − k
j を k からの相対位置で表現
(
)
min {m − j : k − j ∈ G1 (k )} ∪ {2m − k }
(
)
′
min {m − j : k ∈ G (j) ∧ (p[k ] ̸= p[j])} ∪ {2m − k }
BM 法表 g の作成アルゴリズム (2 回目の for 文)
k := m + 1;
for j := m downto 1 do
{I2 : ∀j ′ (j < j ′ ≤ m) g ′ [j ′ ] = g ′ (j ′ ) ∧ k = g ′ (j)};
g ′ [j] := k ;
while (k ≤ m) and (p[j] ̸= p[k ]) do
{I(k ) : (k = m + 1 ∨ k ∈ G′ (j)) ∧ ∀k ′ (k ′ < k )k ′ − 1 ̸∈ G′ (j − 1)};
g[k ] := min{g[k ], m − j};
k := g ′ [k ];
{k − 1 = g ′ (j − 1)};
k := k − 1
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
22 / 30
2 回目の for 文 (m − j の意味)
g[k ] = m − k + min(G(k)) が最終目標だが, 2 回目の for 文の目標は,
g[k ] = m − k + min(G1 (k ) ∪ G3 (k)) を求めている.
[
]
2 回目の for 文では, k ∈ G′ (j) ∧ (p[k ] ̸= p[j]) を満たすすべての組 (k , j) である計算をしている.
事実 1 の k ∈ G′ (j) ∧ (p[k ] ̸= p[j]) ⇐⇒ k − j ∈ G1 (k ) に注意すると, 2 回目の for 文では実際に,
[
]
k − j ∈ G1 (k ) を満たすすべての組 (k , j) に対して m − j の最小値を計算している.
m − k + (k − j) = m − j に注意すると, while 文の min{g[k ], m − j} は以下から来ている:
g[k]
=
=
=
=
=
m − k + min(G1 (k ) ∪ G3 (k ))
(
)
′
′
′′
′′
min m − k + min{j : j ∈ G1 (k )}, m − k + min{j : j ∈ G3 (k )}
(
) ′
min m − k + min{k − j : k − j ∈ G1 (k)}, 2m − k
j を k からの相対位置で表現
(
)
min {m − j : k − j ∈ G1 (k )} ∪ {2m − k }
(
)
′
min {m − j : k ∈ G (j) ∧ (p[k ] ̸= p[j])} ∪ {2m − k }
BM 法表 g の作成アルゴリズム (2 回目の for 文)
k := m + 1;
for j := m downto 1 do
{I2 : ∀j ′ (j < j ′ ≤ m) g ′ [j ′ ] = g ′ (j ′ ) ∧ k = g ′ (j)};
g ′ [j] := k ;
while (k ≤ m) and (p[j] ̸= p[k ]) do
{I(k ) : (k = m + 1 ∨ k ∈ G′ (j)) ∧ ∀k ′ (k ′ < k )k ′ − 1 ̸∈ G′ (j − 1)};
g[k ] := min{g[k ], m − j};
k := g ′ [k ];
{k − 1 = g ′ (j − 1)};
k := k − 1
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
22 / 30
2 回目の for 文 (m − j の意味)
g[k ] = m − k + min(G(k)) が最終目標だが, 2 回目の for 文の目標は,
g[k ] = m − k + min(G1 (k ) ∪ G3 (k)) を求めている.
[
]
2 回目の for 文では, k ∈ G′ (j) ∧ (p[k ] ̸= p[j]) を満たすすべての組 (k , j) である計算をしている.
事実 1 の k ∈ G′ (j) ∧ (p[k ] ̸= p[j]) ⇐⇒ k − j ∈ G1 (k ) に注意すると, 2 回目の for 文では実際に,
[
]
k − j ∈ G1 (k ) を満たすすべての組 (k , j) に対して m − j の最小値を計算している.
m − k + (k − j) = m − j に注意すると, while 文の min{g[k ], m − j} は以下から来ている:
g[k]
=
=
=
=
=
m − k + min(G1 (k ) ∪ G3 (k ))
(
)
′
′
′′
′′
min m − k + min{j : j ∈ G1 (k )}, m − k + min{j : j ∈ G3 (k )}
(
) ′
min m − k + min{k − j : k − j ∈ G1 (k)}, 2m − k
j を k からの相対位置で表現
(
)
min {m − j : k − j ∈ G1 (k )} ∪ {2m − k }
(
)
′
min {m − j : k ∈ G (j) ∧ (p[k ] ̸= p[j])} ∪ {2m − k }
BM 法表 g の作成アルゴリズム (2 回目の for 文)
k := m + 1;
for j := m downto 1 do
{I2 : ∀j ′ (j < j ′ ≤ m) g ′ [j ′ ] = g ′ (j ′ ) ∧ k = g ′ (j)};
g ′ [j] := k ;
while (k ≤ m) and (p[j] ̸= p[k ]) do
{I(k ) : (k = m + 1 ∨ k ∈ G′ (j)) ∧ ∀k ′ (k ′ < k )k ′ − 1 ̸∈ G′ (j − 1)};
g[k ] := min{g[k ], m − j};
k := g ′ [k ];
{k − 1 = g ′ (j − 1)};
k := k − 1
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
22 / 30
2 番目の for 文 (I2 , I(k ) の意味)
2 番目の for 文の中にある I2 , I(k ) の意味は以下の通り.
′
′
′ ′
′ ′
I2 : ∀j (j < j ≤ m)
g [j ] = g (j )
|
{z
}
大きい世界は既に計算済み
′
I(k ) : (k = m + 1 ∨ k ∈ G (j))
|
{z
}
∧
k ∈G′ (j)∪{m+1}
′
∧
′
′
k = g (j)
| {z }
while 文の直前の
k は g ′ (j)
′
′
∀k (k < k ) k − 1 ∈
/ G (j − 1)
|
{z
}
k −1 は不明だが
′
k −2 以下は G (j−1) に属さない
BM 法表 g の作成アルゴリズム
for k := 1 to m do
g[k ] := 2m − k ;
k := m + 1;
for j := m downto 1 do
{I2 : ∀j ′ (j < j ′ ≤ m) g ′ [j ′ ] = g ′ (j ′ ) ∧ k = g ′ (j)};
g ′ [j] := k ;
/* g ′ の値はここで設定される */
while (k ≤ m) and (p[j] ̸= p[k ]) do
{I(k ) : (k = m + 1 ∨ k ∈ G′ (j)) ∧ ∀k ′ (k ′ < k )k ′ − 1 ̸∈ G′ (j − 1)};
g[k ] := min{g[k ], m − j};
k := g ′ [k ];
{k − 1 = g ′ (j − 1)};
k := k − 1
l := k ;
for k := 1 to m do
g[k ] := min{g[k ], l + m − k };
if k ≥ l then l := g ′ [l];
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
23 / 30
2 番目の for 文 (g ′ の計算過程のイメージ)
p
p
p
p
p
p
p
p
p
p
a
a a
a a a
a a a b
a
a a
a a a
a a a b
a a b a
a b a a
b a a b
a a b a
a
a
a
b
a
a
a a b
a
a b a
a
b a a
a
a a b
a b a
b
a
b a a
a b a a
b a a
a a
a
j=12
↓
a a b a a
a b a a
b a a
a a
a
p[j] = p[k ] ならば, 左図の行が変わ
らず, 左に平行にシフト. (後で参照す
るので「考察 1」と呼ぶことにする.)
p[j] = p[k ] ならば, 左図の行が変わ
り, 左下にシフト.
→
↓
j\k
m(= 12)
K3 (= 11)
k2 (= 10)
9
8
k1 (= 7)
6
j(= 5)
4
3
2
1
山崎浩一 (理工学部 電子情報理工学科)
m+1
✓
m(= 12)
11
10
文字列照合
9
8
7
6
5
4
Gunma Univ. 2015
24 / 30
2 番目の for 文 (g ′ の計算過程のイメージ)
p
p
p
p
p
p
p
p
p
p
a
a a
a a a
a a a b
a
a a
a a a
a a a b
a a b a
a b a a
b a a b
a a b a
a
a
a
b
a
a
a a b
a
a b a
a
b a a
a
a a b
a b a
b
a
b a a
a b a a
b a a
a a
a
j=11
↓
a a b a a
a b a a
b a a
a a
a
p[j] = p[k ] ならば, 左図の行が変わ
らず, 左に平行にシフト. (後で参照す
るので「考察 1」と呼ぶことにする.)
p[j] = p[k ] ならば, 左図の行が変わ
り, 左下にシフト.
→
↓
j\k
m(= 12)
K3 (= 11)
k2 (= 10)
9
8
k1 (= 7)
6
j(= 5)
4
3
2
1
山崎浩一 (理工学部 電子情報理工学科)
m+1
✓
m(= 12)
11
10
9
8
7
6
5
4
✓
文字列照合
Gunma Univ. 2015
24 / 30
2 番目の for 文 (g ′ の計算過程のイメージ)
p
p
p
p
p
p
p
p
p
p
a
a a
a a a
a a a b
a
a a
a a a
a a a b
a a b a
a b a a
b a a b
a a b a
a
a
a
b
a
a
a a b
a
a b a
a
b a a
a
a a b
a b a
b
a
b a a
a b a a
b a a
a a
a
j=10
↓
a a b a a
a b a a
b a a
a a
a
p[j] = p[k ] ならば, 左図の行が変わ
らず, 左に平行にシフト. (後で参照す
るので「考察 1」と呼ぶことにする.)
p[j] = p[k ] ならば, 左図の行が変わ
り, 左下にシフト.
→
↓
j\k
m(= 12)
K3 (= 11)
k2 (= 10)
9
8
k1 (= 7)
6
j(= 5)
4
3
2
1
山崎浩一 (理工学部 電子情報理工学科)
m+1
✓
m(= 12)
11
10
9
8
7
6
5
4
✓
✓
文字列照合
Gunma Univ. 2015
24 / 30
2 番目の for 文 (g ′ の計算過程のイメージ)
p
p
p
p
p
p
p
p
p
p
a
a a
a a a
a a a b
a
a a
a a a
a a a b
a a b a
a b a a
b a a b
a a b a
a
a
a
b
a
a
a a b
a
a b a
a
b a a
a
a a b
a b a
b
a
b a a
a b a a
b a a
a a
a
j=9
↓
a a b a a
a b a a
b a a
a a
a
p[j] = p[k ] ならば, 左図の行が変わ
らず, 左に平行にシフト. (後で参照す
るので「考察 1」と呼ぶことにする.)
p[j] = p[k ] ならば, 左図の行が変わ
り, 左下にシフト.
→
↓
j\k
m(= 12)
K3 (= 11)
k2 (= 10)
9
8
k1 (= 7)
6
j(= 5)
4
3
2
1
山崎浩一 (理工学部 電子情報理工学科)
m+1
✓
✓
m(= 12)
11
✓
✓
✓
✓
10
文字列照合
9
8
7
6
5
4
Gunma Univ. 2015
24 / 30
2 番目の for 文 (g ′ の計算過程のイメージ)
p
p
p
p
p
p
p
p
p
p
a
a a
a a a
a a a b
a
a a
a a a
a a a b
a a b a
a b a a
b a a b
a a b a
a
a
a
b
a
a
a a b
a
a b a
a
b a a
a
a a b
a b a
b
a
b a a
a b a a
b a a
a a
a
j=8
↓
a a b a a
a b a a
b a a
a a
a
p[j] = p[k ] ならば, 左図の行が変わ
らず, 左に平行にシフト. (後で参照す
るので「考察 1」と呼ぶことにする.)
p[j] = p[k ] ならば, 左図の行が変わ
り, 左下にシフト.
→
↓
j\k
m(= 12)
K3 (= 11)
k2 (= 10)
9
8
k1 (= 7)
6
j(= 5)
4
3
2
1
山崎浩一 (理工学部 電子情報理工学科)
m+1
✓
✓
m(= 12)
11
✓
✓
✓
✓
10
9
8
7
6
5
4
✓
文字列照合
Gunma Univ. 2015
24 / 30
2 番目の for 文 (g ′ の計算過程のイメージ)
p
p
p
p
p
p
p
p
p
p
a
a a
a a a
a a a b
a
a a
a a a
a a a b
a a b a
a b a a
b a a b
a a b a
j=7
↓
a a b a
a
a b a a
a
b a a b
a
a a b a
a b a a
b
a
b a a
a b a a
b a a
a a
a
a
a
a
b
a
a
a b a a
b a a
a a
a
p[j] = p[k ] ならば, 左図の行が変わ
らず, 左に平行にシフト. (後で参照す
るので「考察 1」と呼ぶことにする.)
p[j] = p[k ] ならば, 左図の行が変わ
り, 左下にシフト.
→
↓
j\k
m(= 12)
K3 (= 11)
k2 (= 10)
9
8
k1 (= 7)
6
j(= 5)
4
3
2
1
山崎浩一 (理工学部 電子情報理工学科)
m+1
✓
✓
m(= 12)
11
✓
✓
✓
✓
✓
10
9
8
7
6
5
4
✓
文字列照合
Gunma Univ. 2015
24 / 30
2 番目の for 文 (g ′ の計算過程のイメージ)
p
p
p
p
p
p
p
p
p
p
a
a a
a a a
a a a b
a
a a
a a a
a a a b
a a b a
a b a a
b a a b
a a b a
j=6
↓
a a b
a
a b a
a
b a a
a
a a b
a b a
b
a
b a a
a b a a
b a a
a a
a
a
a
a
b
a
a
a a b a a
a b a a
b a a
a a
a
p[j] = p[k ] ならば, 左図の行が変わ
らず, 左に平行にシフト. (後で参照す
るので「考察 1」と呼ぶことにする.)
p[j] = p[k ] ならば, 左図の行が変わ
り, 左下にシフト.
→
↓
j\k
m(= 12)
K3 (= 11)
k2 (= 10)
9
8
k1 (= 7)
6
j(= 5)
4
3
2
1
山崎浩一 (理工学部 電子情報理工学科)
m+1
✓
✓
m(= 12)
11
✓
✓
✓
✓
✓
10
✓
文字列照合
9
8
7
6
5
4
✓
Gunma Univ. 2015
24 / 30
2 番目の for 文 (g ′ の計算過程のイメージ)
p
p
p
p
p
a
a a
p
a a a
p
a a a b
p
a a a b a
p
a a a b a a
p
a
a a
a a a
a a b
a b a
b a a
a a b
a b a
b a a
j=5
↓
a a
a b
b a
a a
a b
b a
b a a
a a
a
a
a
a
b
a
a
b
a
a
b
a
a
a a b a a
a b a a
b a a
a a
a
p[j] = p[k ] ならば, 左図の行が変わ
らず, 左に平行にシフト. (後で参照す
るので「考察 1」と呼ぶことにする.)
p[j] = p[k ] ならば, 左図の行が変わ
り, 左下にシフト.
→
↓
j\k
m(= 12)
K3 (= 11)
k2 (= 10)
9
8
k1 (= 7)
6
j(= 5)
4
3
2
1
山崎浩一 (理工学部 電子情報理工学科)
m+1
✓
✓
m(= 12)
11
✓
✓
✓
✓
✓
10
✓
文字列照合
9
✓
8
7
6
5
4
✓
Gunma Univ. 2015
24 / 30
2 番目の for 文 (g ′ の計算過程のイメージ)
p
p
p
p
p
p
p
p
p
p
a
a a
a a a
a a a b
a
a a
a a a
a a a b
a a b a
a b a a
b a a b
a a b a
j=4
↓
a a
a a a
a a b
a b a
b a a
a a b
a b a
b a a
a a
a
a b a a b a a
b a a b a a
a a b a a
a b a a
b a a
a a
a
p[j] = p[k ] ならば, 左図の行が変わ
らず, 左に平行にシフト. (後で参照す
るので「考察 1」と呼ぶことにする.)
p[j] = p[k ] ならば, 左図の行が変わ
り, 左下にシフト.
→
↓
j\k
m(= 12)
K3 (= 11)
k2 (= 10)
9
8
k1 (= 7)
6
5
4
3
2
1
山崎浩一 (理工学部 電子情報理工学科)
m+1
✓
✓
m(= 12)
11
✓
✓
✓
✓
✓
10
✓
文字列照合
9
✓
8
✓
7
6
5
4
✓
Gunma Univ. 2015
24 / 30
2 番目の for 文 (g ′ の計算過程のイメージ)
j=3
↓
p
p
p
p
p
a
a a
p
a a a
p
a a a b
p
a a a b a
p
a a a b a a
p
a a a b
a a a b a
a a a b a a
a a a b a a b
a a b a a b a
a b a a b a a
b a a b a a
a a b a a
a b a a
b a a
a a b a a
a b a a
b a a
a a
a
p[j] = p[k ] ならば, 左図の行が変わ
らず, 左に平行にシフト. (後で参照す
るので「考察 1」と呼ぶことにする.)
p[j] = p[k ] ならば, 左図の行が変わ
り, 左下にシフト.
→
↓
j\k
m(= 12)
K3 (= 11)
k2 (= 10)
9
8
k1 (= 7)
6
5
j(= 4)
3
2
1
山崎浩一 (理工学部 電子情報理工学科)
m+1
✓
✓
m(= 12)
11
✓
✓
✓
✓
✓
✓
✓
✓
10
✓
✓
文字列照合
9
✓
8
✓
7
6
5
4
✓
Gunma Univ. 2015
24 / 30
2 番目の for 文 (g ′ の計算過程のイメージ)
j
↓
a a b a a b a a
p
k1 −j
z }| {
k1
↓
a a b a a b a a
k2 −j
k2
}|
{
↓
a a b a a b a a
k3 −j
k3
}|
{
↓
a a b a a b a a
k4 −j
k4 =m
}|
{
↓
a a b a a b a a
p
z
p
z
p
z
p
→
↓
j\k
m(= 12)
K3 (= 11)
k2 (= 10)
9
8
k1 (= 7)
6
j(= 5)
4
3
2
1
山崎浩一 (理工学部 電子情報理工学科)
m+1
✓
m(= 12)
11
10
9
8
7
6
5
4
✓
✓
✓
✓
✓
文字列照合
✓
✓
✓
Gunma Univ. 2015
25 / 30
2 番目の for 文 (g ′ の計算過程のイメージ)
p
k1 −j
z }| {
p
z
p
z
p
z
p
k2 −j
}|
j
↓
a a a b a a b a a
k1
↓
⇐
a a b a a b a a
k2
↓
⇐
b a a b a a
k3
↓
⇐
a a b a a
{
a a
k3 −j
}|
{
a a b
k4 −j
k4 =m
}|
{
↓
a a b a a b a a
→
↓
j\k
m(= 12)
K3 (= 11)
k2 (= 10)
9
8
k1 (= 7)
6
5
j(= 4)
3
2
1
山崎浩一 (理工学部 電子情報理工学科)
m+1
✓
m(= 12)
11
10
9
8
7
6
5
4
✓
✓
✓
✓
✓
✓
✓
✓
✓
文字列照合
✓
✓
✓
Gunma Univ. 2015
25 / 30
2 番目の for 文 (I(k ) が成り立つと仮定して g ′ が正しく計算されていることの確認)
先ず一番最初に for 文に入った時点では，k = m + 1，j = m であるので I2 は成立している.
次のループ (j − 1 の世界) に入った時点でも I2 が成立つことを示す. そのためには, while 文終了時点で
k − 1 = g ′ (j − 1) が成立していることを示せばよい.
何故なら, for 文の i ターン目を抜ける直前に k := k − 1 を実行し, 次の i + 1 ターンに入った直後に g ′ [j] := k を実
行しているからである. (i + 1 ターン目の j と k は, i ターン目の j − 1 と k − 1 に対応することに注意)
while 文を終了したとき I(k ) : (k = m + 1 ∨ k ∈ G′ (j)) ∧ ∀k ′ (k ′ < k )k ′ − 1 ̸∈ G′ (j − 1) が成立してい
ると仮定すれば, k − 1 = g ′ (j − 1) は次のようにして確かめられる.
while 文終了後には, while 文の脱出条件”(k > m) ∨ (p[j] = p[k ])” が成立している.
k > m であればk = m + 1(つまり k − 1 = m) であり，
さらに，I(m + 1) より ∀k ′ < m, k ′ ̸∈ G′ (j − 1) であり,
また性質 1 より, j − 1 ≤ m − 1 < m より G′ (j − 1) は m を含む.
′
′
よって G (j − 1) = {m} である. したがって，k − 1 = m = g (j − 1) である.
k ≤ m のときは，while 文の脱出条件と I(k ) が成り立っていることより以下が成り立つ.
k −1∈G′ (j−1)
k −1 が G′ (j−1) で最小
z
}|
{
z
}|
{
′
′ ′
′
′
(p[j] = p[k ]) ∧ (k ∈ G (j)) ∧ (∀k (k < k ) k − 1 ̸∈ G (j − 1))
|
{z
}
|
{z
}
I(k )
脱出条件
k − 1 ∈ G′ (j − 1) が成り立つ理由を各自考えてみよ. (ヒント:考察 1)
′
′
したがって，k − 1 ∈ G′ (j − 1) と k − 1 の最小性より, k − 1 = min(G (j − 1)) = g (j − 1) である.
|
{z
}
定義より
よって， while 文を終了した時点で，k − 1 = g ′ (j − 1) が成立している. 故に, g ′ が正しく計算されてい
ることが確認できた.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
26 / 30
2 番目の for 文 (I(k ) が成り立つと仮定して g ′ が正しく計算されていることの確認)
先ず一番最初に for 文に入った時点では，k = m + 1，j = m であるので I2 は成立している.
次のループ (j − 1 の世界) に入った時点でも I2 が成立つことを示す. そのためには, while 文終了時点で
k − 1 = g ′ (j − 1) が成立していることを示せばよい.
何故なら, for 文の i ターン目を抜ける直前に k := k − 1 を実行し, 次の i + 1 ターンに入った直後に g ′ [j] := k を実
行しているからである. (i + 1 ターン目の j と k は, i ターン目の j − 1 と k − 1 に対応することに注意)
while 文を終了したとき I(k ) : (k = m + 1 ∨ k ∈ G′ (j)) ∧ ∀k ′ (k ′ < k )k ′ − 1 ̸∈ G′ (j − 1) が成立してい
ると仮定すれば, k − 1 = g ′ (j − 1) は次のようにして確かめられる.
while 文終了後には, while 文の脱出条件”(k > m) ∨ (p[j] = p[k ])” が成立している.
k > m であればk = m + 1(つまり k − 1 = m) であり，
さらに，I(m + 1) より ∀k ′ < m, k ′ ̸∈ G′ (j − 1) であり,
また性質 1 より, j − 1 ≤ m − 1 < m より G′ (j − 1) は m を含む.
′
′
よって G (j − 1) = {m} である. したがって，k − 1 = m = g (j − 1) である.
k ≤ m のときは，while 文の脱出条件と I(k ) が成り立っていることより以下が成り立つ.
k −1∈G′ (j−1)
k −1 が G′ (j−1) で最小
z
}|
{
z
}|
{
′
′ ′
′
′
(p[j] = p[k ]) ∧ (k ∈ G (j)) ∧ (∀k (k < k ) k − 1 ̸∈ G (j − 1))
|
{z
}
|
{z
}
I(k )
脱出条件
k − 1 ∈ G′ (j − 1) が成り立つ理由を各自考えてみよ. (ヒント:考察 1)
′
′
したがって，k − 1 ∈ G′ (j − 1) と k − 1 の最小性より, k − 1 = min(G (j − 1)) = g (j − 1) である.
|
{z
}
定義より
よって， while 文を終了した時点で，k − 1 = g ′ (j − 1) が成立している. 故に, g ′ が正しく計算されてい
ることが確認できた.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
26 / 30
2 番目の for 文 (I(k ) が成り立つと仮定して g ′ が正しく計算されていることの確認)
先ず一番最初に for 文に入った時点では，k = m + 1，j = m であるので I2 は成立している.
次のループ (j − 1 の世界) に入った時点でも I2 が成立つことを示す. そのためには, while 文終了時点で
k − 1 = g ′ (j − 1) が成立していることを示せばよい.
何故なら, for 文の i ターン目を抜ける直前に k := k − 1 を実行し, 次の i + 1 ターンに入った直後に g ′ [j] := k を実
行しているからである. (i + 1 ターン目の j と k は, i ターン目の j − 1 と k − 1 に対応することに注意)
while 文を終了したとき I(k ) : (k = m + 1 ∨ k ∈ G′ (j)) ∧ ∀k ′ (k ′ < k )k ′ − 1 ̸∈ G′ (j − 1) が成立してい
ると仮定すれば, k − 1 = g ′ (j − 1) は次のようにして確かめられる.
while 文終了後には, while 文の脱出条件”(k > m) ∨ (p[j] = p[k ])” が成立している.
k > m であればk = m + 1(つまり k − 1 = m) であり，
さらに，I(m + 1) より ∀k ′ < m, k ′ ̸∈ G′ (j − 1) であり,
また性質 1 より, j − 1 ≤ m − 1 < m より G′ (j − 1) は m を含む.
′
′
よって G (j − 1) = {m} である. したがって，k − 1 = m = g (j − 1) である.
k ≤ m のときは，while 文の脱出条件と I(k ) が成り立っていることより以下が成り立つ.
k −1∈G′ (j−1)
k −1 が G′ (j−1) で最小
z
}|
{
z
}|
{
′
′ ′
′
′
(p[j] = p[k ]) ∧ (k ∈ G (j)) ∧ (∀k (k < k ) k − 1 ̸∈ G (j − 1))
|
{z
}
|
{z
}
I(k )
脱出条件
k − 1 ∈ G′ (j − 1) が成り立つ理由を各自考えてみよ. (ヒント:考察 1)
′
′
したがって，k − 1 ∈ G′ (j − 1) と k − 1 の最小性より, k − 1 = min(G (j − 1)) = g (j − 1) である.
|
{z
}
定義より
よって， while 文を終了した時点で，k − 1 = g ′ (j − 1) が成立している. 故に, g ′ が正しく計算されてい
ることが確認できた.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
26 / 30
2 番目の for 文 (I(k ) が成り立つと仮定して g ′ が正しく計算されていることの確認)
先ず一番最初に for 文に入った時点では，k = m + 1，j = m であるので I2 は成立している.
次のループ (j − 1 の世界) に入った時点でも I2 が成立つことを示す. そのためには, while 文終了時点で
k − 1 = g ′ (j − 1) が成立していることを示せばよい.
何故なら, for 文の i ターン目を抜ける直前に k := k − 1 を実行し, 次の i + 1 ターンに入った直後に g ′ [j] := k を実
行しているからである. (i + 1 ターン目の j と k は, i ターン目の j − 1 と k − 1 に対応することに注意)
while 文を終了したとき I(k ) : (k = m + 1 ∨ k ∈ G′ (j)) ∧ ∀k ′ (k ′ < k )k ′ − 1 ̸∈ G′ (j − 1) が成立してい
ると仮定すれば, k − 1 = g ′ (j − 1) は次のようにして確かめられる.
while 文終了後には, while 文の脱出条件”(k > m) ∨ (p[j] = p[k ])” が成立している.
k > m であればk = m + 1(つまり k − 1 = m) であり，
さらに，I(m + 1) より ∀k ′ < m, k ′ ̸∈ G′ (j − 1) であり,
また性質 1 より, j − 1 ≤ m − 1 < m より G′ (j − 1) は m を含む.
′
′
よって G (j − 1) = {m} である. したがって，k − 1 = m = g (j − 1) である.
k ≤ m のときは，while 文の脱出条件と I(k ) が成り立っていることより以下が成り立つ.
k −1∈G′ (j−1)
k −1 が G′ (j−1) で最小
z
}|
{
z
}|
{
′
′ ′
′
′
(p[j] = p[k ]) ∧ (k ∈ G (j)) ∧ (∀k (k < k ) k − 1 ̸∈ G (j − 1))
|
{z
}
|
{z
}
I(k )
脱出条件
k − 1 ∈ G′ (j − 1) が成り立つ理由を各自考えてみよ. (ヒント:考察 1)
′
′
したがって，k − 1 ∈ G′ (j − 1) と k − 1 の最小性より, k − 1 = min(G (j − 1)) = g (j − 1) である.
|
{z
}
定義より
よって， while 文を終了した時点で，k − 1 = g ′ (j − 1) が成立している. 故に, g ′ が正しく計算されてい
ることが確認できた.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
26 / 30
2 番目の for 文 (I(k ) が成り立つと仮定して g ′ が正しく計算されていることの確認)
先ず一番最初に for 文に入った時点では，k = m + 1，j = m であるので I2 は成立している.
次のループ (j − 1 の世界) に入った時点でも I2 が成立つことを示す. そのためには, while 文終了時点で
k − 1 = g ′ (j − 1) が成立していることを示せばよい.
何故なら, for 文の i ターン目を抜ける直前に k := k − 1 を実行し, 次の i + 1 ターンに入った直後に g ′ [j] := k を実
行しているからである. (i + 1 ターン目の j と k は, i ターン目の j − 1 と k − 1 に対応することに注意)
while 文を終了したとき I(k ) : (k = m + 1 ∨ k ∈ G′ (j)) ∧ ∀k ′ (k ′ < k )k ′ − 1 ̸∈ G′ (j − 1) が成立してい
ると仮定すれば, k − 1 = g ′ (j − 1) は次のようにして確かめられる.
while 文終了後には, while 文の脱出条件”(k > m) ∨ (p[j] = p[k ])” が成立している.
k > m であればk = m + 1(つまり k − 1 = m) であり，
さらに，I(m + 1) より ∀k ′ < m, k ′ ̸∈ G′ (j − 1) であり,
また性質 1 より, j − 1 ≤ m − 1 < m より G′ (j − 1) は m を含む.
′
′
よって G (j − 1) = {m} である. したがって，k − 1 = m = g (j − 1) である.
k ≤ m のときは，while 文の脱出条件と I(k ) が成り立っていることより以下が成り立つ.
k −1∈G′ (j−1)
k −1 が G′ (j−1) で最小
z
}|
{
z
}|
{
′
′ ′
′
′
(p[j] = p[k ]) ∧ (k ∈ G (j)) ∧ (∀k (k < k ) k − 1 ̸∈ G (j − 1))
|
{z
}
|
{z
}
I(k )
脱出条件
k − 1 ∈ G′ (j − 1) が成り立つ理由を各自考えてみよ. (ヒント:考察 1)
′
′
したがって，k − 1 ∈ G′ (j − 1) と k − 1 の最小性より, k − 1 = min(G (j − 1)) = g (j − 1) である.
|
{z
}
定義より
よって， while 文を終了した時点で，k − 1 = g ′ (j − 1) が成立している. 故に, g ′ が正しく計算されてい
ることが確認できた.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
26 / 30
2 番目の for 文 (I(k ) が不変量であることの確認)
I(k ) : (k = m + 1 ∨ k ∈ G′ (j)) ∧ ∀k ′ (k ′ < k)k ′ − 1 ̸∈ G′ (j − 1) を示すために以下を示す.
1
【while 文の直前で g ′ [j] = k 】⇒ 【while 文の直前で I(k )】と,
2
【p[j] ̸= p[k], I(k )】⇒ I(g ′ [k ])
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
27 / 30
2 番目の for 文 (I(k ) が不変量であることの確認)
I(k ) : (k = m + 1 ∨ k ∈ G′ (j)) ∧ ∀k ′ (k ′ < k)k ′ − 1 ̸∈ G′ (j − 1) を示すために以下を示す.
1
【while 文の直前で g ′ [j] = k 】⇒ 【while 文の直前で I(k )】と,
2
【p[j] ̸= p[k], I(k )】⇒ I(g ′ [k ])
while 文の直前で g ′ [j] = k = g ′ (j) が成立するとする. このとき, while 文の直前で I(k ) は成立している.
何故なら:
g ′ (j) の性質より k = min(G′ (j) ∪ {m + 1}) である. よって I(k ) の前半が成立.
また， k が (g ′ (j) の) 最小値であることから ∀k ′ (k ′ < k ) k ′ − 1 ̸∈ G′ (j − 1) も成り立つ.(各自理由を考えてみよ
う) よって I(k ) の後半が成立.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
27 / 30
2 番目の for 文 (I(k ) が不変量であることの確認)
I(k ) : (k = m + 1 ∨ k ∈ G′ (j)) ∧ ∀k ′ (k ′ < k)k ′ − 1 ̸∈ G′ (j − 1) を示すために以下を示す.
1
【while 文の直前で g ′ [j] = k 】⇒ 【while 文の直前で I(k )】と,
2
【p[j] ̸= p[k], I(k )】⇒ I(g ′ [k ])
p[j] ̸= p[k], I(k ) が成立, を仮定. このとき, k ≤ m より k ∈ G′ (j)(I(k ) の最初の条件) に注意.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
27 / 30
2 番目の for 文 (I(k ) が不変量であることの確認)
I(k ) : (k = m + 1 ∨ k ∈ G′ (j)) ∧ ∀k ′ (k ′ < k)k ′ − 1 ̸∈ G′ (j − 1) を示すために以下を示す.
1
【while 文の直前で g ′ [j] = k 】⇒ 【while 文の直前で I(k )】と,
2
【p[j] ̸= p[k], I(k )】⇒ I(g ′ [k ])
p[j] ̸= p[k], I(k ) が成立, を仮定. このとき, k ≤ m より k ∈ G′ (j)(I(k ) の最初の条件) に注意.
まず，(g ′ [k ] = m + 1) ∨ (g ′ [k ] ∈ G′ (j)) であること (I(g ′ [k ]) の前半が成り立つこと) を示す.
∀j < j ′ ≤ m, g ′ [j ′ ] には正しい値が入っている, すなわち g ′ [j ′ ] = min{G′ (j ′ ) ∪ {m + 1}} が成り立ってることに
注意.
k ∈ G′ (j) より j < k . よって, g ′ [k ] = min{G′ (k ) ∪ {m + 1}}, したがって g ′ [k] ̸= m + 1 ならば g ′ [k ] ∈ G′ (k )
が成り立つ.
g ′ [k ] = m + 1 のときは明らかなので, G′ (k ) ̸= m + 1 のときについて考える.
このとき g ′ [k ] ∈ G′ (k ) より，p[g ′ [k ] + 1..m] = p[k + 1..k + m − g ′ [k ]] であり，
k ∈ G′ (j) より p[k + 1..m] = p[j + 1..j + m − k ] である.
よって，p[g ′ [k ] + 1..m] = p[k + 1..k + m − g ′ [k]] = p[j + 1..j + m − g ′ [k ]] が成立し，以下が成立つ.
′
′
g [k] ∈ G (j) = {k | j < k ≤ m, p[k + 1..m] = p[j + 1..j + m − k ]}
g ′ [k ]
↓
m
↓
k
↓
k +m−g ′ [k ]
↓
j
↓
j+m−g ′ [k ] j+m−k
↓
↓
p
p
p
p
図:
山崎浩一 (理工学部 電子情報理工学科)
g ′ [k ] ∈ G′ (j) の説明
文字列照合
Gunma Univ. 2015
27 / 30
2 番目の for 文 (I(k ) が不変量であることの確認)
I(k ) : (k = m + 1 ∨ k ∈ G′ (j)) ∧ ∀k ′ (k ′ < k)k ′ − 1 ̸∈ G′ (j − 1) を示すために以下を示す.
1
【while 文の直前で g ′ [j] = k 】⇒ 【while 文の直前で I(k )】と,
2
【p[j] ̸= p[k], I(k )】⇒ I(g ′ [k ])
p[j] ̸= p[k], I(k ) が成立, を仮定. このとき, k ≤ m より k ∈ G′ (j)(I(k ) の最初の条件) に注意.
つぎに ∀k ′ (k ′ < g ′ [k ]) k ′ − 1 ̸∈ G′ (j − 1)(I(g ′ [k ]) の後半が成り立つこと) を示す.
k ′ < k である k ′ については, I(k ) を仮定しているので 成り立つ.
k ′ = k のときには，p[k ′ ] = p[k ] ̸= p[j](つまり p[k ′ ] ̸= p[j]) なので，k ′ − 1 ̸∈ G′ (j − 1) である.
k < k ′ < g ′ [k ] を考える.
この場合，j < k より g ′ [k ] = min{G′ (k ) ∪ {m + 1}}.
よって, k ′ < g ′ [k ] より (最小値未満なので)k ′ ̸∈ G′ (k ) となり, p[k ′ + 1..m] ̸= p[k + 1..k + m − k ′ ].
一方，I(k ) が成り立っているので, k ∈ G′ (j) が成り立ち, よって p[k + 1..m] = p[j + 1..j + m − k ] である. 故に,
p[k ′ + 1..m] ̸= p[k + 1..k + m − k ′ ] = p[j + 1..j + m − k ′ ] である. (赤の点線を参照)
したがってこの場合も k ′ − 1 ̸∈ G′ (j − 1) である.
k
↓
k +m−k ′
↓
k
↓
k′
↓
m
↓
j
↓
j+m−k ′ j+m−k
↓
↓
p
p
p
p
図: p[k ′ + 1..m] ̸=
以上で， I(k ) が不変量であることが示された.
山崎浩一 (理工学部 電子情報理工学科)
p[j + 1..j + m − k ′ ] の説明
文字列照合
Gunma Univ. 2015
27 / 30
3 番目の for 文
つぎに，最後の for 文について説明する. ここでは，min(G2 (k )) に対応する計算を行っている. 2 番目の for
文が終了した直後に l に k を代入している. for 文, while 文の終了条件と不変量 I(k ) を考慮すると,
l = min(G′ (0)) である.
G′ (j) = {k | j < k ≤ m, p[k + 1..m] = p[j + 1..j + m − k ]} より,
G′ (0) = {k | 0 < k ≤ m, p[k + 1..m] = p[1..m − k ]} は, パターンの後半と前半が等しくなる添え字の
集合である.
したがって, l = min(G′ (0)) は p[l + 1..m] = p[1..m − l] を満たす最小の値である.
よって, G2 (k) = {j | k ≤ j < m, p[1..m − j] = p[j + 1..m]} より, l(= min G′ (0)) = min(G2 (1)).
G′ (0) = {k | 0 < k ≤ m, p[k + 1..m] = p[1..m − k ]}
G2 (1) = {j | 1 ≤ j < m, p[1..m − j] = p[j + 1..m]}
l+1
↓
m
↓
1
↓
m−l
↓
p
l
m
↓
G2 の定義より，1 ≤ k ≤ l であるすべての k に対して min(G2 (k )) = l(= min G2 (1)) である.
G2 (k ) = {j | k ≤ j < m, p[1..m − j] = p[j + 1..m]} より, j として l が取れるので, l ∈ G2 (k) となる.
この後すぐに述べるが, k ≤ l から l < k に状態が変化すると min(G2 (k )) = l の更新が必要となる.
一般に， G2 は G′ (0) を使ってつぎのように記述できる.
′
G2 (k ) = {j | k ≤ j < m, j ∈ G (0)}
′
すなわち，min(G2 (k )) は k 以上で最小の G (0) の要素である. 一方，事実 1 より, G′ (0) のすべての要素
は，l = g ′ (0) < g ′ (l) < g ′ (g ′ (l)) < · · · のようにたどることができる.
表作成アルゴリズムの最後の for 文は，以上の考えをそのままアルゴリズムとしたものである.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
28 / 30
3 番目の for 文 (続き)
この for 文の不変量 I3 は l = min(G2 (k )) である.
′
′
′
′
′
′
l = min(G2 (k )) ならば G2 (k ) = {l, g (l), g (g (l)), · · · , g (g (· · · (g (l)) · · · ))} に注意.
|
{z
}
k 以上で G′ (0) に属する元
k のインクリメントが進むといずれ k が l を超えるが, (l はそのままで) その新しい k に対し,
′
′
′
′
′
′
G2 (新しい k) = {g (l), g (g (l)), · · · , g (g (· · · (g (l)) · · · ))} となる.
|
{z
}
(新しい)k 以上で G′ (0) に属する元
上述を踏まえて考えると, if 文で k が l を超えるときに g ′ [l] = min(G2 (k + 1)) を新しい l としているの
で，l = min(G2 (k )) は確かに不変量である.
l = min(G2 (k )) が成り立っていれば，g[k ] への代入文”g[k ] := min{g[k], m − k + l}"で，
g[k ] = m − k + min{G2 (k ) ∪ G1 (k) ∪ G3 (k )} が計算されていることは明らかである.
以上で，表 g の作成アルゴリズム bm-init-g が正しく動作することが示された.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
29 / 30
表作成の時間計算量
BM 法表 g の作成アルゴリズム
for k := 1 to m do
g[k ] := 2m − k;
k := m + 1;
for j := m downto 1 do
g ′ [j] := k ;
while (k ≤ m) and (p[j] ̸= p[k ]) do
g[k ] := min{g[k ], m − j}; k := g ′ [k ];
k := k − 1
l := k ;
for k := 1 to m do
g[k ] := min{g[k ], l + m − k};
if k ≥ l then l := g ′ [l];
表の作成にかかる時間計算量について調べる.
最初と最後の for 文はそれぞれ m 回の繰り返しがあるだけである.
2 番目の for 文について考える. 内側の while 文の比較”p[j] ̸= p[k ]” の実行回数は，”k := g ′ [k ]” による k
の増加の回数と”k := k − 1” による減少の回数の和である.
k の範囲は 1 ≤ k ≤ m + 1 であり，減少が高々m 回しか実行されないことから，比較の回数は O(m) で
ある. したがってこのアルゴリズムの時間計算量は O(m) である.
定理 9.2
Boyer-Moore のアルゴリズムにより，文字列照合問題は O(m + n) の時間計算量で解くことができ
る. ここで，m はパターンの長さ，n はテキストの長さである.
山崎浩一 (理工学部 電子情報理工学科)
文字列照合
Gunma Univ. 2015
30 / 30
© Copyright 2024 ExpyDoc
