<テクニカルレポート>
Shift-And Approach to Pattern Matching in LZW Compressed Text

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 This paper considers the Shift-And approach to the problem of pattern matching in LZW compressed text, and gives a new algorithm that solves it. The algorithm is indeed fast when the pattern length is... at most 32, or the word length. After an $ O(m+ mid Sigma mid) $ time and $ O(mid Sigma mid) $ space preprocessing of a pattern, it scans an LZW compressed text in $ O(n + r) $ time and reports all occurrences of the pattern, where $ n $ is the compressed text length, $ m $ is the pattern length, and r is the number of the pattern occurrences. Experimental results show that it runs approximately 1.5 times faster than a decompression followed by a simple search using the Shift-And algorithm. Moreover, the algorithm can be extended to the generalized pattern matching, to the pattern matching with $ k $ mismatches, and to the multiple pattern matching, like the Shift-And algorithm.続きを見る

本文情報を非表示

trcs156.ps gz 189 KB 66  
trcs156 pdf 137 KB 32  

詳細

レコードID
査読有無
関連情報
タイプ
登録日 2009.04.22
更新日 2018.08.31