Studies on fast pattern matching algorithms based on text compressions

基于文本压缩的快速模式匹配算法研究

基本信息

批准号：
09680343
负责人：
TAKEDA Masayuki
金额：
$ 0.45万
依托单位：
KYUSHU UNIVERSITY
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
1997
资助国家：
日本
起止时间：
1997 至 1998
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-09680343/
关键词：
pattern matching in compressed texts speeding up pattern matching by text compression multiple pattern matching LZW compression Huffman encoding finite-state encoding byte-pair encoding パターン照合テキスト圧縮テキストデータベース情報検索データ圧縮

项目摘要

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.

文本压缩的目的是减少在辅助磁盘存储中存储文件的金额。因此，传统标准是压缩比。在此项目中，我们提出了一个新标准来选择一种压缩方法。标准是在不解码的情况下在压缩文本中匹配的字符串模式的效率。该项目的目标是：目标1：与减压后的压缩文本中更快的搜索，然后进行简单搜索。目标2：与未压缩文本中的简单搜索相比，在压缩文本中更快的搜索搜索。这两年的这项研究的结果总结如下所示。（2）我们还为LZW压缩文本中的单个模式设计了一种更有效的算法，该算法基于移位和方法。（3）我们通过实验证明了（1）和（2）的算法比对压缩的算法（2）的算法快两倍，然后进行了简单的搜索。也就是说，我们已经实现了目标1。（4）我们通过实验证明了（1）和（2）的算法比对未压缩文本的简单搜索要快。也就是说，我们已经实现了目标2。（5）我们还为其他压缩方法开发了压缩模式匹配算法，例如，字节对编码，Huffman编码，有限状态编码和使用反杂种的压缩，然后对其进行评估。我们已经成功完成了这个项目。