Don't Care 記号つき文字列に対する近似マッチングアルゴリズム

Akutsu Tatsuya

文字列の近似マッチング・アルゴリズムとしてLandauとVishkinによるアルゴリズムが良く知られている.本稿では彼らのアルゴリズムを基に開発した,Don't Care記号付き文字列に対する逐次および並列の近似マッチング・アルゴリズムを示す.なお,nをテキスト文字列の長さ,mをパターン文字列の長さ,Σを文字集合,kを許容誤差とした場合に,逐次アルゴリズムはO(√<km>nlog|Σ|log^2m/k loglogm/k)時間で動作し,並列アルゴリズムはCRCW-PRAM上でO(√<m/k>nlog|Σ|logm/k loglogm/k)個のプロセッサを用いてO(klogm)時間で動作する.さらに,より拡張した文字列パターンに対する近似マッチング・アルゴリズムも示す.
This paper presents parallel and serial approximate matching algorithms for strings with don't care characters. They are based on the approximate string matching algorithm developed by Landau and Vishkin. The serial algorithm works in o(√<km>n log|Σ|log^2 m/k log log m/k) time and the parallel algorithm works in o(k log m) time using o(√m/k n log|Σ|log m/k log log m/k) processors on a CRCW-PRAM, where n denotes the length of a text string, m denotes the length of a pattern string, k denotes the maximum number of differences and Σ denotes the alphabet (i.e. the set of characters). Several extensions of algorithms are described, too.

Don't Care 記号つき文字列に対する近似マッチングアルゴリズム

Bibliographic Information

Search this article

Description

Journal

Citations (1)*help

Details 詳細情報について

Export

Report a problem