Copyright
when quoting this document, please refer to the following
URN: urn:nbn:de:0030-drops-7984
URL: http://drops.dagstuhl.de/opus/volltexte/2006/798/
Lifshits, Yury

Solving Classical String Problems an Compressed Texts

pdf-format:
Dokument 1.pdf (224 KB)

Abstract

How to solve string problems, if instead of input string we get only program generating it? Is it possible to solve problems faster than just "generate text + apply classical algorithm"? In this paper we consider strings generated by straight-line programs (SLP). These are programs using only assignment operator. We show new algorithms for equivalence, pattern matching, finding periods and covers, computing fingerprint table on SLP-generated strings. From the other hand, computing the Hamming distance is NP-hard. Main corollary is an $O(n2*m)$ algorithm for pattern matching in LZ-compressed texts.

BibTeX - Entry

@InProceedings{lifshits:DSP:2006:798,
  author =	{Yury Lifshits},
  title =	{Solving Classical String Problems an Compressed Texts},
  booktitle =	{Combinatorial and Algorithmic Foundations of Pattern and Association Discovery},
  year =	{2006},
  editor =	{Rudolf Ahlswede and Alberto Apostolico and Vladimir I. Levenshtein},
  number =	{06201},
  series =	{Dagstuhl Seminar Proceedings},
  ISSN =	{1862-4405},
  publisher =	{Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2006/798},
  annote =	{Keywords: Pattern matching, Compressed text}
}

Keywords: Pattern matching, Compressed text
Seminar: 06201 - Combinatorial and Algorithmic Foundations of Pattern and Association Discovery
Documenttype: InProceedings
Issue date: 2006
Date of publication: 10.11.2006

DROPS-Home | Fulltext Search | Imprint Published by LZI