電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2008-06-19 14:00
編集距離による最類似文字列の探索高速化に関する研究
花田博幸工藤峰一北大
技報オンラインサービス実施中
抄録 (和) 文字列の集合$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 / / /  
文献情報 信学技報, vol. 108, no. 94, PRMU2008-26, pp. 41-46, 2008年6月.
資料番号 PRMU2008-26 
発行日 2008-06-12 (DE, PRMU) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 PRMU DE  
開催期間 2008-06-19 - 2008-06-20 
開催地(和) 小樽市民会館 
開催地(英) Otaru-Shimin-Kaikan 
テーマ(和) 膨大なデータから学ぶもの 
テーマ(英)  
講演論文情報の詳細
申込み研究会 PRMU 
会議コード 2008-06-PRMU-DE 
本文の言語 日本語 
タイトル(和) 編集距離による最類似文字列の探索高速化に関する研究 
サブタイトル(和)  
タイトル(英) 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  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 花田 博幸 / Hiroyuki Hanada / ハナダ ヒロユキ
第1著者 所属(和/英) 北海道大学 (略称: 北大)
Hokkaido University (略称: Hokkaido Univ.)
第2著者 氏名(和/英/ヨミ) 工藤 峰一 / Mineichi Kudo / クドウ ミネイチ
第2著者 所属(和/英) 北海道大学 (略称: 北大)
Hokkaido University (略称: Hokkaido Univ.)
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2008-06-19 14:00:00 
発表時間 30 
申込先研究会 PRMU 
資料番号 IEICE-DE2008-8,IEICE-PRMU2008-26 
巻番号(vol) IEICE-108 
号番号(no) no.93(DE), no.94(PRMU) 
ページ範囲 pp.41-46 
ページ数 IEICE-6 
発行日 IEICE-DE-2008-06-12,IEICE-PRMU-2008-06-12 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会