Efficiently decodable and searchable natural language adaptive compression

ABSTRACT

We address the problem of adaptive compression of natural language text, focusing on the case where low bandwidth is available and the receiver has little processing power, as in mobile applications. Our technique achieves compression ratios around 32% and requires very little effort from the receiver. This tradeoff, not previously achieved with alternative techniques, is obtained by breaking the usual symmetry between sender and receiver dominant in statistical adaptive compression. Moreover, we show that our technique can be adapted to avoid decompression at all in cases where the receiver only wants to detect the presence of some keywords in the document. This is useful in scenarios such as selective dissemination of information, news clipping, alert systems, text categorization, and clustering. Thanks to the asymmetry we introduce, the receiver can search the compressed text much faster than the plain text. This was previously achieved only in semistatic compression scenarios.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 2: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 3: Robert S. Boyer , J. Strother Moore, A fast string searching algorithm, Communications of the ACM, v.20 n.10, p.762-772, Oct. 1977 [doi>10.1145/359842.359859]
• 4: N. Brisaboa, A. Fariña, G. Navarro, and M. Esteller. (s,c)-dense coding: An optimized compression code for natural language text databases. Proc. 10th SPIRE, LNCS 2857, pp. 122--136, 2003.
• 5: N. Brisaboa, A. Fariña, G. Navarro, and J. Paramá Simple, fast, and efficient natural language adaptive compression. Proc. 11th SPIRE, LNCS 3246, pp. 230--241, 2004.
• 6: N. Brisaboa, E. Iglesias, G. Navarro, and J. Paramá An efficient compression code for text databases. Proc 25th ECIR, LNCS 2633, pp. 468--481, 2003.
• 7: M. Burrows and D. Wheeler. A block-sorting lossless data compression algorithm. TR 124, DEC, 1994.
• 8: J. Carpinelli, A. Moffat, R. Neal, W. Salamonsen, L. Stuiver, A. Turpin, and I. Witten. Word, character, integer, and bit based compression using arithmetic coding. www.cs.mu.oz.au/~alistair/arith_coder, 1999.
• 9: 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]
• 10: Edleno Silva de Moura , Gonzalo Navarro , Nivio Ziviani , Ricardo Baeza-Yates, Fast and flexible word searching on compressed text, ACM Transactions on Information Systems (TOIS), v.18 n.2, p.113-139, April 2000 [doi>10.1145/348751.348754]
• 11: A. Fariña. New Compression Codes for Text Databases. PhD thesis, Univ. A Coruñ a, Comp. Sci. Dept., A Coruñ a, Spain, 2005. To appear.
• 12: H. S. Heaps, Information Retrieval: Computational and Theoretical Aspects, Academic Press, Inc., Orlando, FL, 1978
• 13: R. N. Horspool. Practical fast searching in strings. Soft. Pract. Exp., 10(6):501--506, 1980.
• 14: D. A. Huffman. A method for the construction of minimum-redundancy codes. Proc. Inst. Radio Eng., 40(9):1098--1101, 1952.
• 15: A. Moffat, Word-based text compression, Software—Practice & Experience, v.19 n.2, p.185-198, February 1989 [doi>10.1002/spe.4380190207]
• 16: Alistair Moffat , Andrew Turpin, Compression and Coding Algorithms, Kluwer Academic Publishers, Norwell, MA, 2002
• 17: 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 ]
• 18: Gonzalo Navarro , Mathieu Raffinot, Flexible pattern matching in strings: practical on-line search algorithms for texts and biological sequences, Cambridge University Press, New York, NY, 2002
• 19: Gonzalo Navarro , Jorma Tarhio, Boyer-Moore String Matching over Ziv-Lempel Compressed Text, Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching, p.166-180, June 21-23, 2000
• 20: A. Turpin and A. Moffat. Fast file search using text compression. Proc. 20th Australian Comp. Sci. Conf., pp. 1--8, 1997.
• 21: Ian H. Witten , Alistair Moffat , Timothy C. Bell, Managing gigabytes (2nd ed.): compressing and indexing documents and images, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1999
• 22: G. K. Zipf. Human Behavior and the Principle of Least Effort. Addison-Wesley, 1949.
• 23: J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE TIT, 23(3):337--343, 1977.
• 24: J. Ziv and A. Lempel. Compression of individual sequences via variable-rate coding. IEEE TIT, 24(5):530--536, 1978.
• 25: Nivio Ziviani , Edleno Silva de Moura , Gonzalo Navarro , Ricardo Baeza-Yates, Compression: A Key for Next-Generation Text Retrieval Systems, Computer, v.33 n.11, p.37-44, November 2000 [doi>10.1109/2.881693 ]

INDEX TERMS

Primary Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY

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

General Terms:
Algorithms

Keywords:
adaptive natural language text compression, searching compressed text