<会議発表論文>
FFTを用いた繰り返しパターン発見手法の提案

作成者
本文言語
出版者
発行日
雑誌名
開始ページ
終了ページ
出版タイプ
アクセス権
概要 半構造テキスト中から自明でない情報を取り出す技術である,データマイニング,あるいはテキストマイニングは,拡大するWWW上の情報を取り扱う上で非常に重要である.その技術の一つとして,対象のデータに繰り返し出現するパターンを発見する問題がある.発見されたパターンを用いることで,そのデータを加工する,あるいはデータから新たな情報を抽出する事が可能となる.繰り返しパターンを発見する方法として,対象となるデ...ータをそれ自身のコピーと位置をずらして重ね,一致部分を見つける素朴な方法が考えられる.しかしこの方法は,テキストサイズnに対して計算量がO(n2)となり,大きなデータに対しては現実的ではない.本研究では,我々が提唱しているFFTを用いた効率的な近似文字列照合アルゴリズムを適用し,O(nlogn)の計算量で繰り返しパターンを発見する手法について提案する.
Data-Mining or Text-Mining, that is technique to extract non-obvious information from semi-structured texts, has been very important technologies when we handle expanding information in WWW. One of them is to discover patterns that appear in the data repetitively. Using the patterns, we can process the data and can extract from the data. To discover them, we can think about the naive method, i.e. the method of aligning data with that own shifted copy data, and compare them. However, when the size of the text is n, time complexity of this method becomes O(n^2), and it isn't efficient for big data. In this paper, we propose the technique to reduce time complexity of the method to O(n log n) using our string matching algorithm with mismatches.
続きを見る

本文情報を非表示

2003_b_3 pdf 742 KB 123  

詳細

レコードID
査読有無
権利関係
関連情報
主題
注記
タイプ
登録日 2009.04.22
更新日 2017.01.19

この資料を見た人はこんな資料も見ています