| 作成者 |
|
|
|
|
|
|
|
|
|
| 本文言語 |
|
| 発行日 |
|
| 出版タイプ |
|
| アクセス権 |
|
| 関連DOI |
|
| 関連URI |
|
| 関連情報 |
|
| 概要 |
文字列中に存在する特定のパターンを見つけ出す問題は，文字列照合問題と呼ばれ，Web上の情報からの検索やDNA配列の特定パターンの検索に用いられるなど，幅広い応用範囲を持っている．近似文字列照合問題の一種である不一致を許す文字列照合問題は，単なる文字列照合問題より応用範囲が広く，また難易度も高い．我々は，高速フーリエ変換（FFT）を利用してこの問題の解を高速に計算する効率的なアルゴリズムを提案する．...すべての位置でのマッチングのスコアを求めるもので，ミスマッチ数に制限はない．すなわちk-mismatch問題より難易度が高い．本アルゴリズムは，k個のサンプルを用いた確率アルゴリズムで，計算量はO(knlogm)である．このkは1≦k≦|Σ|の範囲を持ち，k=|Σ|においては常に正しいスコアが得られる決定性アルゴリズムとなる．すなわち，本アルゴリズムにおいては，精度と計算量の兼ね合いを，正確なスコアベクトルを得る事も含め自由に選ぶことが可能である．
The problem to find out a pattern from the string is called String matching problem. That has a wide application range, such as text search, search form the database and an information extraction from Web. Specially, String matching with mismatches problem is more difficult problem than String matching problem. We propose a new efficient algorithm to solve String matching with mismatches problem fast by utilizing fast Fourier transformation (FFT). That does not restrict the number of mismatches. That is a randomized algorithm, and its time complexity is O(knlogm), where k is the number of randomly sampled estimations and its value is in the range of 1 to |Σ|. We can compute an exact score vector with k = |Σ|. Exactly, our algorithm can be deterministic, too. We can choose a balance of time complexity and precision freely.続きを見る
|
Mendeley出力
