FFTを用いた繰り返しパターン発見手法の提案(セッション5B : パターン抽出) 

中藤 哲也
広川 佐千男

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

情報処理学会研究報告. データベース・システム研究会報告

情報処理学会

09196072

110002911214

http://ci.nii.ac.jp/naid/110002911214
http://ci.nii.ac.jp/ncid/AN10112482
http://id.ndl.go.jp/bib/6676534
http://hdl.handle.net/2324/2964