文字列検索アルゴリズム

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

コンピュータサイエンスでは文字列検索アルゴリズム(文字列照合アルゴリズムと呼ばれることもあります)は、1つまたは複数の文字列(パターンとも呼ばれる)がより大きな文字列またはテキスト内で見つかる 場所を見つけようとする文字列アルゴリズムの重要なクラスです。

文字列検索の基本的な例は、パターンと検索されたテキストがアルファベット有限集合)Σの要素の配列である場合です。Σは人間の言語のアルファベットである場合があります。たとえば、AからZの文字や他のアプリケーションでは、バイナリアルファベット(Σ= {0,1})またはDNAアルファベット(Σ= {A、C、G、T})を使用できます。バイオインフォマティクス

実際には、実行可能な文字列検索アルゴリズムの方法は、文字列エンコーディングの影響を受ける可能性があります。特に、可変幅エンコーディングが使用されている場合、 N番目の文字を見つけるのに時間がかかる可能性があり、おそらくNに比例する時間が必要になります。これにより、一部の検索アルゴリズムが大幅に遅くなる可能性があります。多くの可能な解決策の1つは、代わりにコードユニットのシーケンスを検索することですが、エンコードがそれを回避するように特別に設計されていない限り、そうすると誤った一致が生成される可能性があります。[要出典]

概要

文字列検索の最も基本的なケースには、干し草の山と呼ばれることもある1つの(非常に長い)文字列と、と呼ばれることもある1つの(非常に短い)文字列が含まれます。目標は、干し草の山の中の針の1つ以上の出現を見つけることです。たとえば、次の範囲内で 検索できます。

   味わう本もあれば、飲み込む本もあれば、噛んで消化する本もあります。

4番目の単語である「to」の最初の出現を要求する場合があります。またはすべての発生、そのうち3つあります。または最後、つまり最後から5番目の単語です。

ただし、非常に一般的には、さまざまな制約が追加されます。たとえば、「針」を1つ(または複数)の完全な単語で構成されている場合にのみ一致させたい場合があります。おそらく、両側に他の文字が隣接していないと定義されます。その場合、「hew」または「low」の検索は、これらのリテラル文字列が発生したとしても、上記の例文では失敗するはずです。

もう1つの一般的な例には、「正規化」が含まれます。多くの目的で、「to」と「be」の間に何か他のものが介在している場所でも、「tobe」などのフレーズの検索は成功するはずです。

  • 複数のスペース
  • タブ、改行なしスペース、改行などの他の「空白」文字。
  • あまり一般的ではありませんが、ハイフンまたはソフトハイフン
  • 構造化されたテキスト、タグ、または脚注、リスト番号やその他のマーカー、埋め込み画像など、任意に大きいが「括弧で囲まれた」もの。

多くのシンボルシステムには、同義の文字が含まれています(少なくとも一部の目的では)。

  • ラテン語ベースのアルファベットは小文字と大文字を区別しますが、多くの目的で、文字列検索はその区別を無視することが期待されます。
  • 多くの言語には合字が含まれており、1つの複合文字が2つ以上の他の文字と同等です。
  • 多くの書記体系には、アクセントや母音のポイントなどの発音区別符号が含まれます。これらのマークは、使用法が異なる場合や、マッチングの重要性が異なる場合があります。
  • DNA配列には、一部の目的では無視される可能性のある非コードセグメント、またはコード化されたタンパク質に変化をもたらさない多型が含まれる場合があります。これは、他の目的では真の違いとは見なされない場合があります。
  • 一部の言語には、単語の最初、中間、または最後に異なる文字または文字の形式を使用する必要があるという規則があります。

最後に、自然言語を表す文字列の場合、言語自体の側面が関与します。たとえば、別のスペル、接頭辞、接尾辞などがあるにもかかわらず、「単語」のすべての出現箇所を検索したい場合があります。

もう1つのより複雑なタイプの検索は、正規表現検索です。この場合、ユーザーは文字またはその他の記号のパターンを作成し、パターンに一致するものがあれば検索を実行する必要があります。たとえば、アメリカ英語の単語「color」と英国の同等の「color」の両方をキャッチするには、2つの異なるリテラル文字列を検索する代わりに、次のような正規表現を使用します。

どこ "?" 通常、前の文字( "u")はオプションになります。

この記事では、主に、より単純な種類の文字列検索のアルゴリズムについて説明します。

バイオインフォマティクスとゲノミクスの分野で導入された同様の問題は、最大正確一致(MEM)です。[1] 2つの文字列がある場合、MEMは一般的なサブ文字列であり、不一致を引き起こさずに左右に拡張することはできません。[2]

