文字列探索とは? わかりやすく解説

文字列探索

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2024/07/13 14:05 UTC 版)

文字列探索 (もじれつたんさく) とは、ある文字列の中から、別の文字列(単一の文字列である場合もあれば、数千語から数万語以上の辞書の語彙である場合もある)を探索することである。前者の単一の文字列の探索は英文のテキストエディタ等で必須の機能であり(いわゆるスペルチェックと関連する)、後者は「かな漢字変換」等で必須の機能であるため、これまでさまざまなアルゴリズムが考案されている。

ここでいう文字列とは、ある定まった文字集合の要素を任意に並べた系列のことである。通常、文字はアルファベット等の言語に依拠した文字セットを指すことが多いが、生物情報学における染色体の塩基配列A, T, G, Cの4文字を対象とするもののように、特定の領域に特化した応用も行われている。

正規表現にマッチする文字列の探索、と類似した問題だが、正規表現で可能なパターンに比べ検索対象を絞ることで、より高速に探索するものとして研究されている(ユーザの使うプログラムでは、検索するパターンに応じて、アルゴリズムを切り替えるものもある)。正規表現による探索については正規表現の記事を参照のこと。

近年は、暗号化された文字列を復号せずに探索する秘匿検索、圧縮テキスト中の文字列探索の研究、多国語文字列のバイト列表現に対する探索の研究、なども行われている。

探索効率

欧米語のような、空白文字列で区切られている言語のテキストに関しては、効率のよいアルゴリズムが知られている。ところが日本語のように「どこからどこまでに対して辞書引きをするか」が不明確な場合、「あるバイト列に対し、不定長のバイト列に対して検索を行う」という作業が必要となる。

こうした要求に応えるものとしてトリプル配列法(および、トリプル配列法のスペースファクターを改善する目的で開発されたダブル配列法)があるが、ジップの法則によって、「頻出するバイト列にのみ対処すれば、出現頻度の少ないものに対しては、他の(実行効率の低い)アルゴリズムを用いても、システム全体のスループットには、ほとんど影響しない」という経験則があるため、トリプル配列法はあまり知られていない。

各種アルゴリズム

外部リンク


文字列探索

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/04/15 03:07 UTC 版)

探索」の記事における「文字列探索」の解説

詳細は「文字列探索」を参照 文字列内のパターン探索する接尾辞木などのデータ構造効率化することもある。 クヌース-モリス-プラット法 ボイヤー-ムーア文字列検索アルゴリズム エイホ-コラシック法 ラビン-カープ文字列検索アルゴリズム Bitapアルゴリズム 複数ファイルにまたがる物を全文検索という。

※この「文字列探索」の解説は、「探索」の解説の一部です。
「文字列探索」を含む「探索」の記事については、「探索」の概要を参照ください。

ウィキペディア小見出し辞書の「文字列探索」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「文字列探索」の関連用語

文字列探索のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



文字列探索のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの文字列探索 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの探索 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS