Commentz-Walterアルゴリズム

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

コンピュータサイエンスではCommentz-Walterアルゴリズムは、BeateCommentz -Walterによって発明された文字列検索アルゴリズムです。[1] Aho–Corasick文字列照合アルゴリズムと同様に、一度に複数のパターンを検索できます。これは、Aho–Corasickのアイデアと、 Boyer–Moore文字列検索アルゴリズムの高速マッチングを組み合わせたものです長さがnで最大パターン長がmのテキストの場合、最悪の場合の実行時間はOmn)ですが、平均的な場合の方がはるかに優れていることがよくあります。[2]

GNU grepはかつて、Commentz-Walterと非常によく似た文字列照合アルゴリズムを実装していました。[3]

歴史

アルゴリズムに関する論文は、1979年にザールラント大学を通じてBeate Commentz-Walterによって最初に公開され、 「R.Scherner」によって入力されました。[1]この論文は、彼が主張した2つの異なるアルゴリズムを、彼がアルゴリズムBおよびB1と呼んだAho-CorasickアルゴリズムとBoyer-Mooreアルゴリズムのアイデアを組み合わせたものとして詳述しました。ただし、このホワイトペーパーでは主にアルゴリズムBに焦点を当てています。

アルゴリズムのしくみ

逆パターンツリーのサンプル

Commentz-Walterアルゴリズムは、マルチパターンマッチングの問題により適切に対処するために、2つの既知のアルゴリズムを組み合わせたものです。これらの2つのアルゴリズムは、フィルタリングを使用して単一パターンマッチングに対処するBoyer-MooreとAho-Corasickです。これを行うために、アルゴリズムは、 Aho-Corasickとは異なり、逆パターンを使用しながら、入力文字列内のパターンを検索するための接尾辞自動化を実装します[4]

Commentz-Walterには、実行する必要のある2つのフェーズがあります。これらは、事前計算フェーズとマッチングフェーズです。最初のフェーズでは、Commentz-Walterアルゴリズムは逆パターンを使用してパターンツリーを構築します。これは、事前計算フェーズと見なされます。マッチングフェーズと呼ばれる2番目のフェーズでは、他の2つのアルゴリズムが考慮されます。ボイヤームーア文字のシフト手法とエイホコラシック手法の有限オートマトンを使用して、Commentz-Walterアルゴリズムでマッチングを開始できます。[4]

Commentz-Walterアルゴリズムは、入力文字列全体を逆方向にスキャンし、不一致をチェックします。アルゴリズムが不一致を検出した場合、アルゴリズムは一致する文字の一部をすでに認識しており、この情報をインデックスとして使用します。インデックスを使用して、アルゴリズムは事前に計算されたテーブルをチェックして、シフトする必要のある距離を見つけます。その後、アルゴリズムはもう一度マッチングの試行を開始します。

時間計算量

Aho-CorasickをCommentz-Walterアルゴリズムと比較すると、時間計算量の概念を備えた結果が得られますAho-Corasickは線形On + k )と見なされますが、Commentz-Walterは2次Omn)と見なされる場合があります。この理由は、Commentz-WalterがBoyer-Moore文字列検索アルゴリズム内のシフトをAho-Corasickに追加することによって開発されたため、その複雑さが線形から2次に移行したことにあります。

「TheJournalofNational Science Foundation of Sri Lanka 46」で行われた調査によると、Commentz-Walterは、一般的にAho-Corasick文字列照合アルゴリズムよりも高速であるようです。ジャーナルによると、これは長いパターンを使用する場合にのみ存在します。ただし、ジャーナルには、このステートメントに関する重要な分析はなく、アルゴリズムのパフォーマンスに関する一般的な合意がないことが記載されています。[5]

「TheInternationalJournalof Advanced Computer Science and Information Technology」による研究で行われたアルゴリズムの実行時間の視覚化に見られるように、アルゴリズムのパフォーマンスは、パターンセット内の最短パターンが増加するにつれて直線的に増加しました。[4]

代替アルゴリズム

元のCommentz-Walterの論文では、代替アルゴリズムも作成されました。B1として知られるこのアルゴリズムは、メインのCommentz-Walterアルゴリズムと同様に動作しますが、スキャンフェーズでのパターンツリーの使用方法が異なります。

この論文はまた、このアルゴリズムは、前処理フェーズと検索フェーズの両方の実行時間とスペースを増やすという犠牲を払って、より優れたパフォーマンスを発揮すると主張しています。ただし、このアルゴリズムは他の研究では正式にテストされていないため、実際のパフォーマンスは不明です。[1]

参照

  1. ^ a b c Commentz-Walter、Beate(1979)。平均で高速な文字列照合アルゴリズム (PDF)Automata、Languages、Programmingに関する国際コロキウムLNCS71.オーストリア、グラーツ:スプリンガー。pp。118–132。土井10.1007/3-540-09510-1_10ISBN 3-540-09510-12017-10-10にオリジナル (PDF)からアーカイブされました。
  2. ^ ワトソン、ブルースウィリアム(1995-09-15)。正規言語アルゴリズムの分類とツールキットアイントホーフェン工科大学土井10.6100/IR444299ISBN 90-386-0396-7
  3. ^ "grep:Commentz-Walterコードを削除"GNUgrep_ 2017-01-18 2022-05-15を取得
  4. ^ a b c Akinul Islam Jony(2014)。「複数の文字列パターンマッチングアルゴリズムの分析」(PDF)高度なコンピュータ科学と情報技術の国際ジャーナル(IJACSIT)3(4):344–353。ISSN2296-1739_  
  5. ^ Dewasurendra、SD; Vidanagamachchi、SM(2018)。「Commentz-Walterアルゴリズムの平均時間計算量分析」。スリランカ国立科学財団のジャーナル46(4):547–557。土井10.4038/jnsfsr.v46i4.8630