検索アルゴリズムの例

素朴な文字列検索

ある文字列が別の文字列のどこにあるかを確認する簡単で非効率的な方法は、各インデックスを1つずつ確認することです。まず、干し草の山の最初の文字から始まる針のコピーがあるかどうかを確認します。そうでない場合は、干し草の山の2番目の文字から始まる針のコピーがあるかどうかを確認します。通常の場合、間違った位置ごとに1つまたは2つの文字を調べて、それが間違った位置であることを確認するだけで済みます。したがって、平均的な場合、これにはOn + m)ステップが必要です。ここで、 nは次の長さです。干し草の山とmは針の長さです。しかし、最悪の場合、「aaaaaaaaab」のような文字列で「aaaab」のような文字列を検索すると、Onm

有限状態オートマトンベースの検索

DFA検索mommy.svg

このアプローチでは、保存された検索文字列を認識する決定性有限オートマトン(DFA)を構築することにより、バックトラックを回避します。これらは構築に費用がかかります—通常はパワーセット構造を使用して作成されます—しかし、非常にすばやく使用できます。たとえば、右に示されているDFAは、「MOMMY」という単語を認識します。このアプローチは、実際には、任意の正規表現を検索するために一般化されることがよくあります。

スタブ

Knuth–Morris–Prattは、検索する文字列を接尾辞として入力を認識するDFAを計算します。Boyer–Mooreは針の端から検索を開始するため、通常、各ステップで針の長さ全体をジャンプできます。Baeza–Yatesは、前のj文字が検索文字列のプレフィックスであったかどうかを追跡するため、あいまい文字列検索に適応できます。bitapアルゴリズムは、Baeza–Yatesのアプローチを応用したものです

インデックスメソッド

より高速な検索アルゴリズムは、テキストを前処理します。接尾辞ツリー接尾辞配列などの部分文字列インデックスを作成した後、パターンの出現をすばやく見つけることができます。例として、接尾辞木を組み込むことができます時間、そしてすべてパターンの出現はで見つけることができますアルファベットが一定のサイズであり、接尾辞ツリーのすべての内部ノードがその下にある葉を知っているという仮定の下での時間。後者は、サフィックスツリーのルートから DFSアルゴリズムを実行することで実現できます。

その他のバリエーション

トライグラム検索などの一部の検索方法は、「一致/不一致」ではなく、検索文字列とテキストの間の「近さ」スコアを見つけることを目的としています。これらは「ファジー」検索と呼ばれることもあります

検索アルゴリズムの分類

パターン数による分類

さまざまなアルゴリズムは、それぞれが使用するパターンの数によって分類できます。

シングルパターンアルゴリズム

次のコンパイルでは、mはパターンの長さ、nは検索可能なテキストの長さ、k =|Σ|です。アルファベットのサイズです。

アルゴリズム 前処理時間 マッチング時間[1] スペース
ナイーブアルゴリズム 無し Θ(mn) 無し
ラビン-カープ Θ(m) 平均でΘ(n)、
最悪の場合O(mn)
O(1)
クヌース-モリス-プラット Θ(m) Θ(n) Θ(m)
ボイヤームーア Θ(m + k) せいぜいΩ(n / m)
、最悪の場合O(mn)
Θ(k)
双方向アルゴリズム[3] [2] Θ(m) の上) O(1)
後方非決定論的DAWGマッチング(BNDM)[4] [3] O(m) の上)
後方Oracleマッチング(BOM)[5] O(m) O(mn)
1. ^漸近時間は、O、Ω、およびΘ表記を使用して表されます。
2. ^ glibc [6]およびmusl [7] C標準ライブラリにmemmemおよびstrstr検索関数を実装するために使用されます
3. ^拡張して、正規言語として表されるおおよその文字列マッチングと(潜在的に無限の)パターンのセットを処理できます[要出典]

ボイヤー-ムーア文字列検索アルゴリズムは、実用的な文字列検索文献の標準的なベンチマークです[8]

有限のパターンセットを使用するアルゴリズム

次のコンパイルでは、Mは最長のパターンの長さ、mは全長、nは検索可能なテキストの長さ、oは出現回数です。

アルゴリズム の拡張 前処理時間 マッチング時間[4] スペース
エイホ-コラシック クヌース-モリス-プラット Θ(m) Θ(n + o) Θ(m)
Commentz-ウォルター ボイヤームーア Θ(m)
Θ(M * n)平均で劣線形の最悪の場合[9]
Θ(m)
セット-BOM 後方Oracleマッチング

無限のパターンを使用するアルゴリズム

