Substring compression problems

ABSTRACT

We initiate a new class of string matching problems called Substring Compression Problems. Given a string S that may be preprocessed, the problem is to quickly find the compressed representation or the compressed size of any query substring of S (Substring Compression Query or SCQ) or to find the length l substring of S whose compression is the least (Least Compressible Substring or LCS problem).Starting from the seminal paper of Lempel and Ziv over 25 years ago, many different methods have emerged for compressing entire strings. Determining substring compressibility is a natural variant that is combinatorially and algorithmically challenging, yet surprisingly has not been studied before. In addition, compressibility of strings is emerging as a tool to compare biological sequences and analyze their information content. However, typically, the compressibility of the entire sequence is not as informative as that of portions of the sequences. Thus substring compressibility may be a more suitable basis for sequence analysis.We present the first known, nearly optimal algorithms for substring compression problems---SCQ, LCS and their generalizations---that are exact or provably approximate. Our exact algorithms exploit the structure in strings via suffix trees and our approximate algorithms rely on new relationships we find between Lempel-Ziv compression and string parsings.

REFERENCES

• 1: 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]
• 2: S. Alstrup , G. Stolting Brodal , T. Rauhe, New data structures for orthogonal range searching, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.198, November 12-14, 2000
• 3: Amihood Amir , Martin Farach , Yossi Matias, Efficient Randomized Dictionary Matching Algorithms (Extended Abstract), Proceedings of the Third Annual Symposium on Combinatorial Pattern Matching, p.262-275, April 29-May 01, 1992
• 4: Pankaj K. Agarwal, Range searching, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 5: {BCL02} D. Benedetto, E. Caglioti, and V. Loreto. Language trees and zipping. Physical Review Letters, 88(048702), 2002.
• 6: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 7: {BW94} M. Burrows and D. J. Wheeler. A block-sorting lossless data compression algorithm. Technical Report SRC-RR-124, Hewlett Packard Laboratories, 1994.
• 8: Xin Chen , Sam Kwong , Ming Li, A compression algorithm for DNA sequences and its applications in genome comparison, Proceedings of the fourth annual international conference on Computational molecular biology, p.107, April 2000, Tokyo, Japan [doi>10.1145/332306.332352]
• 9: {CLMT02} X. Chen, M. Li, B. Ma, and J. Tromp. DNA-Compress: Fast and effective DNA sequence compression. Bioinformatics, 18(12):1696--1698, 2002.
• 10: Graham Cormode , S. Muthukrishnan, The string edit distance matching problem with moves, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.667-676, January 06-08, 2002, San Francisco, California
• 11: R Cole , U Vishkin, Deterministic coin tossing and accelerating cascades: micro and macro techniques for designing parallel algorithms, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.206-219, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12151]
• 12: {EMS03} F. Ergun, S. Muthukrishnan, and S. C. Sahinalp. Comparing sequences with segment rearrangements. In Proceedings of the 23rd Conference on Foundations of Software Technology and Theoretical Computer Science, 2003.
• 13: P. Ferragina , G. Manzini, Opportunistic data structures with applications, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.390, November 12-14, 2000
• 14: 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]
• 15: Stéphane Grumbach , Fariza Tahi, A new challenge for compression algorithms: genetic sequences, Information Processing and Management: an International Journal, v.30 n.6, p.875-886, 1994 [doi>10.1016/0306-4573(94)90014-0]
• 16: Dan Gusfield, Algorithms on strings, trees, and sequences: computer science and computational biology, Cambridge University Press, New York, NY, 1997
• 17: Roberto Grossi , Jeffrey Scott Vitter, Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract), Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.397-406, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335351]
• 18: Eamonn Keogh , Stefano Lonardi , Chotirat Ann Ratanamahatana, Towards parameter-free data mining, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014077]
• 19: Richard M. Karp , Raymond E. Miller , Arnold L. Rosenberg, Rapid identification of repeated patterns in strings, trees and arrays, Proceedings of the fourth annual ACM symposium on Theory of computing, p.125-136, May 01-03, 1972, Denver, Colorado, United States [doi>10.1145/800152.804905]
• 20: Richard M. Karp , Michael O. Rabin, Efficient randomized pattern-matching algorithms, IBM Journal of Research and Development, v.31 n.2, p.249-260, March 1987
• 21: Ming Li , Xin Chen , Xin Li , Bin Ma , Paul Vitányi, The similarity metric, Proceedings of the fourteenth annual ACM-SIAM symposium on Discrete algorithms, January 12-14, 2003, Baltimore, Maryland
• 22: S. Muthukrishnan , Süleyman Cenk Sahinalp, Approximate nearest neighbors and sequence comparison with block operations, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.416-424, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335353]
• 23: {MSIO00} T. Matsumoto, K. Sadakane, H. Imai, and T. Okazaki. Can general-purpose compression schemes really compress DNA sequences? In Currents in Computational Molecular Biology, pages 76--77, 2000.
• 24: Moni Naor, String Matching with Preprocessing of Text and Pattern, Proceedings of the 18th International Colloquium on Automata, Languages and Programming, p.739-750, July 08-12, 1991
• 25: Craig G. Nevill-Manning , Ian H. Witten, Protein Is Incompressible, Proceedings of the Conference on Data Compression, p.257, March 29-31, 1999
• 26: {RDD+97} E. Rivals, O. Delgrange, J.-P. Delahaye, M. Dauchet, M.-O. Delorme, A. Henaut, and E. Ollivier. Detection of significant patterns by compression algorithms: the case of approximate tandem repeats in DNA sequences. Comp. Appl. BioSci, 13(2):131--136, 1997.
• 27: {RDDD94} E. Rivals, O. Delgrange, M. Dauchet, and J-P. Delahaye. Compression and sequence comparison. In Proceedings of DIMACS Workshop on Sequence Comparison, 1994.
• 28: {RDDD97} E. Rivals, M. Dauchet, J. Delahaye, and O. Delgrange. Fast discerning repeats in DNA sequences with a compression algorithm. In Proc. Genome Informatics Workshop, pages 215--226, 1997.
• 29: Michael Rodeh , Vaughan R. Pratt , Shimon Even, Linear Algorithm for Data Compression via String Matching, Journal of the ACM (JACM), v.28 n.1, p.16-24, Jan. 1981 [doi>10.1145/322234.322237]
• 30: {Sah97} S. C. Sahinalp. Locally consistent parsing for string processing. PhD thesis, University of Maryland, 1997.
• 31: James A. Storer , Thomas G. Szymanski, Data compression via textual substitution, Journal of the ACM (JACM), v.29 n.4, p.928-951, Oct. 1982 [doi>10.1145/322344.322346]
• 32: {SS03} D. Shapira and J. Storer. Large edit distance with multiple block operations. In 10th International Symposium on String Processing and Information Retrieval (SPIRE), volume 2857 of Lecture Notes in Computer Science, 2003.
• 33: {SV95} S. C. Sahinalp and U. Vishkin. Data compression using locally consistent parsing. Technical report, University of Maryland Department of Computer Science, 1995.
• 34: S. C. Sahinalp , U. Vishkin, Efficient approximate and dynamic matching of patterns using a labeling paradigm, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.320, October 14-16, 1996
• 35: {SYKT01} H. Sato, T. Yoshioka, A. Konagaya, and T. Toyoda. DNA data compression in the post genome era. In Proceedings of Genome Informatics 12, pages 512--514, 2001.
• 36: {Wei73} P. Weiner. Linear pattern matching algorithm. In Proceedings of the 14th Annual IEEE Symposium on Switching and Automata Theory, pages 1--11, 1973.
• 37: {ZL77} J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, IT-23:337--343, 1977.