Substring compression problems

Graham Cormode, S. Muthukrishnan

Research output: Contribution to conferencePaper


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 5 (Substring Compression Query or SCQ) or to find the length i 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.

Original languageEnglish (US)
Number of pages10
StatePublished - Jul 1 2005
Externally publishedYes
EventSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms - Vancouver, BC, United States
Duration: Jan 23 2005Jan 25 2005


OtherSixteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityVancouver, BC

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Substring compression problems'. Together they form a unique fingerprint.

  • Cite this

    Cormode, G., & Muthukrishnan, S. (2005). Substring compression problems. 321-330. Paper presented at Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, BC, United States.