Loading article…
文字列検索アルゴリズム（文字列照合アルゴリズムとも呼ばれる）とは、テキストの中からパターンに一致する部分を検索するアルゴリズムである。
文字列検索の基本的な例としては、パターンと検索対象のテキストがアルファベット（有限集合）Σの要素の配列である場合が挙げられます。Σは、例えばAからZまでの文字である人間の言語のアルファベットである場合もあれば、バイオインフォマティクスなどの他のアプリケーションでは、バイナリアルファベット（Σ = {0,1}）やDNAアルファベット（Σ = {A,C,G,T}）を使用する場合もあります。
実際には、実行可能な文字列検索アルゴリズムの方法は、文字列のエンコーディングによって影響を受ける可能性があります。特に、可変長エンコーディングが使用されている場合、N番目の文字を見つけるのに時間がかかり、 Nに比例する時間が必要になる場合があります。これは、一部の検索アルゴリズムの速度を著しく低下させる可能性があります。考えられる解決策の 1 つは、代わりにコード単位のシーケンスを検索することですが、エンコーディングがそれを回避するように特別に設計されていない限り、誤った一致が発生する可能性があります。
文字列検索の最も基本的なケースは、1つの（多くの場合非常に長い）文字列（干し草の山と呼ばれることもある）と、1つの（多くの場合非常に短い）文字列（針と呼ばれることもある）を用いるものです。目標は、干し草の山の中から針が1回以上出現する箇所を見つけることです。例えば、次のような文字列の中から「to」を検索する場合があります。
本には味わうべきものもあれば、飲み込むべきものもあり、ごく少数の本は噛み砕いて消化すべきものだ。
「to」の最初の出現箇所（4番目の単語）を要求することも、すべての出現箇所（3回）を要求することも、最後の出現箇所（最後から5番目の単語）を要求することもできる。
しかし、非常に一般的には、さまざまな制約が追加されます。たとえば、「needle」という単語が1つ（または複数）の完全な単語で構成されている場合にのみ一致させたい場合などです。完全な単語とは、おそらく、その両側に他の文字が隣接していない単語のことです。この場合、上記の例文では、「hew」や「low」といった文字列は確かに存在しますが、これらの文字列を検索しても失敗します。
もう一つのよくある例は「正規化」です。多くの場合、「to be」のようなフレーズの検索は、「to」と「be」の間に何か別のものが介在している場合でも成功するはずです。
多くの記号体系には、（少なくとも一部の目的においては）同義の文字が含まれています。
最後に、自然言語を表す文字列の場合、言語自体の側面が関係してきます。例えば、綴りの異なる単語、接頭辞、接尾辞などがあっても、その単語のすべての出現箇所を見つけたい場合などが考えられます。
もう一つのより複雑な検索方法は正規表現検索です。これは、ユーザーが文字やその他の記号のパターンを作成し、そのパターンに一致するものがあれば検索が成立するというものです。例えば、アメリカ英語の「color」とイギリス英語の「colour」の両方を検索するには、2つの異なる文字列を検索する代わりに、次のような正規表現を使用できます。
色
ここで「?」は慣例として、直前の文字（「u」）を省略可能にする。
この記事では主に、より単純な文字列検索のためのアルゴリズムについて解説します。
バイオインフォマティクスとゲノミクスの分野で導入された同様の問題は、最大完全一致 (MEM) です。[ 1 ] 2 つの文字列が与えられたとき、MEM は、不一致を引き起こすことなく左右に拡張できない共通の部分文字列です。[ 2 ]
ある文字列が別の文字列の中にどこに含まれているかを調べる単純で非効率的な方法は、インデックスを 1 つずつチェックすることです。まず、干し草の山の最初の文字から始まる針のコピーがあるかどうかを確認します。ない場合は、干し草の山の 2 番目の文字から始まる針のコピーがあるかどうかを確認し、以下同様に続けます。通常の場合、間違った位置が間違っていることを確認するために、各間違った位置について 1 つまたは 2 つの文字だけを確認すればよいので、平均的な場合、これにはO ( n + m ) ステップかかります。ここで、nは干し草の山の長さ、mは針の長さです。しかし、最悪の場合、"aaaaaaaaab" のような文字列の中に "aaaab" のような文字列を検索すると、 O ( nm )かかります。
この手法では、保存された検索文字列を認識する決定性有限オートマトン（DFA）を構築することで、バックトラッキングを回避します。DFAの構築にはコストがかかりますが（通常は冪集合構成を用いて作成されます）、使用は非常に高速です。例えば、右図のDFAは「MOMMY」という単語を認識します。この手法は、実際には任意の正規表現の検索に一般化されることがよくあります。
Knuth–Morris–Pratt アルゴリズムは、検索対象の文字列を接尾辞として認識するDFAを計算します。Boyer –Moore アルゴリズムは、ニードルの末尾から検索を開始するため、通常は各ステップでニードルの長さ分だけ先に進むことができます。Baeza–Yates アルゴリズムは、前のj文字が検索文字列の接頭辞であったかどうかを追跡するため、あいまい文字列検索にも適用可能です。bitapアルゴリズムは、Baeza–Yates アルゴリズムの応用例です。
より高速な検索アルゴリズムはテキストを前処理します。部分文字列インデックス（例えば、接尾辞ツリーや接尾辞配列）を構築した後、パターンの出現箇所を素早く見つけることができます。例として、接尾辞ツリーは次のように構築できます。時間、そしてすべてパターンの出現は、アルファベットのサイズが一定であり、接尾辞ツリー内のすべての内部ノードがその下にある葉を知っているという前提の下で、時間を計算する。後者は、接尾辞ツリーのルートから深さ優先探索（DFS）アルゴリズムを実行することで実現できる。
トリグラム検索など、一部の検索方法は、「一致／不一致」ではなく、検索文字列とテキスト間の「類似度」スコアを求めることを目的としています。これらは「あいまい検索」と呼ばれることもあります。
様々なアルゴリズムは、それぞれが使用するパターンの数によって分類することができる。
以下のコンパイルでは、mはパターンの長さ、n は検索可能なテキストの長さ、k = |Σ| はアルファベットのサイズです。
Boyer –Moore文字列検索アルゴリズムは、実用的な文字列検索に関する文献における標準的なベンチマークとなっている。[ 8 ]
以下のコンパイルでは、Mは最長のパターンの長さ、mはパターンの全長、nは検索可能なテキストの長さ、oは出現回数です。
当然ながら、この場合、パターンを有限個に列挙することはできません。それらは通常、正規文法または正規表現によって表現されます。
他の分類手法も可能である。最も一般的な手法の一つは、前処理を主要な基準として用いるものである。
もう1つは、アルゴリズムをマッチング戦略によって分類するものです。[ 12 ]
リアルタイム文字列マッチングでは、マッチング器はテキストの各文字を読み取った後に、それがマッチングの最後の文字であるかどうかを示す応答を出力する必要があります。応答は定数時間内に提供されなければなりません。前処理に関する要件は様々です。パターンを読み取った後（ただしテキストを読み込む前）にO( m )の前処理が許可される場合もあれば、マッチング器がパターンの任意の文字（最後の文字を含む）を読み取った後に最大で定数時間一時停止する必要があるという、より厳しい要件が課される場合もあります。前処理時間とメモリ要件がアルファベットのサイズに依存することを気にしない、より寛容なバージョンでは、オートマトンマッチングによってリアルタイムソリューションが提供されます。Zvi Galilは、特定のアルゴリズムをリアルタイムアルゴリズムに変換する方法を開発し、それを適用して、厳しい要件の下でリアルタイムに動作するKMPマッチング器のバリアントを作成しました。[ 13 ]
このバージョンの文字列検索問題では、特別な記号 ø (読み方: 気にしない) があり、これは他の任意の記号 (別の ø を含む) と一致できます。気にしない記号は、パターンまたはテキストのどちらにも出現する可能性があります。2002 年に、この問題に対するアルゴリズムが開発され、リチャード・コールとラメシュ・ハリハランによって、1973年のフィッシャーとパターソンの解法を改良した 複雑な解法が提案されている。ここで、kはアルファベットのサイズです。[ 14 ]より単純だとされる別のアルゴリズムがクリフォードとクリフォード によって提案されています。[ 15 ]
