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

被引用文献1件

書誌事項

タイトル別名
  • APPROXIMATE STRING MATCHING WITH DON'T CARE CHARACTERS

この論文をさがす

説明

文字列の近似マッチング・アルゴリズムとして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.

収録刊行物

被引用文献 (1)*注記

もっと見る

詳細情報 詳細情報について

  • CRID
    1573950401931468032
  • NII論文ID
    110002812095
  • NII書誌ID
    AN1009593X
  • ISSN
    09196072
  • 本文言語コード
    en
  • データソース種別
    • CiNii Articles

問題の指摘

ページトップへ