誤りを許したVLDCパタン照合アルゴリズム(<特集>文字列アルゴリズム)

概要

論文の詳細を見る
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)時間で動作する.また,これらのアルゴリズムを実装し,照合速度の比較実験を行った.
社団法人電子情報通信学会の論文
2004-01-22