FFT を用いた繰り返しパターン発見手法の提案

中藤 哲也
廣川 佐千男

半構造テキスト中から自明でない情報を取り出す取り出す技術である,データマイニング,あるいはテキストマイニングは,拡大するWWW上の情報を取り扱う上で非常に重要である.その技術の一つとして,対象のデータに繰り返し出現するパターンを発見する問題がある.発見されたパターンを用いることで,そのデータを加工する,あるいはデータから新たな情報を抽出する事が可能となる.繰り返しパターンを発見する方法として,対象となるデータをそれ自身のコピーと位置をずらして重ね,ー致部分を見つける素朴な方法が考えられる.しかしこの方法は,テキストのサイズnに対して計算量がO(n^2)となり,大きなデータに対しては現実的でない.本研究では,我々が提唱しているFFTを用いた効率的な近似文字列照合アルゴリズムを適用し, O(n log n)の計算量で繰り返しパターンを発見する手法について提案する.

電子情報通信学会技術研究報告. DE, データ工学

一般社団法人電子情報通信学会

http://ci.nii.ac.jp/naid/110003174639
http://ci.nii.ac.jp/ncid/AN10012921
http://id.ndl.go.jp/bib/6676817