編集距離による最類似文字列の探索高速化に関する研究 (パターン認識・メディア理解)  [in Japanese] A study on fast search of the nearest string in edit distance  [in Japanese]

Search this Article

Author(s)

    • 工藤 峰一 KUDO Mineichi
    • 北海道大学大学院情報科学研究科 Graduate School of Information Science and Technology, Hokkaido University

Abstract

文字列の集合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.

Journal

  • IEICE technical report

    IEICE technical report 108(94), 41-45, 2008-06-19

    The Institute of Electronics, Information and Communication Engineers

Codes

  • NII Article ID (NAID)
    110006951809
  • NII NACSIS-CAT ID (NCID)
    AN10541106
  • Text Lang
    JPN
  • Article Type
    特集
  • ISSN
    09135685
  • NDL Article ID
    9572310
  • NDL Source Classification
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL Call No.
    Z16-940
  • Data Source
    NDL  NII-ELS 
Page Top