| 講演名 | 2008-06-19 編集距離による最類似文字列の探索高速化に関する研究(テーマ,膨大なデータから学ぶもの) 花田 博幸, 工藤 峰一, |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 文字列の集合T(索引の作成を許す)の中から,クエリ文字列qとの編集距離が最小となる要素を求める問題を考える.この探索を高速化する索引付けの方法として,従来はTの要素同士の距離の関係に基づき索引を作るものが主であった.これに対し我々は,要素が文字列であることを積極的に利用した索引付けを考え,索引付けおよび探索を高速化する.本研究では,編集距離の近似としてn-gram距離を導入し,距離空間における探索木の一つであるVP木の構築を高速化する.実験の結果,探索速度を落とさずに,VP木構築の時間を編集距離をそのまま用いる場合に比べて8分の1に削減できた. |
| 抄録(英) | The problem is finding the nearest string, measured by edit distance, to a query string q from a set T of strings. Here indexing of T is assumed. Conventional indexing methods construct indexes mainly from the distances between elements in T. In the proposed method, the nature of strings is introduced to enhancing indexing and searching. We introduce n-gram distance as an approximation of edit distance for faster construction of the VP-trees which are search trees in metric spaces. The method succeeded to speed up the construction of VP-trees at a factor of 1/8, without increasing searching time. |
| キーワード(和) | 文字列 / 編集距離 / 最近隣(Nearest Neighbor)法 / 索引付け / 探索木 |
| キーワード(英) | String / Edit Distance / Nearest Neighbor Method / Indexing / Search Tree |
| 資料番号 | DE2008-8,PRMU2008-26 |
| 発行日 |
| 研究会情報 | |
| 研究会 | PRMU |
|---|---|
| 開催期間 | 2008/6/12(から1日開催) |
| 開催地（和） | |
| 開催地（英） | |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | |
| 委員長氏名（英） | |
| 副委員長氏名（和） | |
| 副委員長氏名（英） | |
| 幹事氏名（和） | |
| 幹事氏名（英） | |
| 幹事補佐氏名（和） | |
| 幹事補佐氏名（英） | |
| 講演論文情報詳細 | |
| 申込み研究会 | Pattern Recognition and Media Understanding (PRMU) |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | 編集距離による最類似文字列の探索高速化に関する研究(テーマ,膨大なデータから学ぶもの) |
| サブタイトル（和） | |
| タイトル（英） | A study on fast search of the nearest string in edit distance |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 文字列 / String |
| キーワード(2)（和/英） | 編集距離 / Edit Distance |
| キーワード(3)（和/英） | 最近隣(Nearest Neighbor)法 / Nearest Neighbor Method |
| キーワード(4)（和/英） | 索引付け / Indexing |
| キーワード(5)（和/英） | 探索木 / Search Tree |
| 第 1 著者 氏名（和/英） | 花田 博幸 / Hiroyuki HANADA |
| 第 1 著者 所属（和/英） | 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University |
| 第 2 著者 氏名（和/英） | 工藤 峰一 / Mineichi KUDO |
| 第 2 著者 所属（和/英） | 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University |
| 発表年月日 | 2008-06-19 |
| 資料番号 | DE2008-8,PRMU2008-26 |
| 巻番号（vol） | vol.108 |
| 号番号（no） | 94 |
| ページ範囲 | pp.- |
| ページ数 | 5 |
| 発行日 | |