| 講演名 | 2003/7/10 FETを用いた繰り返しパターン発見手法の提案(パターン抽出)(「夏のデータベースワークショップ(DBWS2003)」一般) 中藤 哲也, 廣川 佐千男, |
|---|---|
| PDFダウンロードページ | PDFダウンロードページへ |
| 抄録(和) | 半構造テキスト中から自明でない情報を取り出す取り出す技術である,データマイニング,あるいはテキストマイニングは,拡大するWWW上の情報を取り扱う上で非常に重要である.その技術の一つとして,対象のデータに繰り返し出現するパターンを発見する問題がある.発見されたパターンを用いることで,そのデータを加工する,あるいはデータから新たな情報を抽出する事が可能となる.繰り返しパターンを発見する方法として,対象となるデータをそれ自身のコピーと位置をずらして重ね,ー致部分を見つける素朴な方法が考えられる.しかしこの方法は,テキストのサイズnに対して計算量がO(n^2)となり,大きなデータに対しては現実的でない.本研究では,我々が提唱しているFFTを用いた効率的な近似文字列照合アルゴリズムを適用し, O(n log n)の計算量で繰り返しパターンを発見する手法について提案する. |
| 抄録(英) | 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. |
| キーワード(和) | 繰り返しパターン発見 / マイニング / 半構造データ / 近似文字列照合 / 検索エンジン / FET |
| キーワード(英) | Finding Repetitive Patterns / Mining / Semi-structured Text / String Matching with Mismatches / Search Engine / FET |
| 資料番号 | DE2003-48 |
| 発行日 |
| 研究会情報 | |
| 研究会 | DE |
|---|---|
| 開催期間 | 2003/7/10(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Data Engineering (DE) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | FETを用いた繰り返しパターン発見手法の提案(パターン抽出)(「夏のデータベースワークショップ(DBWS2003)」一般) |
| サブタイトル（和） | |
| タイトル（英） | Finding Repetitive Patterns Using FET |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 繰り返しパターン発見 / Finding Repetitive Patterns |
| キーワード(2)（和/英） | マイニング / Mining |
| キーワード(3)（和/英） | 半構造データ / Semi-structured Text |
| キーワード(4)（和/英） | 近似文字列照合 / String Matching with Mismatches |
| キーワード(5)（和/英） | 検索エンジン / Search Engine |
| キーワード(6)（和/英） | FET / FET |
| 第 1 著者 氏名（和/英） | 中藤 哲也 / Tetsuya NAKATOH |
| 第 1 著者 所属（和/英） | 九州大学情報基盤センター Computing and Communications Center, Kyushu University |
| 第 2 著者 氏名（和/英） | 廣川 佐千男 / Sachio HIROKAWA |
| 第 2 著者 所属（和/英） | 九州大学情報基盤センター Computing and Communications Center, Kyushu University |
| 発表年月日 | 2003/7/10 |
| 資料番号 | DE2003-48 |
| 巻番号（vol） | vol.103 |
| 号番号（no） | 191 |
| ページ範囲 | pp.- |
| ページ数 | 6 |
| 発行日 | |