<学術雑誌論文>
不一致を許す文字列照合のためのFFTを用いた確率的アルゴリズムの精度評価

作成者
本文言語
出版者
発行日
収録物名
開始ページ
終了ページ
出版タイプ
アクセス権
概要 String matching is the problem of finding all occurrences of a given pattern string in a given text string. It is applicable to a wide range of fields, such as Web information retrieval and pattern di...scovery of DNA sequences. The string matching with mismatches allows inexact match with substitution and has high complexity. In order to solve the problem several fast randomized algorithms have been proposed. They use the fast Fourier transformation (FFT). All of these algorithms introduce a certain number of mappings that convert symbols into numbers. The total number of such mappings and variance of estimates depends on the method to generate the mappings. This paper proposes an algorithm that achieves the theoretically minimum number of mappings and yields accurate estimates. Empirical evaluation is conducted to compare the accuracy of estimates of the proposed algorithm with that of Atallah et al. It is confirmed that the accuracy of the proposed algorithm is better.
テキスト中から与えられたパターンを見つけ出す文字列照合問題は,Webの情報検索やDNA配列の特定パターンの検索に用いられるなど,幅広い応用範囲を持つ.パターンの編集に置換のみを許した近似文字列照合は,不一致を許す文字列照合と呼ばれ,テキスト全域での一致スコアを求めるために,正確な一致場所を求める文字列照合よりも計算量が大きい.この問題の解法として,高速フーリエ変換(FFT)を利用した高速な確率的アルゴリズムがいくつか提案されており,それらは文字から数値への写像の生成方法により,写像の総数と,得られる推定値の精度が異なる.我々の提案するアルゴリズム10)は写像の総数が理論上での最小であり,精度も提案されているアルゴリズム中で最も高い.本稿では,Atallah らのアルゴリズム1)による推定値の精度と実験的な比較を行い,提案アルゴリズムの推定値の精度がより高いことを確認した.
続きを見る

本文情報を非表示

hirokawa_129 pdf 378 KB 45  

詳細

レコードID
査読有無
権利関係
主題
ISSN
NCID
注記
登録日 2013.12.09
更新日 2020.10.26

この資料を見た人はこんな資料も見ています