Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Yamamoto, Jun'ichi; I, Tomohiro; Bannai, Hideo; Inenaga, Shunsuke; Takeda, Masayuki http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-44976
URL:

; ; ; ;

Faster Compact On-Line Lempel-Ziv Factorization

pdf-format:


Abstract

We present a new on-line algorithm for computing the Lempel-Ziv factorization of a string that runs in O(N.log(N)) time and uses only O(N.log(s)) bits of working space, where N is the length of the string and s is the size of the alphabet. This is a notable improvement compared to the performance of previous on-line algorithms using the same order of working space but running in either O(N.log^3(N)) time [Okanohara and Sadakane, 2009] or O(N.log^2(N)) time [Starikovskaya, 2012]. The key to our new algorithm is in the utilization of an elegant but less popular index structure called Directed Acyclic Word Graphs, or DAWGs [Blumer et al., 1985]. We also present an opportunistic variant of our algorithm, which, given the run length encoding of size m of a string of length N, computes the Lempel-Ziv factorization of the string on-line, in O(m.min{log(log(m)).log(log(N))/(log(log(log(N)))), (log(m))^{1/2}/(log(log(m)))^{1/2})}) time and O(m.log(N)) bits of space.

BibTeX - Entry

@InProceedings{yamamoto_et_al:LIPIcs:2014:4497,
  author =	{Jun'ichi Yamamoto and Tomohiro I and Hideo Bannai and Shunsuke Inenaga and Masayuki Takeda},
  title =	{{Faster Compact On-Line Lempel-Ziv Factorization}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{675--686},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4497},
  URN =		{urn:nbn:de:0030-drops-44976},
  doi =		{10.4230/LIPIcs.STACS.2014.675},
  annote =	{Keywords: Lempel-Ziv Factorization, String Index}
}

Keywords: Lempel-Ziv Factorization, String Index
Seminar: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue date: 2014
Date of publication: 2014


DROPS-Home | Fulltext Search | Imprint Published by LZI