std::string::findより速くなるかもしれない。boost::algorithmのboyer_moore_searchとかknuth_morris_pratt_searchとか

この記事は、C++ Advent Calendar 2014の2014年12月7日ぶんです。（1時間弱遅刻してしまいました）

これは何ですか

C++標準の文字列クラスstd::stringには、その中に指定されたキーワード（文字列）が含まれているか&含まれている場合には何文字目から出現するかを返すメソッドとして、std::string::findが用意されている。
多くの場合これがあれば事足りるのだが、あまり長い文字列を検索キーワードに指定するような場合には、（少なくとも理論的には）大幅に遅くなることが知られている。
これを改善した（少なくとも理論的には）アルゴリズムとして、Boyer-Moore SearchやKnuth-Morris-Pratt Searchというアルゴリズムがある。本記事では上記の遅くなる理由とこれら二つのアルゴリズムについて概略を説明する（実装の詳細は一部のみ説明）とともに、Boost C++ Libraries上の実装であるboost::boyer_moore_search・boost::boyer_moore_horspool_search・boost::knuth_morris_pratt_searchによるパフォーマンス比較を行う。

補足

本稿において文字数を数える際は、プログラム中に限らず本文中も含め、先頭の文字を0文字目と数える。

std::string::findの挙動

では最初に、std::string::findがどういった挙動で文字列の検索をしているのかを説明する。といっても難しいものではなく、誰もが思いつきそうなものである。（なお実装はgccのものを参考にしている。）

例えば

std::string corpus = "BANNANABANANAN";
std::string pattern = "BANANA";
size_t pos = corpus.find(pattern);

を考える。このとき、corpus.find(pattern)の返り値は「patternがcorpusの何文字目から始まるか（複数箇所存在すれば最初のもの）」であるので、7となる。

std::string::findは、これを以下の手順で実現している。

• まず、corpusの先頭とpatternの先頭が一致するか、corpusの次の文字とpatternの次の文字が一致するか、…を順に比較し、途中で一致しなければ次に進み、patternの末尾まで一致すればその場所を返す。
• 次に、corpusの比較の起点を1文字進めて同様の比較を行う。これをどこかで一致するか、corpusの比較の起点が文字列の端に到達するまで繰り返す。

図解すると以下のようになる。

BANNANABANANAN
BANA--          0文字目から開始: Aが不一致
 B-----         1文字目から開始: Bが不一致
  B-----        2文字目から開始: Bが不一致
   B-----       3文字目から開始: Bが不一致
    B-----      4文字目から開始: Bが不一致
     B-----     5文字目から開始: Bが不一致
      B-----    6文字目から開始: Bが不一致
       BANANA   7文字目から開始: 最後まで一致

この場合、比較の左端は1文字ずつしかずらせない。
これは一見するとやむを得ないようにも見えるのだが、実はここを「1文字ずつに限定しない」ことが計算速度改善の可能性を生むのである。

Boyer-Moore Search

まず、Boyer-Moore Searchの考え方を説明する。これは「corpus側にあったどの文字で間違ったと判定されたか」を用いて、ずらす文字数を決定するものである。（このほかに、「pattern中に同じ文字列が出現するか」といった情報も使うのだが、そちらの解説は割愛する。）

Boyer-Moore Searchでは、後ろから比較を進める。まず「corpusの先頭から6文字ぶんがpatternと一致するか」を調べるには

BANNANABANANAN
BANANA
     |           不一致

末尾から順に比較していくので、この場合最初の時点ですでに一致してないと判定される。
さてこのときBoyer-Moore Searchでは、「一致しなかったのはcorpus側の'N'が原因だったので、pattern側にある'N'をそこに強制的に合わせよう」と考えるのである。この場合、patternには二つの'N'があるので、そのうち最後にあるものに合わせる。（すなわち、patternをずらす長さが最小になるようにする。）

BANNANABANANAN
BANANA
     ↓
BANNANABANANAN
 BANANA          pattern側の
     |           一番右の'N'の位置を合わせた

続いて、もう一度右から順に比較を進めていくと、今度はpatternの右から5文字目の時点で不一致とわかる。

BANNANABANANAN
 BANANA
  |              不一致

この場合、corpus側の不一致文字は'N'なのだが、pattern側の不一致発生位置より左に'N'がないため、この場合はそれより右側までパターンを動かしてしまう。

BANNANABANANAN
 BANANA
  ↓
BANNANABANANAN
   BANANA

ただしBoostにおける実装ではそれはしておらず簡略化している。というのも、上記のことをまともに行おうとすると、動かす文字数の表が「patternの文字数×patternに利用される文字の種類数」と非常に大きくなるためである。これを「patternに利用される文字の種類数」のみに抑えるため、動かす文字数を決定する際は、「仮に右端で不一致が生じたと仮定したときの動かせる文字数」を必ず適用することにしている（上記の場合、不一致文字が'N'であり、'N'はpatternの右から2文字目に出現しているので、動かせるのは1文字のみ）。動かせる文字数は減少するものの、メモリ量は削減される。

以下同様に進める。次の不一致が発生した際のcorpus側の文字は'B'であるので、以下のように進む。

