License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2015.582
URN: urn:nbn:de:0030-drops-49438
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/4943/
Go to the corresponding LIPIcs Volume Portal

Kosolobov, Dmitry

Lempel-Ziv Factorization May Be Harder Than Computing All Runs

pdf-format:
43.pdf (0.6 MB)

Abstract

The complexity of computing the Lempel-Ziv decomposition and the set of all runs (= maximal repetitions) is studied in the decision tree model of computation over ordered alphabet. It is known that both these problems can be solved by RAM algorithms in O(n\log\sigma) time, where n is the length of the input string and \sigma is the number of distinct letters in it. We prove an \Omega(n\log\sigma) lower bound on the number of comparisons required to construct the Lempel-Ziv decomposition and thereby conclude that a popular technique of computation of runs using the Lempel-Ziv decomposition cannot achieve an o(n\log\sigma) time bound. In contrast with this, we exhibit an O(n) decision tree algorithm finding all runs in a string. Therefore, in the decision tree model the runs problem is easier than the Lempel-Ziv decomposition. Thus we support the conjecture that there is a linear RAM algorithm finding all runs.

BibTeX - Entry

@InProceedings{kosolobov:LIPIcs:2015:4943,
  author =	{Dmitry Kosolobov},
  title =	{{Lempel-Ziv Factorization May Be Harder Than Computing All Runs}},
  booktitle =	{32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)},
  pages =	{582--593},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-78-1},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{30},
  editor =	{Ernst W. Mayr and Nicolas Ollinger},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/4943},
  URN =		{urn:nbn:de:0030-drops-49438},
  doi =		{10.4230/LIPIcs.STACS.2015.582},
  annote =	{Keywords: Lempel-Ziv factorization, runs, repetitions, decision tree, lower bounds}
}

Keywords: Lempel-Ziv factorization, runs, repetitions, decision tree, lower bounds
Collection: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Issue Date: 2015
Date of publication: 26.02.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI