Hello World, We Are Phusion. We provide amazing Ruby & Rails products and services to companies that shape our modern day culture.

エンタープライズ向けの高速Ruby on Rails実行環境を提供しているPhusionがEfficient substring searching - Phusion Corporate Blogにおいて、特定の文字列からある文字列を検索をするためのアルゴリズムの比較と、その実装系(C++)の公開を実施している。文字列検索はプログラミングで頻出する処理のひとつであり、プログラミング上の参考になる。

文字列から特定の文字列を検出する場合、全体の文字列長(M)と一致させたい文字列の長さ(N)の積O(M*N)が計算量となる。O(M*N)よりも計算量を下げるための方法としてはKnuth-Morris-PrattやBoyer-Mooreなどがあり、Efficient substring searchingでは特にBoyer-Mooreアルゴリズムとその派生アルゴリズム(Turbo Boyer-MooreおよびBoyer-Moore-Horspool)に焦点をあて、アルゴリズムの紹介と性能評価を実施している。

これらアルゴリズムは最初に検索対象となる文字列から計算用のデータを生成し、そのデータを活用して不一致時に可能な限り比較対象を飛ばすという処理をしている。こうすることで不要な比較処理を避け、処理の高速化を実現する。

Efficient substring searchingでは、実現的なプログラミングという立場から見た評価をしており、その結果は次のようになっている。

• アルゴリズムごとに性能特性は大きく異なる。
• 対象の文字列が長い場合には賢いアルゴリズムを選択した方がいい。ただし、アルゴリズムの適用には別途計算用のデータを生成する必要があり、この生成の手間が全体の処理時間も含めて許容できるものであるかを判断する必要がある。
• Turbo Boyer-Mooreはワーストケースがそれほどひどくならないという点で魅力的な候補のように見えるが、実際のところ学術的観点からは無視できるオーバーヘッドが大きな問題であり、内部ループも複雑すぎる。採用に適したアルゴリズムとはいえず、ベースとなっているBoyer-Mooreの方が現実的。
• Boyer-Moore-Horspoolは多くのケースで最良の選択肢。理論上では最悪のケースで性能が発揮できないが、これはめったにない。内部ループはシンプルで理解しやすく、その結果CPUキャッシュを活用したコーディングを実施しやすい。
• Boyer-Moore-HorspoolはプロトコルヘッダのパースやMIMEデータのパースなどに活用できる。

Efficient substring searchingではBoyer-Moore-Horspoolを現実的なところ効果的なアルゴリズムであるとし、Boyer-Moore-Horspoolをベースにデータをストリーミングで処理できるように実装したC++ライブラリを公開している。文字列検索にBoyer-Mooreを活用するというのはGNU grepのオリジナル開発者も高速処理の基本だと説明している。

• GNU grepが高速な理由

GNU grepのオリジナル開発者であるMike Haertel氏はBoyer-Mooreをベースにしつつ、いくつかの実装上の工夫とシステム性能を発揮できるプログラミングテクニックを加えて高速な処理を実現している。