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

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 文字列検索の意味・解説 

文字列探索

(文字列検索 から転送)

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

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

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

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

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

探索効率

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

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

各種アルゴリズム

外部リンク




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

辞書ショートカット

すべての辞書の索引

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

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

   

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



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

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

©2025 GRAS Group, Inc.RSS