<テクニカルレポート>
Pattern Matching Machine for Text Compressed Using Finite State Model

作成者
本文言語
出版者
発行日
雑誌名
出版タイプ
アクセス権
概要 The classical pattern matching problem is to find all occurrences of patterns in a text. In many practical cases, since the text is very large and stored in the secondary storage, most of the time for... the pattern matching is dominated by data transmission of the text. Therefore the text compression can speed-up the pattern matching. In this framework it is required to develop an efficient pattern matching algorithm for searching the compressed text directly without decoding. In 1992, Fukamachi et al. proposed a method of constructing pattern matching machine that runs on Huffman coded text, based on the Aho-Coracick algorithm. However, since the Huffman code is optimal only under the assumption of the memoryless source model, the compression ratio is not very high. On the other hand, it is known that English text can be highly compressed by the compression method based on the Markov model. In this paper, we focus our attention on the finite-state model, which subsumes the Markov model as an important special case, and show an algorithm for constructing pattern matching machine for text compressed under the assumption of this model. We also give a proof of the correctness of the algorithm.続きを見る

本文情報を非表示

trcs142.ps gz 138 KB 75  
trcs142 pdf 217 KB 27  

詳細

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