13

私は基本的にいくつかの高速文字列照合アルゴリズムのベンチマークを行っていますが、いくつか出くわしました。

  1. Gonzalo Navarro と Mathieu Raffinot による Backwards Non-deterministic DAWG (Directed acyclic word graph) マッチング アルゴリズム。「接尾辞オートマトンへのビット並列アプローチ: 高速拡張文字列マッチング」を参照してください。

  2. ボイヤー・ムーア文字列検索アルゴリズムの Horspool の改良版。「文字列での実用的な高速検索」を参照してください。

  3. 不一致のある Shift-Or アルゴリズム

  4. KMP

私が試すことができる他の高速文字列マッチングアルゴリズムはありますか?

編集：同様の行に別のスレッドがあり、これにも良い参照があります

4

3 に答える 3

2

私の知る限り、双方向の文字列マッチングは、文字列マッチングに最適な汎用アルゴリズムです。線形の最悪の場合の複雑さを持ち、一定のスペースを使用し、必要以上にバックトラックしません。そして、その背後にある理論は非常に素晴らしいです。

ユーザーがぎくしゃくしていないことがわかっている場合、アーキテクチャに最適化された単純な文字列マッチングは短い「針」で勝ちますが、Boyer-Moore バリアントは長い「針」でサブリニアな処理を実際に実行し始めます。ただし、単純な文字列の一致には 2 次の最悪のケースがあり、Boyer-Moore を使用して入力内のすべての文字を調べることができます。不一致を処理するために必要な追加のテーブルは、実際には、双方向の文字列一致よりも驚くほど深刻なペナルティをもたらします。

于 2013-01-17T11:52:55.497 に答える
0

あなたも試すことができます

  • Z Algorithm : いくつかの点で KMP よりも優れています
  • Aho Corasick : Trie ベースで、元々は fgrep で使用されていました
  • Rabin Karp : ハッシュベース
于 2013-01-17T11:39:21.577 に答える