当然、この場合、パターンを有限に列挙することはできません。それらは通常、正規文法または正規表現で表されます。

前処理プログラムの使用による分類

他の分類アプローチも可能です。最も一般的な使用法の1つは、主な基準として前処理を使用します。

文字列検索アルゴリズムのクラス[10]
テキストは前処理されていません 前処理されたテキスト
前処理されていないパターン 基本アルゴリズム インデックスメソッド
前処理されたパターン 構築された検索エンジン 署名方法:[11]

マッチング戦略による分類

もう1つは、マッチング戦略によってアルゴリズムを分類します。[12]

  • 最初にプレフィックスを一致させます(Knuth–Morris–Pratt、Shift-And、Aho–Corasick)
  • 最初に接尾辞を一致させます(Boyer–Mooreおよびバリアント、Commentz-Walter)
  • 最初に最良の要素を一致させます(BNDM、BOM、Set-BOM)
  • その他の戦略(ナイーブ、ラビン-カープ)

も参照してください

参照

  1. ^ Kurtz、Stefan; フィリッピー、アダム; デルチャー、アーサーL; スムート、マイケル; マーティン、シャムウェイ; アントネスク、コリーナ; サルツバーグ、スティーブンL(2004)。「大きなゲノムを比較するための多用途でオープンなソフトウェア」ゲノム生物学5(2):R12。土井10.1186/gb-2004-5-2-r12ISSN1465-6906 _ PMC395750 _ PMID14759262 _
  2. ^ カーン、ジア; ブルーム、ジョシュアS .; Kruglyak、Leonid; シン、モナ(2009-07-01)。「スパース接尾辞配列を使用して、大規模なシーケンスデータセットで最大の完全一致を見つけるための実用的なアルゴリズム」バイオインフォマティクス25(13):1609–1616。土井10.1093 / bioinformatics/btp275PMC2732316_ PMID19389736_  
  3. ^ クロシュモア、マキシム; ペリン、ドミニク(1991年7月1日)。「双方向の文字列照合」(PDF)ACMのジャーナル38(3):650–674。土井10.1145/116825.116845S2CID15055316_ 2021年11月24日のオリジナルからアーカイブ(PDF)2019年4月5日取得  
  4. ^ Navarro、ゴンザロ; ラフィノット、マシュー(1998)。「接尾辞オートマトンへのビット並列アプローチ:高速拡張文字列照合」(PDF)組み合わせパターンマッチングコンピュータサイエンスの講義ノート。シュプリンガーベルリンハイデルベルク。1448:14–33。土井10.1007/bfb0030778ISBN  978-3-540-64739-32019-01-05のオリジナルからアーカイブ (PDF)2019年11月22日取得
  5. ^ ファン、H .; 八尾、N .; Ma、H.(2009年12月)。「後方オラクルマーチングアルゴリズムの高速バリアント」(PDF)科学と工学のためのインターネットコンピューティングに関する2009年第4回国際会議:56–59。土井10.1109/ICICSE.2009.53ISBN  978-1-4244-6754-9S2CID6073627 _ 2022-05-10にオリジナルからアーカイブされました2019年11月22日取得
  6. ^ "glibc / string/str-two-way.h"2020-09-20にオリジナルからアーカイブされました2022-03-22を取得
  7. ^ "musl / src / string/memmem.c"2020年10月1日にオリジナルからアーカイブされました2019年11月23日取得
  8. ^ ヒューム; 日曜日(1991)。「高速文字列検索」ソフトウェア:実践と経験21(11):1221–1248。土井10.1002/spe.4380211105S2CID5902579_ 2022-05-10にオリジナルからアーカイブされました2019-11-29を取得 
  9. ^ 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)からアーカイブされました。
  10. ^ Melichar、Borivoj、Jan Holub、およびJ.Polcar。テキスト検索アルゴリズム。ボリュームI:フォワード文字列照合。1. 2巻、2005年。http://stringology.org/athens/TextSearchingAlgorithms/WaybackMachine で2016-03-04にアーカイブされました。
  11. ^ Riad Mokadem; Witold Litwin http://www.cse.scu.edu/~tschwarz/Papers/vldb07_final.pdf(2007)、代数署名を使用してエンコードされたデータに対する高速nGramベースの文字列検索、第33回超大規模データベースに関する国際会議(VLDB) {{citation}}:(ヘルプ外部リンク|surname2=
  12. ^ ゴンサロ・ナヴァロ; Mathieu Raffinot(2008)、柔軟なパターンマッチング文字列:テキストおよび生物学的シーケンスの実用的なオンライン検索アルゴリズムISBN 978-0-521-03993-2

外部リンク