類似部分文字列の探索
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/05/02 09:30 UTC 版)
「ハッシュ関数」の記事における「類似部分文字列の探索」の解説
同じ技法は巨大な文字列の集まりから同じ部分か類似する部分を見つけ出すのに応用できる。例えば、文書リポジトリや遺伝子データベースなどに応用できる。この場合、入力文字列群を多数の小さな部分に分割し、それらに対してハッシュ関数を適用して上述してきたような技法で同じ部分や類似の部分を探す。 ラビン-カープ文字列検索アルゴリズムは比較的高速な文字列検索アルゴリズムで、平均でO(n)の時間で動作する。このアルゴリズムは文字列の比較にハッシュ関数を使っている。
※この「類似部分文字列の探索」の解説は、「ハッシュ関数」の解説の一部です。
「類似部分文字列の探索」を含む「ハッシュ関数」の記事については、「ハッシュ関数」の概要を参照ください。
- 類似部分文字列の探索のページへのリンク