誤りを許したVLDCパタン照合アルゴリズム VLDC Pattern Matching Algorithm with Arrowing Errors

この論文をさがす

著者

抄録

VLDCパタンとは,任意の文字列と一致するメタ記号'*'を含む文字列パタンである.いま,VLDCパタンPに対して,Pと一致する文字列の集合をPとする.このとき,VLDCパタンに対する文字列照合問題とは,与えられた文字列T中に,あるq∈Pが存在するかどうかを答えることである.今回,P中の'*'以外の部分においてk個以下の不一致を許した近似照合問題に取り組んだ.本論文では,この問題を解く三つのアルゴリズムを提案する.一つは,動的計画法に基づく近似文字列照合アルゴリズムの変形であり,mをPの長さ,nをTの長さとすると,O(mn)時間で動作する.二つ目は,ビットパラレル手法を用いて動的計画法の計算を模倣するアルゴリズムである.もう一つは,ビットパラレル手法を用いて非決定性オートマトンの動作を模倣するアルゴリズムである.マシンのワード長をwとすると,各々,O(⌈(⌈log(k+1)⌋+1)m/w⌋n)時間,O(⌈(m+1)/w⌋(k+1)n)時間で動作する.また,これらのアルゴリズムを実装し,照合速度の比較実験を行った.

A variable length don't care (VLDC) pattern is a string pattern including gaps that can match any strings. Let P be a VLDC pattern and P be a set of strings that match to P. Given P and a string T, the problem we address is to answer whether T includes some q ∈ P or not with at most k mismatches. We present three different types of algorithms. One is based on a dynamic programming (DP), which runs in O (mn) time, where m=|P| and n=|T|. The rests are based on bit-parallelism. One of them simulates the calculation of the DP, and another simulates the move of an NFA. They run in O(⌈(⌈log(k+1)⌋+1)m/w⌋n) time and O(⌈(m+1)/w⌋(k+1)n) time, respectively, where w is the machine word length. Finally we present the experimental results of search time comparison.

収録刊行物

  • 電子情報通信学会技術研究報告. COMP, コンピュテーション

    電子情報通信学会技術研究報告. COMP, コンピュテーション 103(622), 61-68, 2004-01-22

    一般社団法人電子情報通信学会

参考文献:  11件中 1-11件 を表示

各種コード

  • NII論文ID(NAID)
    110003202537
  • NII書誌ID(NCID)
    AN10013152
  • 本文言語コード
    JPN
  • 資料種別
    ART
  • ISSN
    09135685
  • NDL 記事登録ID
    6860387
  • NDL 雑誌分類
    ZN33(科学技術--電気工学・電気機械工業--電子工学・電気通信)
  • NDL 請求記号
    Z16-940
  • データ提供元
    CJP書誌  NDL  NII-ELS 
ページトップへ