BANNANABANANAN
   BANANA
       ↓         ここが不一致
BANNANABANANAN
       BANANA    'B'の位置を合わせた
                 (ここで全文字一致)

これをすべてまとめると、実際に検索の過程で比較している文字は以下のようになる。4つの左端についてしか比較していないことがわかる。

BANNANABANANAN
----NA
 -ANANA
   ----NA
       BANANA

これを実現するためには、実際の検索を始める前にあらかじめpatternをスキャンして、どの文字が何文字目に出現しているかを調べ、その上で左端を何文字動かすかの表を作る必要がある。そうしないと実際の検索が遅くなってしまうので。
具体的には以下のように計算される。

BANAN(A)   末尾を除いた状態で、
   |------ pattern中に現れる一番右のAは2文字目。
|--------- pattern中に現れる一番右のBは5文字目。
    |----- pattern中に現れる一番右のNは1文字目。

以上より、
「corpus側で違っていた文字がAなら2文字ずらす」
「corpus側で違っていた文字がBなら5文字ずらす」
「corpus側で違っていた文字がNなら1文字ずらす」
（それ以外はpatternの長さ=6文字ずらす）

なお実際にはこれに加え、patternのsuffix（末尾から適当な文字数取ったもの。'BANANA'なら'A', 'NA', 'ANA', ...が該当）がpattern中の別の位置に出現している場合には、それをもとに左端をずらすことも同時に行っているのだが、その部分は割愛する。（この場合、suffixの'NA'は'BANANA'中にもう一度出現している、など）
ただし参考記事では、その部分を省いたものをBoyer-Moore Searchとして紹介しているものもある。

またその亜種であるBoyer-Moore-Horspool法では、上記の「文字列中で一致している部分文字列がどこにあるかをもとに左端をずらす」という手法を省略しているほか、「corpus側の不一致文字がpattern側の末尾の文字に一致していた場合」の処理が異なっている（らしい）。

参考記事

今回省略した「文字列中で一致している部分文字列がどこにあるかをもとに左端をずらす」という手順については、以下の記事においてはWikipedia以外言及がなかった。難しいからなのか、案外必要ないからなのか。

• ボイヤー-ムーア文字列検索アルゴリズム - Wikipedia
• Algorithms with Python / 文字列の探索 これが解説が細かい
• 文字列検索（BM法） 比較的解説が細かい
• C言語アルゴリズム-BM法 CapmNetwork 図が見やすくサンプルプログラムも付いている。ただしアルゴリズムの解説は完全ではない（場合分けの一部を省略している）と思われる
• コーディングに役立つ！ アルゴリズムの基本（7）：文字列の中から効率良くキーワードを探し出せ (3/4) - ＠IT 同上

Knuth-Morris-Pratt Search

Boyer-Moore Searchにおいては「corpus側にあったどの文字で間違ったと判定されたか」を用いてずらす文字数を決定していたのに対し、Knuth-Morris-Pratt Searchにおいてはpattern側の文字列のみに注目してずらす文字数を決定する。
具体的には、patternのprefix（先頭から適当な文字数取ったもの。'BANANA'なら'B', 'BA', 'BAN', ...が該当）がpattern中の別の位置に含まれているならばその位置までずらし、そうでなければすでに照合済みの区間をすべて飛び越える位置までずらす。
あとは、Wikipediaの記事が（比較的）分かりやすいのでそちらを参照されたい。
クヌース-モリス-プラット法 - Wikipedia

計算時間の特徴

これらの方法はともに、事前にpatternをスキャンして左端をずらす文字数をあらかじめ計算する必要がある。しかしながら、理論的な計算時間が最初に示した方法に比べてよく、特に「patternの長さへの依存が小さくなる」という利点がある。

計算方法	計算時間（平均）	計算時間（最悪）
std::string::find	O(CP)	O(CP)
Boyer-Moore(-Horspool)	O(C+P)	O(CP)
Knuth-Morris-Pratt	O(C+P)	O(C+P)

※C: corpus（走査される文字列）の長さ、P: pattern（切り出したい文字列）の長さ

理論的にはKnuth-Morris-Prattが最悪時間計算量（性能が悪化する事例まで踏まえた性能）がもっともよいのだが、実用上はBoyer-Moore(-Horspool)のほうが高速といわれている。

Boostでの利用方法

これらの関数は、boost::algorithm空間中に定義されている。std::string::findが何文字目を返すのかとは異なり、返り値は出現位置に対するイテレータとなっている。

単に検索を行うコードの例を示す。Boostがインストールされている状態で（必要ならそのパスをオプションで指定した上で）このコードをコンパイルし実行すると、「7」が4回表示されるはずである。

#include <iostream>
#include <string>

#include <boost/algorithm/searching/boyer_moore.hpp>
#include <boost/algorithm/searching/boyer_moore_horspool.hpp>
#include <boost/algorithm/searching/knuth_morris_pratt.hpp>

