<学術雑誌論文>
FFTを用いた近似文字列照合のスコア計算のための最適な写像

作成者
本文言語
出版者
発行日
収録物名
開始ページ
終了ページ
出版タイプ
アクセス権
関連URI
概要 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. An extension of the string matching is string matching with mismatches, which allows inexact match with substitution, is expected to have wider application even though it has higher complexity. Several randomized algorithms have been proposed which use fast Fourier transformation (FFT) and run fast to solve the problem. All of these algorithms introduce 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. The present paper shows an algorithm which achieves the theoretical minimum number of mappings, and yields an estimate with small variance.
文字列中から与えられたパターンを見つけ出す文字列照合問題は,Web の情報検索やDNA 配列の特定パターンの検索に用いられるなど,幅広い応用範囲を持つ.パターンの編集に置換のみを許した近似文字列照合は,不一致を許す文字列照合と呼ばれ,単なる文字列照合より応用範囲が広く,また難易度も高い.この問題の解法として,高速フーリエ変換(FFT) を利用した高速な確率アルゴリズムが幾つか提案されている.それらは文字から数値への写像の生成方法により,写像総数と,解の推定値の分散が異なる.本稿で提案するアルゴリズムは,総写像数が理論上での最小であり,推定値の分散も小さい.
続きを見る

本文情報を非表示

nakatoh pdf 102 KB 50  

詳細

レコードID
査読有無
関連情報
主題
タイプ
登録日 2009.04.22
更新日 2020.02.10

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