Fast and flexible word searching on compressed text

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.

REFERENCES

• 1: Alfred V. Aho , Margaret J. Corasick, Efficient string matching: an aid to bibliographic search, Communications of the ACM, v.18 n.6, p.333-340, June 1975 [doi>10.1145/360825.360855]
• 2: AMIR, A. AND BENSON, G. 1992. Efficient two-dimensional compressed matching. In Proceedings of the on 1992 IEEE Data Compression Conference (Mar.), J. Storer and M. Cohn, Eds. IEEE Computer Society Press, Los Alamitos, CA, 279-288.
• 3: Amihood Amir , Gary Benson , Martin Farach, Let sleeping files lie: pattern matching in Z-compressed files, Journal of Computer and System Sciences, v.52 n.2, p.299-307, April 1996 [doi>10.1006/jcss.1996.0023]
• 4: ARA JO, M. D., NAVARRO, G., AND ZIVIANI, N. 1997. Large text searching allowing errors. In Proceedings of the 4th South American Workshop on String Processing, R. Baeza-Yates, Ed. Carleton University Press International Informatics Series, vol. 8. Carleton University Press, Ottawa, Canada, 2-20.
• 5: Ricardo Baeza-Yates , Gaston H. Gonnet, A new approach to text searching, Communications of the ACM, v.35 n.10, p.74-82, Oct. 1992 [doi>10.1145/135239.135243]
• 6: Ricardo Baeza-Yates , Gonzalo Navarro, Block addressing indices for approximate text retrieval, Proceedings of the sixth international conference on Information and knowledge management, p.1-8, November 10-14, 1997, Las Vegas, Nevada, United States [doi>10.1145/266714.266719]
• 7: BAEZA-YATES, R. AND NAVARRO, G. 1999. Faster approximate string matching. Algorithmica 23, 2, 127-158.
• 8: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 9: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 10: Timothy C. Bell , Alistair Moffat , Craig G. Nevill-Manning , Ian H. Witten , Justin Zobel, Data compression in full-text retrieval systems, Journal of the American Society for Information Science, v.44 n.9, p.508-531, Oct. 1993 [doi>10.1002/(SICI)1097-4571(199310)44:9<508::AID-ASI2>3.0.CO;2-A]
• 11: Jon Louis Bentley , Daniel D. Sleator , Robert E. Tarjan , Victor K. Wei, A locally adaptive data compression scheme, Communications of the ACM, v.29 n.4, p.320-330, April 1986 [doi>10.1145/5684.5688]
• 12: Martin Farach , Mikkel Thorup, String matching in Lempel-Ziv compressed strings, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.703-712, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225288]
• 13: G. H. Gonnet , R. Baeza-Yates, Handbook of algorithms and data structures: in Pascal and C (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1991
• 14: HARMAN, D. 1995. Overview of the third Text Retrieval Conference (TREC-3). In Proceedings of the 3rd Text Retrieval Conference (TREC-3), D. Harman, Ed. National Institute of Standards and Technology, Gaithersburg, MD.
• 15: H. S. Heaps, Information Retrieval: Computational and Theoretical Aspects, Academic Press, Inc., Orlando, FL, 1978
• 16: Daniel S. Hirschberg , Debra A. Lelewer, Efficient decoding of prefix codes, Communications of the ACM, v.33 n.4, p.449-459, April 1990 [doi>10.1145/77556.77566]
• 17: HORSPOOL, R. N. AND CORMACK, G.V. 1992. Constructing word-based text compression algorithms. In Proceedings of the on 1992 IEEE Data Compression Conference (Mar.), J. Storer and M. Cohn, Eds. IEEE Computer Society Press, Los Alamitos, CA, 62-71.
• 18: HUFFMAN, D.A. 1952. A method for the construction of minimum-redundancy codes. Proc. Inst. Radio Eng. 40, 9 (Sept.), 1098-1101.
• 19: Takuya Kida , Yusuke Shibata , Masayuki Takeda , Ayumi Shinohara , Setsuo Arikawa, A Unifying Framework for Compressed Pattern Matching, Proceedings of the String Processing and Information Retrieval Symposium & International Workshop on Groupware, p.89, September 21-24, 1999
• 20: T. Kida , M. Takeda , A. Shinohara , M. Miyazaki , S. Arikawa, Multiple Pattern Matching in LZW Compressed Text, Proceedings of the Conference on Data Compression, p.103, March 30-April 01, 1998
• 21: Takuya Kida , Masayuki Takeda , Ayumi Shinohara , Setsuo Arikawa, Shift-And Approach to Pattern Matching in LZW Compressed Text, Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching, p.1-13, July 22-24, 1999
• 22: Udi Manber, A text compression scheme that allows fast searching directly in the compressed file, ACM Transactions on Information Systems (TOIS), v.15 n.2, p.124-136, April 1997 [doi>10.1145/248625.248639]
• 23: MANBER, U. AND WU, S. 1993. Glimpse: A tool to search through entire file systems. Tech. Rep. 93-34. Department of Computer Science, University of Arizona, Tucson, AZ.
• 24: MILIDIU, R., PESSOA, A., AND LABER, E. 1998. In-place, simple, and fast length-restricted prefix coding. In Proceedings of 5th International Symposium on String Processing and Information Retrieval (SPIRE'98, Sept. 1998), IEEE Computer Society, Washington, DC, 50-59.
• 25: A. Moffat, Word-based text compression, Software—Practice & Experience, v.19 n.2, p.185-198, February 1989 [doi>10.1002/spe.4380190207]
• 26: Alistair Moffat , Jyrki Katajainen, In-Place Calculation of Minimum-Redundancy Codes, Proceedings of the 4th International Workshop on Algorithms and Data Structures, p.393-402, August 16-18, 1995
• 27: MOURA, E. S. 1999. Aplica# es de Compress o de Dados a Sistemas de Recupera# o de Informa# o. Ph.D. Dissertation. Department of Computer Science, Universidad Federal de Minas Gerais, Brazil.
• 28: MOURA, E. S., NAVARRO, G., AND ZIVIANI, N. 1997. Indexing compressed text. In Proceedings of the 4th South American Workshop on String Processing, R. Baeza-Yates, Ed. Carleton University Press International Informatics Series, vol. 8. Carleton University Press, Ottawa, Canada, 95-111.
• 29: Edleno Silva de Moura , Gonzalo Navarro , Nivio Ziviani , Ricardo Baeza-Yates, Fast searching on compressed text allowing errors, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.298-306, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291013]
• 30: MOURA, E. S., NAVARRO, G., ZIVIANI, N., AND BAEZA-YATES, R. 1998b. Direct pattern matching on compressed text. In Proceedings of 5th International Symposium on String Processing and Information Retrieval (SPIRE'98, Sept. 1998), IEEE Computer Society, Washington, DC, 90-95.
• 31: Gonzalo Navarro , Mathieu Raffinot, A General Practical Approach to Pattern Matching over Ziv-Lempel Compressed Text, Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching, p.14-36, July 22-24, 1999
• 32: Gonzalo Navarro , Edleno Silva De Moura , Marden Neubert , Nivio Ziviani , Ricardo Baeza-Yates, Adding Compression to Block Addressing Inverted Indexes, Information Retrieval, v.3 n.1, p.49-77, July 2000 [doi>10.1023/A:1009934302807]
• 33: Eugene S. Schwartz , Bruce Kallick, Generating a canonical prefix encoding, Communications of the ACM, v.7 n.3, p.166-169, March 1964 [doi>10.1145/363958.363991]
• 34: Daniel M. Sunday, A very fast substring search algorithm, Communications of the ACM, v.33 n.8, p.132-142, Aug. 1990 [doi>10.1145/79173.79184]
• 35: TURPIN, A. AND MOFFAT, A. 1997. Fast file search using text compression. In Proceedings of the 20th Conference on Australian Computer Science, 1-8.
• 36: WITTEN, I., MOFFAT, A., AND BELL, T. 1999. Managing Gigabytes. 2nd Morgan Kaufmann Publishers Inc., San Francisco, CA.
• 37: Sun Wu , Udi Manber, Fast text searching: allowing errors, Communications of the ACM, v.35 n.10, p.83-91, Oct. 1992 [doi>10.1145/135239.135244]
• 38: ZmF, G. K. 1949. Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology. Addison-Wesley, Reading, MA.
• 39: ZIv, J. AND LEMPEL, A. 1976. On the complexity of finite sequences. IEEE Trans. Inf. Theor. 22, 1, 75-81.
• 40: ZIv, g. AND LEMPEL, A. 1977. A universal algorithm for sequential data compression. IEEE Trans. Inf. Theor. IT-23, 3 (May), 337-343.
• 41: ZIv, J. AND LEMPEL, A. 1978. Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theor. IT-24, 5 (Sept.), 530-536.
• 42: Justin Zobel , Alistair Moffat, Adding compression to a full-text retrieval system, Software—Practice & Experience, v.25 n.8, p.891-903, Aug. 1995 [doi>10.1002/spe.4380250804]

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Design

Keywords:
compressed pattern matching, natural language text compression, word searching, word-based Huffman coding