| Creator |
|
|
|
| Language |
|
| Publisher |
|
| Date |
|
| Source Title |
|
| Vol |
|
| Issue |
|
| First Page |
|
| Last Page |
|
| Publication Type |
|
| Access Rights |
|
| Rights |
|
| Related DOI |
|
|
|
| Related URI |
|
|
|
| Relation |
|
|
|
| Abstract |
半構造テキスト中から自明でない情報を取り出す技術である，データマイニング，あるいはテキストマイニングは，拡大する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.show more
|
Export Mendeley
2003_b_3