文字列アルゴリズム
文字列アルゴリズムは、記号のシーケンス（テキスト、DNA、その他の線形データ）を処理し、パターンを検索し、大規模なテキストを高速検索のためにインデックス化し、類似性によってシーケンスをアラインメントするものです。
Definition
文字列アルゴリズムとは、アルファベットから抽出された文字の有限シーケンスである文字列を操作し、パターン特定、高速検索のためのインデックス作成、シーケンス間の類似性の測定やアラインメントといった問題を解決するための手順およびデータ構造です。
Scope
この分野は、文字列に特化したアルゴリズムとデータ構造を扱います。具体的には、厳密および近似パターンマッチング、繰り返しクエリのためにテキストを前処理するインデックス構造（トライ、接尾辞木、接尾辞配列）、および文字列を比較するためのシーケンスアラインメント手法が含まれます。これは、動的計画法（アラインメント）、データ構造（木と配列）、計算生物学、テキスト検索、自然言語処理の応用と関連しています。
Sub-topics
Core questions
- 素朴な文字ごとの比較よりも速く、テキスト内のパターンを特定するにはどうすればよいか？
- 多くの後続クエリが高速になるように、大規模なテキストを前処理するにはどうすればよいか？
- 2つの文字列間の類似性はどのように定義され、計算されるか？
- アルファベットのサイズと文字列の長さは、文字列アルゴリズムの効率にどのように影響するか？
- 厳密一致法は、近似一致や複数パターン一致にどのように拡張されるか？
Key concepts
- アルファベットと文字列
- 厳密パターンマッチング
- Knuth-Morris-PrattとBoyer-Moore
- トライ
- 接尾辞木と接尾辞配列
- 編集距離
- シーケンスアラインメント
- 近似マッチング
Key theories
- 線形時間厳密パターンマッチング
- 部分一致からの情報を利用してパターンを前処理することにより、Knuth-Morris-PrattやBoyer-Mooreなどのアルゴリズムは、テキスト長に線形な時間でパターンのすべての出現箇所を見つけ、素朴なマッチングの二次的なコストを回避します。
- テキストのインデックス構造
- 接尾辞木と接尾辞配列はテキストを前処理し、任意のパターンクエリ、繰り返し、最長共通部分文字列の質問に迅速に答えることを可能にします。これは、構築コストを犠牲にして、繰り返される検索を高速化するものです。
Clinical relevance
文字列アルゴリズムは、テキスト検索とバイオインフォマティクスにおいて基礎的なものです。パターンマッチングは、検索ユーティリティ、テキストエディタ、侵入検知の基盤となり、接尾辞構造は検索エンジンやゲノムデータベースをインデックス化し、シーケンスアラインメントは分子生物学におけるDNA、RNA、タンパク質シーケンスの比較の中心となります。
History
効率的な文字列マッチングは、Knuth-Morris-Pratt (1977) および Boyer-Moore (1977) アルゴリズムとともに1970年代に登場しました。接尾辞木 (Weiner, 1973; McCreight, 1976; Ukkonen, 1995) およびその後の接尾辞配列 (Manber and Myers, 1990) は強力なインデックス作成機能を提供し、Gusfieldの1997年のテキストで概説されたように、計算生物学を通じてこの分野は急速に拡大しました。
Key figures
- Donald Knuth
- James H. Morris
- Vaughan Pratt
- Robert Boyer
- J Strother Moore
- Dan Gusfield
Related topics
Seminal works
- knuth1977
- gusfield1997
- cormen2009
Frequently asked questions
- 直接検索する代わりに、パターンやテキストを前処理するのはなぜですか？
- 素朴なマッチングは、パターンとテキストの長さの積に比例する時間がかかる場合があります。パターンを前処理する（Knuth-Morris-Prattのように）ことで線形時間の検索が可能になり、テキストをインデックス（接尾辞木や配列）に前処理することで、多くの後続クエリがそれぞれはるかに高速に実行できるようになります。これは、同じテキストが繰り返し検索される場合に効果を発揮します。
- 文字列アルゴリズムは生物学でどのように使われていますか？
- DNA、RNA、タンパク質は自然に文字列として表現されるため、パターンマッチングはモチーフを特定し、接尾辞構造はゲノムを高速検索のためにインデックス化し、シーケンスアラインメントアルゴリズムはシーケンス間の類似性を定量化して、進化的関係と機能を推定します。