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

• Item type: SIG Technical Reports(1)
• 公開日: 1993-10-01
• タイトル: Don't Care記号つき文字列に対する近似マッチング・アルゴリズム
• タイトル / 言語: en
• タイトル: APPROXIMATE STRING MATCHING WITH DON'T CARE CHARACTERS
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 機械技術研究所
• 著者所属(英): en
• 著者所属(英): Mechanical Engineering Laboratory
• 著者名: 阿久津, 達也
• 著者名(英): Tatsuya, Akutsu
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 文字列の近似マッチング・アルゴリズムとして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 ）時間で動作する。さらに、より拡張した文字列パターンに対する近似マッチング・アルゴリズムも示す。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1993, 号 88(1993-AL-035), p. 27-34, 発行日 1993-10-01
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会