1990年, Daniel M. Sundayの論文 http://dl.acm.org/citation.cfm?id=79184
Boyer-Mooreアルゴリズムより高速な部分文字列検索アルゴリズムを提案している。
- Quick Search(QS)
- Maximal Shift(MS)
- Optimal Mismatch(OM) の3つ。 これらはパターン文字列の処理がどちらの方向からでもできるのが特徴
KMP(Knuth-Morris-Pratt), BM(Boyer-Moore)などのSF(straight forward)よりも高速なアルゴリズムは検索するパターン文字列の前処理を必要とする。 この論文で紹介する3つのアルゴリズムはどちらの方向からでもスキャンでき、BMより高速なアルゴリズム。
検索対象のtext, 検索する文字列patternに出現しうる全ての文字をキーとした配列を用意する。 text, patternの比較を行った結果から、次の比較場所へ移動する量をこの配列から決定する。 こうすることで、pattern文字列のどの文字からでも比較することが可能になり(in any particular order)、単純に比較する(QS)や英単語に出現する頻度の高い文字の位置から検索する(OM)など比較する順序の違いで、論文中の3つのアルゴリズムが紹介されている。
論文中ではUNIXのspelling dictionary file(/usr/dict/words)に出てくる英単語をつなげた文字列と、UNIXマニュアルページの文章をつなげたものに対して、a ~ zの文字列のみにして、大文字を小文字に変換した文字列から単語を検索するという方法で評価実験をしている。
結果は検索する文字列の長さ: Plen, Plenに固定して検索した文字のパターン: Wordsにおいて、文字の比較回数の比率(各アルゴリズムの比較回数/BMの1文字の比較回数)はTalbe 1のような結果になった。
Table 1
比較回数が最も少なかったのはOMアルゴリズムで、BMとの速度の比率(BM/OM)はTable 3のようになった。
Table 3
これらのアルゴリズムではpattern文字列が少ないほど比較回数の現象に効果があり、一般的な文字列の検索においては10%の高速化が実現できるとしている。
感想
中盤で出て来るδ1, δ2, Δ1, Δ2を英文のみから理解できなくて辛かった。 〜みたいな操作を考えるとこれがΔ1である。みたいに書かれていて、定義が曖昧な気もする。 (δ1がBMにおける移動量, δ2がKMPにおける移動量だと思っていたけど、途中でBMのδ2みたいな表現もあって、崩壊した) 模擬コード・Cのコードがあるのでこれで理解できたので、問題ないが知らないアルゴリを英語で説明されるとつらいのがわかった、、、
オレオレgrep(fgrep)を作ってみようと思ってこの論文を読んでみたので、出現しうる全ての文字配列を用意できないorそのコストで検索自体よりコストが掛かりそうなので、使えんなと言うとこおろ。
Appendixに乗っているCのコードが明らかに自分のPCのgccではコンパイルできなさそうで、さすがに読む論文が古すぎたなと思った。
ここで紹介されている論文やBMの亜種などの論文は http://www-igm.univ-mlv.fr/~lecroq/string/index.html によくまとまっていた。
