| 作成者 |
|
|
|
|
|
|
|
| 本文言語 |
|
| 出版者 |
|
|
|
| 発行日 |
|
| 収録物名 |
|
| 巻 |
|
| 号 |
|
| 開始ページ |
|
| 終了ページ |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
| 関連DOI |
|
|
|
| 関連URI |
|
|
|
| 関連URI |
|
| 関連HDL |
|
| 関連情報 |
|
|
|
| 概要 |
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) を利用した高速な確率アルゴリズムが幾つか提案されている．それらは文字から数値への写像の生成方法により，写像総数と，解の推定値の分散が異なる．本稿で提案するアルゴリズムは，総写像数が理論上での最小であり，推定値の分散も小さい．続きを見る
|
Mendeley出力
