Let sleeping files lie: pattern matching in Z-compressed files
Let sleeping files lie: pattern matching in Z-compressed files
复制标题
让休眠文件躺下：Z 压缩文件中的模式匹配
DOI：
10.1006/jcss.1996.0023
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
Martín Farach
中科院分区：
文献类型：
--
作者：
A. Amir;Gary Benson;Martín Farach
当前存储信息的爆炸需要一种新的模式匹配模型，即压缩匹配模型。在该模型中，试图在与压缩文本大小成比例的时间内找到压缩文本中模式的所有出现，即，而不压缩文本。最有效的通用压缩算法是自适应的，因为每个压缩符号所表示的文本是由数据动态确定的。因此，子字符串的编码取决于它的位置。因此，相同的子串每次出现在压缩文本中时可能“看起来不同”。在本文中，我们考虑模式匹配不解压UNIX Z压缩。这是Lempel Ziv自适应压缩方案的变体。如果n是压缩文本的长度，m是模式的长度，我们的算法在时间O（n+m）或O（nlog m+m）内找到第一个模式出现。我们还介绍了一个新的标准来衡量压缩匹配算法，额外的空间。我们将展示如何修改我们的算法，以实现额外的空间使用量和算法的时间复杂度之间的权衡。] 1996年学术出版社，公司。
The current explosion of stored information necessitates a new model of pattern matching, that of compressed matching. In this model one tries to find all occurrences of a pattern in a compressed text in time proportional to the compressed text size, i.e., without decompressing the text. The most effective general purpose compression algorithms are adaptive, in that the text represented by each compression symbol is determined dynamically by the data. As a result, the encoding of a substring depends on its location. Thus the same substring may ``look different'' every time it appears in the compressed text. In this paper we consider pattern matching without decompression in the UNIX Z-compression. This is a variant of the Lempel Ziv adaptive compression scheme. If n is the length of the compressed text and m is the length of the pattern, our algorithms find the first pattern occurrence in time O(n+m) or O(n log m+m). We also introduce a new criterion to measure compressed matching algorithms, that of extra space. We show how to modify our algorithms to achieve a trade-off between the amount of extra space used and the algorithm's time complexity. ] 1996 Academic Press, Inc.