文字列検索アルゴリズム

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

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

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

概要

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

ある本は味わうべきものであり、他の本は飲み込むべきものであり、そしていくつかの本は噛んで消化すべきものである。

「to」の最初の出現（4 番目の単語）を要求することも、すべての出現（3 回）を要求することも、最後から 5 番目の単語である最後の出現を要求することもできます。

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

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

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

多くの記号システムには、（少なくともいくつかの目的においては）同義の文字が含まれています。

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

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

もう 1 つのより複雑なタイプの検索は正規表現検索です。正規表現検索では、ユーザーが文字やその他の記号のパターンを作成し、そのパターンに一致するものがあれば検索が満たされます。たとえば、アメリカ英語の単語「color」とイギリス英語の同義語「colour」の両方を検索するには、2 つの異なるリテラル文字列を検索する代わりに、次のような正規表現を使用します。

色

ここで、「?」は慣例的に、先行する文字 (「u」) をオプションにします。

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

バイオインフォマティクスとゲノミクスの分野で導入された同様の問題に、最大完全一致（MEM）があります。^[1] 2つの文字列が与えられた場合、MEMは不一致を起こさずに左または右に拡張できない共通の部分文字列です。^[2]

検索アルゴリズムの例

単純な文字列検索

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

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

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

スタブ

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

インデックスメソッド

より高速な検索アルゴリズムは、テキストを前処理します。サフィックスツリーやサフィックス配列などの部分文字列インデックスを構築した後、パターンの出現をすばやく見つけることができます。たとえば、アルファベットのサイズが一定で、サフィックスツリー内のすべての内部ノードがその下にあるリーフを認識しているという仮定の下で、サフィックスツリーを時間内に構築し、パターンのすべての出現を時間内に見つけることができます。後者は、サフィックスツリーのルートから DFS アルゴリズムを実行することで実現できます。 $\Theta (n)$ $z$ $O(m)$

その他のバリエーション

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

検索アルゴリズムの分類

いくつかのパターンによる分類

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

単一パターンアルゴリズム

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

1. ^漸近時間はO、Ω、Θ表記法で表されます。

2. ^ glibc ^[6]およびmusl ^[7]C標準ライブラリのmemmemおよびstrstr検索関数を実装するために使用されます。

3. ^近似文字列マッチングや正規言語として表現されるパターンの（潜在的に無限の）集合を扱うように拡張できる。^[^要出典^]

ボイヤー・ムーアの文字列検索アルゴリズムは、実用的な文字列検索の文献における標準的なベンチマークとなっている。^[8]

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

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

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

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

前処理プログラムを使用した分類

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

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

もう一つの分類法は、アルゴリズムをマッチング戦略によって分類するものである。^[12]

最初にプレフィックスを一致させる (Knuth–Morris–Pratt、Shift-And、Aho–Corasick)
接尾辞を最初に一致させる (Boyer–Moore とその変種、Commentz-Walter)
最初に最適な要因を一致させる (BNDM、BOM、Set-BOM)
その他の戦略（ナイーブ、ラビン・カープ、ベクトル化）

参照

参考文献

^ Kurtz, Stefan; Phillippy, Adam; Delcher, Arthur L; Smoot, Michael; Shumway, Martin; Antonescu, Corina; Salzberg, Steven L (2004). 「大規模ゲノムを比較するための多用途でオープンなソフトウェア」.ゲノム生物学. 5 (2): R12. doi : 10.1186/gb-2004-5-2-r12 . ISSN 1465-6906. PMC 395750. PMID 14759262 .
^ Khan, Zia; Bloom, Joshua S.; Kruglyak, Leonid; Singh, Mona (2009-07-01). 「スパースサフィックスアレイを使用して大規模なシーケンスデータセットで最大の完全一致を見つけるための実用的なアルゴリズム」.バイオインフォマティクス. 25 (13): 1609–1616. doi :10.1093/bioinformatics/btp275. PMC 2732316. PMID 19389736 .
^ Crochemore, Maxime; Perrin, Dominique (1991年7月1日). 「双方向文字列マッチング」(PDF) . Journal of the ACM . 38 (3): 650–674. doi :10.1145/116825.116845. S2CID 15055316. 2021年11月24日時点のオリジナルよりアーカイブ(PDF ) . 2019年4月5日閲覧。
^ Navarro, Gonzalo; Raffinot, Mathieu (1998). 「サフィックスオートマトンへのビット並列アプローチ: 高速拡張文字列マッチング」( PDF) .組み合わせパターンマッチング.コンピュータサイエンスの講義ノート。第 1448 巻。Springer Berlin Heidelberg。pp. 14–33。doi :10.1007/bfb0030778。ISBN 978-3-540-64739-3. 2019年1月5日にオリジナルからアーカイブ（PDF）されました。2019年11月22日閲覧。
^ Fan, H.; Yao, N .; Ma, H. (2009 年 12 月)。「Backward-Oracle-Marching アルゴリズムの高速バリアント」(PDF)。2009年第 4 回科学技術のためのインターネットコンピューティングに関する国際会議。pp. 56–59。doi : 10.1109/ICICSE.2009.53。ISBN 978-1-4244-6754-9. S2CID 6073627. 2022年5月10日時点のオリジナルよりアーカイブ。2019年11月22日閲覧。
^ “glibc/string/str-two-way.h”. 2020年9月20日時点のオリジナルよりアーカイブ。2022年3月22日閲覧。
^ “musl/src/string/memmem.c”. 2020年10月1日時点のオリジナルよりアーカイブ。2019年11月23日閲覧。
^ Hume; Sunday (1991). 「高速文字列検索」.ソフトウェア: 実践と経験. 21 (11): 1221–1248. doi :10.1002/spe.4380211105. S2CID 5902579.
^ Commentz-Walter, Beate (1979). 平均的に高速な文字列マッチングアルゴリズム(PDF) .オートマトン、言語、プログラミングに関する国際コロキウム. LNCS . 第 71 巻。グラーツ、オーストリア: Springer。pp. 118–132。doi : 10.1007 / 3-540-09510-1_10。ISBN 3-540-09510-12017年10月10日時点のオリジナル（PDF）よりアーカイブ。
^ Melichar、Borivoj、Jan Holub、J. Polcar。テキスト検索アルゴリズム。第 1 巻: 前方文字列マッチング。第 1 巻。全 2 巻、2005 年。http://stringology.org/athens/TextSearchingAlgorithms/ 2016 年 3 月 4 日にWayback Machineにアーカイブされました。
^ Riad Mokadem、Witold Litwin http://www.cse.scu.edu/~tschwarz/Papers/vldb07_final.pdf (2007)、代数署名を使用してエンコードされたデータに対する高速 nGram ベースの文字列検索、第 33 回国際大規模データベース会議 (VLDB) {{citation}}:外部リンク|surname2=(ヘルプ)CS1 maint: numeric names: authors list (link)
^ ゴンサロ・ナバロ、マシュー・ラフィノ（2008）、柔軟なパターンマッチング文字列：テキストと生物学的配列の実用的なオンライン検索アルゴリズム、ケンブリッジ大学出版局、ISBN 978-0-521-03993-2

RS BoyerとJS Moore、「高速文字列検索アルゴリズム」、 Carom。ACM 20、(10)、262–272(1977)。
Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズム入門、第3版。MIT Press and McGraw-Hill、2009年。ISBN 0-262-03293-7。第32章：文字列マッチング、pp. 985–1013。

外部リンク

パターンマッチングリンクの膨大なリスト最終更新日: 2008/12/27 20:18:38
文字列マッチングアルゴリズムの大規模な（メンテナンスされた）リスト
NIST 文字列マッチングアルゴリズムのリスト
StringSearch – Java での高性能パターンマッチングアルゴリズム – Java での多数の文字列マッチングアルゴリズムの実装 (BNDM、Boyer-Moore-Horspool、Boyer-Moore-Horspool-Raita、Shift-Or)
StringsAndChars – Java での多数の文字列マッチングアルゴリズム (単一パターンおよび複数パターン用) の実装
正確な文字列マッチングアルゴリズム - Java でのアニメーション、多数のアルゴリズムの詳細な説明と C 実装。
(PDF) 単一および複数の近似文字列マッチングの改善 2017-03-11 にWayback Machineでアーカイブ
Kalign2: 外部特徴を考慮したタンパク質およびヌクレオチド配列の高性能多重アラインメント
NyoTengu – C での高性能パターンマッチングアルゴリズム – C でのベクトルおよびスカラー文字列マッチングアルゴリズムの実装

