Studies on fast pattern matching algorithms based on text compressions

文本压缩的目的是减少在辅助磁盘存储中存储文件的数量。因此，传统的判据是压缩比。在这个项目中，我们提出了一个新的标准来选择压缩方法。标准是在不解码的情况下在压缩文本中进行字符串模式匹配的效率。这个项目的目标是：目标1：与先解压缩再进行简单搜索相比，在压缩文本中进行更快的搜索。目标2：与在未压缩文本中进行简单搜索相比，在压缩文本中进行更快的搜索。现将这两年的主要研究成果总结如下：(1)在UNIX的COMPRESS命令中采用LZW压缩方法，开发并实现了压缩文本中的多模式匹配算法。(2)我们还设计了一种基于Shift-And方法的LZW压缩文本中单个模式的更高效算法。(3)我们通过实验证明，(1)和(2)的算法比先解压缩再进行简单搜索的算法大约快两倍。也就是说，我们已经实现了目标1。(4)我们通过实验证明了(1)和(2)的算法比在未压缩文本上进行简单搜索要快。也就是说，我们实现了目标2。(5)我们还开发了其他压缩方法的压缩模式匹配算法，如字节对编码、霍夫曼编码、有限状态编码和使用反字典的压缩，然后对它们进行评估。我们成功地完成了这个项目。

The aim of text compressions is to decrease the amount for storing files in secondary disk stor- ages. Therefore the traditional criterion is the compression ratio. In this project we propose a new criterion to select a compression method. The criterion is the efficiency of string pattern matching in compressed texts without decoding. The goals of this project are :Goal 1 : A faster search in compressed text in comparison with a decompression followed by a simple search.Goal 2 : A faster search in compressed text in comparison with a simple search in uncompressed text.Main results of this research in these two years are summarized as follows.(1) We developed and implemented a multiple pattern matching algorithm in compressed text by the LZW compression method, which is used in the COMPRESS command in UNIX.(2) We also devised a more efficient algorithm for a single pattern in LZW compressed texts, which is based on the Shift-And approach.(3) We proved by experiments that the algorithms of (1) and (2) are approximately twice faster than a decompression followed by a simple search. That is, we have achieved Goal 1.(4) We proved by experiments that the algorithms of (1) and (2) are faster than a simple search on uncompressed texts. That is, we have achieved Goal 2.(5) We also developed compressed pattern matching algorithms for other compression methods, such as, byte pair encoding, Huffman encoding, finite-state encoding, and compression using antidictionaries, and then evaluate them. We have finished this project successfully.