不一致を許す文字列照合のためのFFTを用いた確率的アルゴリズムの精度評価

中藤 哲也
馬場 謙介
池田 大輔
森 雅生
廣川 佐千男

テキスト中から与えられたパターンを見つけ出す文字列照合問題は,Webの情報検索やDNA配列の特定パターンの検索に用いられるなど,幅広い応用範囲を持つ.パターンの編集に置換のみを許した近似文字列照合は,不一致を許す文字列照合と呼ばれ,テキスト全域での一致スコアを求めるために,正確な一致場所を求める文字列照合よりも計算量が大きい.この問題の解法として,高速フーリエ変換(FFT)を利用した高速な確率的アルゴリズムがいくつか提案されており,それらは文字から数値への写像の生成方法により,写像の総数と,得られる推定値の精度が異なる.我々の提案するアルゴリズム10)は写像の総数が理論上での最小であり,精度も提案されているアルゴリズム中で最も高い.本稿では,Atallah らのアルゴリズム1)による推定値の精度と実験的な比較を行い,提案アルゴリズムの推定値の精度がより高いことを確認した.

情報処理学会論文誌. データベース

一般社団法人情報処理学会

03875806

110007990064

http://ci.nii.ac.jp/naid/110007990064