Knuth-Morris-Pratt algorithm - コードの恵み

WEB-DB PRESS Vol.66 に文字列検索のアルゴリズムが載っていたので、検索していたら気づいたこと

今まで Boyer-Moore だと思っていたものは Boyer-Moore-Horspool だった
KMP 法のプログラムはシンプルなのに読めない

KMP 法については日本語で書かれたわかり易い説明を見つけられなかったので久しぶりにエントリを書いてみる。
正確さより直感的に理解できる感じで...多分

KMP 法の解説で自分にとってわかり易かったのはここ

Knuth-Morris-Pratt algorithm

KMP 法を理解する手順

border の概念を理解する
border が文字列検索でどう役立つのかを理解する
border を効率的に求める方法を理解する

border とは

ある文字列の prefix と suffix が一致している場合、一致している prefix と suffix をその文字列の border と呼ぶ
ただし prefix と suffix は重複する部分があってもよいが一致していてはいけない
border が空文字でも OK
空文字には border が存在しない
最も幅広い border を tagged border と呼ぶ

文章より例を見た方が早いので
例) tagged border を返す関数を taggedBorderOf とすると

assert taggedBorderOf("ababaa") == "a"
assert taggedBorderOf("ababa") == "aba" // prefix と suffix で a を共有している
assert taggedBorderOf("abab") == "ab"
assert taggedBorderOf("aba") == "a"
assert taggedBorderOf("ab") == ""       // border が空文字の場合もある
assert taggedBorderOf("a") == ""
assert taggedBorderOf("") == null       // 空文字に border は存在しない

border の持つ性質

ある文字列の border の border もまたある文字列の border である

例) 引数の文字列のすべての border を返す関数を bordersOf とすると

assert bordersOf("aabaa") == ["aa", "a", ""]
assert bordersOf("aa") == ["a", ""]
assert bordersOf("a") == [""]
// border は再帰的な構造になっている
assert bordersOf("aabaa") == ["aa", *bordersOf("aa")]

文字列検索で border を活用する

border の prefix 側と suffix 側は同じ文字列であることを利用する

pattern[j] で照合に失敗した場合、次の照合開始位置は pattern[0..

//        i
//...aabaa?...    text    (text[i] != pattern[j])
//   aabaab       pattern (この位置で不一致だった場合、次にどの位置から照合を始めればよいか?)
//        j
//   aabaa の border の prefix を suffix の位置に移動するので pattern[border.size()] を調べる
//      aabaab    border "aa" の場合 text[i] を pattern[2] と比較
//       aabaab   border "a"  の場合 text[i] を pattern[1] と比較
//        aabaab  border ""   の場合 text[i] を pattern[0] と比較

pattern[0..i] の tagged border を求める

i までの tagged border は i-1 までの border に1文字足したものか空文字である

例) "aabaa" までの tagged border が分かっていて "aabaa?" の tagged border を求める場合

//      i
// aabaa?
// aabaa? の tagged border は aabaa の border に1文字加えたものか空文字である
//    aabaa    border "aa" の場合 ? == pattern[2] であれば tagged border は "aab"
//     aabaa   border "a"  の場合 ? == pattern[1] であれば tagged border は "aa"
//      aabaa  border ""   の場合 ? == pattern[0] であれば tagged border は "a" (この pattern ではありえない)
// それでも一致しない(例えば "aabaac")場合 tagged border は ""

"aabaa" の border の prefix 側+1文字を "aabaa?" の suffix と一致させることなので先程の文字列検索と同じ処理になる。

KMP法のソースコードを読む

参考にしたサイトのソースを Groovy で書き直してコメントを追加したもの

// i は pattern の照合開始位置
int kmp_search(text, pattern, int i=0) {
  final int N = text.size()
  final int M = pattern.size()
  // pattern が空文字の場合、i を返す仕様とする
  if (M == 0) return i
  // b[j] := taggedBorderOf(pattern[0..<j]).size()
  // b[0] := -1 (border が存在しない場合。インクリメントして 0 になるので都合がよい) 
  def b = kmp_table(pattern)
  int j = 0
  while (i < N) {
    // text[i] が pattern に含まれる場合の pattern の位置を探す
    // border の再帰的な構造を利用して繰り返す
    while (j >= 0 && text[i] != pattern[j]) j = b[j]
    i++
    j++
    // pattern が見つかれば pattern の開始位置を返す
    if (j == M) return i-j
  }
  return -1
}

// pattern[0..i] の tagged border の size を求める
def kmp_table(pattern) {
  final int M = pattern.size()
  // kmp_search では b[M-1] までしか参照しないが中途半端なので b[M] まで調べておく
  def b = new int[M+1]
  int i = 0
  // j は border size
  int j = -1
  // 空文字の border は存在しないが、-1 を設定しておくと border が存在するしないの分岐がなくなって都合がよい
  b[i] = j
  while (i < M) {
    // pattern[0..<i] の border に1文字足して pattern[0..i] の border にならないか調べる
    while (j >= 0 && pattern[i] != pattern[j]) j = b[j]
    // pattern[0..<i] の border に1文字足したら　pattern[0..i] の border になった -> j = j+1
    // そんな border は見つからなかった -> j = 0
    i++
    j++
    b[i] = j
  }
  return b
}

assert kmp_search("aaabaabaaa", "aabaab") == 1
assert kmp_table("aabaab") == [-1,0,1,0,1,2,3]

自分の場合 KMP 法で意味が分からなかった部分は border を再帰的に処理するところだった。
文字列検索のアルゴリズムでは実装によって i が照合中の文字の位置だったり、pattern の照合開始位置だったりするので注意が必要だけれども他の実装も読めるようになっているはず。

kmp_table からあり得ない場合を取り除く

他の実装を読んでいるともう少し kmp_table を効率化してある場合があった。

def kmp_table(pattern) {
  final int M = pattern.size()
  def b = new int[M+1]
  int i = 0
  int j = -1
  b[i] = j
  while (i < M) {
    while (j >= 0 && pattern[i] != pattern[j]) j = b[j]
    i++
    j++
    // pattern[0..j] == "aaba" の場合で考える
    // "aab" の border は "" だと分かったが、もし "aaba" であれば
    // ...aab?...  text[i] == ?
    //    aaba     で不一致だった場合
    //       aaba  次の比較位置のはずだが("aab" の border は "")
    //        aaba ? != 'a' であるこが分かっているのでさらに次の border を調べる("" の border は null)
    b[i] = i < M && pattern[i] == pattern[j] ? b[j] : j
  }
  return b
}
// 戻り値は tagged border の size ではなく、次に一致する可能性のある border の size になる
assert kmp_table("aabaab") == [-1,-1, 1,-1,-1, 1, 3]

最後に

最近プログラミングの勉強をあまりしていなかったが、理解できるようになることは楽しいということを思い出した。

「プログラミングとは理解することである」
― Kristen Nygaard

ストラウストラップのプログラミング入門第6章より引用