int main(void){
    size_t pos;
    std::string corpus = "BANNANABANANAN";
    std::string pattern = "BANANA";
    
    // 単にstd::string::findで検索する
    pos = corpus.find(pattern);
    std::cout << pos << std::endl;
    
    // 以下では検索結果をイテレータで受け取るため
    // あらかじめ定義している
    std::string::const_iterator search_result;
    
    // Boyer-Moore Search
    search_result = boost::algorithm::boyer_moore_search(
        corpus.begin(), corpus.end(),
        pattern.begin(), pattern.end());
    std::cout << (search_result - corpus.begin()) << std::endl;
    
    // Boyer-Moore-Horspool Search
    search_result = boost::algorithm::boyer_moore_horspool_search(
        corpus.begin(), corpus.end(),
        pattern.begin(), pattern.end());
    std::cout << (search_result - corpus.begin()) << std::endl;
    
    // Knuth-Morris-Pratt Search
    search_result = boost::algorithm::knuth_morris_pratt_search(
        corpus.begin(), corpus.end(),
        pattern.begin(), pattern.end());
    std::cout << (search_result - corpus.begin()) << std::endl;
}

なお前述の通り、これらの検索方法は「ずらせる文字数をpatternから事前に計算する」ということを行っているため、その結果を保持するためのクラスも用意されている。同じpatternで何度も検索する場合はそのクラスを用いればよい。以下にBoyer-Moore Searchでの例を示す。

#include <iostream>
#include <string>

#include <boost/algorithm/searching/boyer_moore.hpp>

int main(void){
    size_t pos;
    std::string corpus = "BANNANABANANAN";
    std::string pattern = "BANANA";
    
    std::string::const_iterator search_result;

    boost::algorithm::boyer_moore<std::string::iterator> bm_pattern(
        pattern.begin(), pattern.end());
    search_result = bm_pattern(corpus.begin(), corpus.end());
    std::cout << (search_result - corpus.begin()) << std::endl;
}

実験

本当はもう少し普通なデータで実験したかったのですが準備してる時間がありませんでした。特徴の出やすいデータで実験しています。
実験環境はVMware上のUbuntu14.04（RAM：1GB、CPU：Core-i5 M480 2.67GHz）です。

パターン：

1. ABCDEABCDE...ABCDEABCDEZ（長さ10001）
2. ZABCDEABCDE...ABCDEABCDE（長さ10001）
3. ABCDE...ABCDEZABCDE...ABCDE（長さ10001、Zは中央）

コーパス：

1. ABCDEABCDEABCDEABCDE...ABCDEABCDE（長さ100万）の後ろにパターンを付け加えたもの
2. ABCDEFGHIJABCDEFGHIJ...ABCDEFGHIJ（長さ100万）の後ろにパターンを付け加えたもの

コーパスの1と2の違いは、コーパス側にパターンに存在しない文字が頻繁に登場するかである。

実験結果

まずパターンとして1を利用した場合。

方法	コーパス1	コーパス2
find	104.4	119.6
BM	8.7	9.4
BMH	6.3	8.1
KMP	12.6	13.3
（単位はミリ秒）

このパターンにコーパス1の場合、普通のfindを使うと、「しばらく完全に一致しているのに、最後にコーパスとパターンで不一致が生じる」ということになるため、これは当然遅い。BMやBMHは後ろから走査するため当然速いし、KMPも不一致文字がZであるということから位置を一気に動かせるのが利いているとみられる。

続いてパターンとして2を利用した場合。

方法	コーパス1	コーパス2
find	1.0	1.5
BM	9.7	10.4
BMH	17168.6	16949.2
KMP	19.5	19.3
（単位はミリ秒）

この場合、パターンの先頭がコーパスに存在しない文字であるため、findは「1文字目から一致していない」と判定できて高速になり、一方で後ろからのマッチングであるうえに前処理を減らしているBMHは「findが最も遅くなるような場合」に近い計算をさせられているような状況になっている。

最後にパターンとして3を利用した場合。

方法	コーパス1	コーパス2
find	78.9	57.2
BM	10.4	9.5
BMH	8557.6	8304.9
KMP	12.7	12.4

パターン1とパターン2の中間を取ったケースは、BMとKMPが高速という結果に。この辺の理由を説明するまで勉強できませんでした。

余談

パターンの長さを100に変えて実験した場合、どのケースでもfindが最速であった。

おわりに

文字列検索のアルゴリズムとしてBoyer-Moore(-Horspool)法、Knuth-Morris-Pratt法を紹介し、どんなアルゴリズムなのかならびに、Boostで提供されている実装の利用方法、実験による比較を行った。

上記「余談」の通り、パターンが長いほど効果の出る手法ではあるのだが、実際問題として長いパターンの文字列検索を行う実例は少ないかもしれない。ただ、文字列比較における一つの工夫としてこういうものがあり、またそれがBoostを導入すればすぐ使える、というのを知っておくと何かに役立つかもしれませんよ。文字列検索の内部的処理とかを作らないとならないとか。

そもそもこの記事を書いたきっかけ

は、std::string::findのソースコードを読んだときに実装が上記のような単純なものであり、すでにBoyer-Moore法やKnuth-Morris-Pratt法の話を知っていた私は「なぜそれを使わないんだろう、オーバーヘッドが大きいのだろうか」と思い、今回こうやって調べたのでした。