[1] Kurtz, Stefan; Phillippy, Adam; Delcher, Arthur L; Smoot, Michael; Shumway, Martin; Antonescu, Corina; Salzberg, Steven L (2004). 「大規模ゲノムを比較するための多用途でオープンなソフトウェア」.ゲノム生物学. 5 (2): R12. doi : 10.1186/gb-2004-5-2-r12 . ISSN 1465-6906. PMC 395750. PMID 14759262 .

[2] Khan, Zia; Bloom, Joshua S.; Kruglyak, Leonid; Singh, Mona (2009-07-01). 「スパースサフィックスアレイを使用して大規模なシーケンスデータセットで最大の完全一致を見つけるための実用的なアルゴリズム」.バイオインフォマティクス. 25 (13): 1609–1616. doi :10.1093/bioinformatics/btp275. PMC 2732316. PMID 19389736 .

[3] Crochemore, Maxime; Perrin, Dominique (1991年7月1日). 「双方向文字列マッチング」(PDF) . Journal of the ACM . 38 (3): 650–674. doi :10.1145/116825.116845. S2CID 15055316. 2021年11月24日時点のオリジナルよりアーカイブ(PDF ) . 2019年4月5日閲覧。

[4] Navarro, Gonzalo; Raffinot, Mathieu (1998). 「サフィックスオートマトンへのビット並列アプローチ: 高速拡張文字列マッチング」( PDF) .組み合わせパターンマッチング.コンピュータサイエンスの講義ノート。第 1448 巻。Springer Berlin Heidelberg。pp. 14–33。doi :10.1007/bfb0030778。ISBN 978-3-540-64739-3. 2019年1月5日にオリジナルからアーカイブ（PDF）されました。2019年11月22日閲覧。

[5] ^ Fan, H.; Yao, N .; Ma, H. (2009 年 12 月)。「Backward-Oracle-Marching アルゴリズムの高速バリアント」(PDF)。2009年第 4 回科学技術のためのインターネットコンピューティングに関する国際会議。pp. 56–59。doi : 10.1109/ICICSE.2009.53。ISBN 978-1-4244-6754-9. S2CID 6073627. 2022年5月10日時点のオリジナルよりアーカイブ。2019年11月22日閲覧。

[6] “glibc/string/str-two-way.h”. 2020年9月20日時点のオリジナルよりアーカイブ。2022年3月22日閲覧。

[7] “musl/src/string/memmem.c”. 2020年10月1日時点のオリジナルよりアーカイブ。2019年11月23日閲覧。

[:0-8] Hume; Sunday (1991). 「高速文字列検索」.ソフトウェア: 実践と経験. 21 (11): 1221–1248. doi :10.1002/spe.4380211105. S2CID 5902579.

[Commentz-Walter-9] Commentz-Walter, Beate (1979). 平均的に高速な文字列マッチングアルゴリズム(PDF) .オートマトン、言語、プログラミングに関する国際コロキウム. LNCS . 第 71 巻。グラーツ、オーストリア: Springer。pp. 118–132。doi : 10.1007 / 3-540-09510-1_10。ISBN 3-540-09510-12017年10月10日時点のオリジナル（PDF）よりアーカイブ。

[10] Melichar、Borivoj、Jan Holub、J. Polcar。テキスト検索アルゴリズム。第 1 巻: 前方文字列マッチング。第 1 巻。全 2 巻、2005 年。http://stringology.org/athens/TextSearchingAlgorithms/ 2016 年 3 月 4 日にWayback Machineにアーカイブされました。

[11] Riad Mokadem、Witold Litwin http://www.cse.scu.edu/~tschwarz/Papers/vldb07_final.pdf (2007)、代数署名を使用してエンコードされたデータに対する高速 nGram ベースの文字列検索、第 33 回国際大規模データベース会議 (VLDB) {{citation}}:外部リンク|surname2=(ヘルプ)CS1 maint: numeric names: authors list (link)

[12] ゴンサロ・ナバロ、マシュー・ラフィノ（2008）、柔軟なパターンマッチング文字列：テキストと生物学的配列の実用的なオンライン検索アルゴリズム、ケンブリッジ大学出版局、ISBN 978-0-521-03993-2

概要