著者

阿久津 達也

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.1993, no.88, pp.27-34, 1993-10-01

被引用文献数

1

---

文字列の近似マッチング・アルゴリズムとしてLandauとVishkinによるアルゴリズムが良く知られている。本稿では彼らのアルゴリズムを基に開発した、Don't Care記号付き文字列に対する逐次および並列の近似マッチング・アルゴリズムを示す。なお、nをテキスト文字列の長さ、mをパターン文字列の長さ、Σを文字集合、kを許容誤差とした場合に、逐次アルゴリズムはO(√<km> n log|Σ|log^2 m/k log log m/) 時間で動作し、並列アルゴリズムはCRCW?PRAM上でO(√<m/k> n log|Σ|log m/k log log m/)個のプロセッサを用いてO( log )時間で動作する。さらに、より拡張した文字列パターンに対する近似マッチング・アルゴリズムも示す。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.