Fast and flexible word searching on compressed text

Citations Over TimeTop 1% of 2000 papers

Abstract

We present a fast compression technique for natural language texts. The novelties are that (1) decompression of arbitrary portions of the text can be done very efficiently, (2) exact search for words and phrases can be done on the compressed text directly, using any known sequential pattern-matching algorithm, and (3) word-based approximate and extended search can also be done efficiently without any decoding. The compression scheme uses a semistatic word-based model and a Huffman code where the coding alphabet is byte-oriented rather than bit-oriented. We compress typical English texts to about 30% of their original size, against 40% and 35% for Compress and Gzip , respectively. Compression time is close to that of Compress and approximately half of the time of Gzip , and decompression time is lower than that of Gzip and one third of that of Compress . We present three algorithms to search the compressed text. They allow a large number of variations over the basic word and phrase search capability, such as sets of characters, arbitrary regular expressions, and approximate matching. Separators and stopwords can be discarded at search time without significantly increasing the cost. When searching for simple words, the experiments show that running our algorithms on a compressed text is twice as fast as running the best existing software on the uncompressed version of the same text. When searching complex or approximate patterns, our algorithms are up to 8 times faster than the search on uncompressed text. We also discuss the impact of our technique in inverted files pointing to logical blocks and argue for the possibility of keeping the text compressed all the time, decompressing only for displaying purposes.

Related Papers

• → Optimality of Huffman Code in the Class of 1-Bit Delay Decodable Codes(2022)7 cited
• → The minimum codeword length and redundancy in the binary Huffman code for uncertain sources(1990)3 cited
• → On constructing symmetrical reversible variable-length codes independent of the Huffman code(2006)2 cited
• → Multi-symbol Accessing Huffman Decoding Method for MPEG-2 AAC(2014)2 cited
• → Optimality of Huffman Code in the Class of 1-bit Delay Decodable Codes(2022)