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：压缩文本中的搜索速度比未压缩文本中的简单搜索快。(1)本文提出并实现了一种基于LZW压缩方法的压缩文本多模式匹配算法。(2)我们还设计了一个更有效的算法，为一个单一的模式在LZW压缩文本，这是基于Shift-And方法。(3)我们通过实验证明，（1）和（2）的算法大约比解压缩后进行简单搜索快两倍。也就是说，我们已经实现了目标1。(4)我们通过实验证明，（1）和（2）的算法比对未压缩文本的简单搜索更快。也就是说，我们实现了目标2。(5)我们还开发了压缩模式匹配算法的其他压缩方法，如字节对编码，霍夫曼编码，有限状态编码，并使用反字典压缩，然后评估他们。我们成功地完成了这个项目。

项目成果

Kida,T.et al.: "Shift-And approach to pattern matching in LZW compressed text" Technical Report DOI-TR-156,Kyushu University. 1-13 (1999)

Kida,T.et al.：“LZW 压缩文本中模式匹配的 Shift-And 方法”技术报告 DOI-TR-156，九州大学。

Kida,T.et al.: "Multiple Pattern Matching in LZW Compressed Text" Proc.Data Compression Conference,DCC'98. 103-112 (1998)

Kida,T.et al.：“LZW 压缩文本中的多重模式匹配”Proc.Data Compression Conference，DCC98。

T.Kida et al.: "Multiple Pattern Matching in LZW Compressed Text" Proc.Data Compression Conference,DCC'98. (to appear). (1998)

T.Kida 等人：“LZW 压缩文本中的多重模式匹配”Proc.Data Compression Conference，DCC98。

Takeda,M.: "Pattern matching machine for text compressed using finite state model" Technical Report DOI-TR-142,Kyushu University. 1-12 (1997)

Takeda,M.：“使用有限状态模型压缩文本的模式匹配机”技术报告 DOI-TR-142，九州大学。

Shibata, Y.et al.: "Pattern matching in text compressed by using antidictionaries" Technical Report DOI-TR-157, Kyushu University. 1-12 (1999)

Shibata, Y.et al.：“使用反词典压缩的文本中的模式匹配”技术报告 DOI-TR-157，九州大学。