Compressed dynamic tries with applications to LZ-compression in sublinear time and space

Jesper Andreas Jansson, Kunihiko Sadakane, Wing Kin Sung

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

3 Citations (Scopus)

Abstract

The dynamic trie is a fundamental data structure which finds applications in many areas. This paper proposes a compressed version of the dynamic trie data structure. Our data-structure is not only space efficient, it also allows pattern searching in o(|P|) time and leaf insertion/deletion in o(log n) time, where |P| is the length of the pattern and n is the size of the trie. To demonstrate the usefulness of the new data structure, we apply it to the LZ-compression problem. For a string S of length s over an alphabet A of size σ, the previously best known algorithms for computing the Ziv-Lempel encoding (LZ78) of S either run in: (1) O(s) time and O(s log s) bits working space; or (2) O(sσ) time and O(sHk+ s log σ/ logσs) bits working space, where Hkis the k-order entropy of the text. No previous algorithm runs in sublinear time. Our new data structure implies a LZ-compression algorithm which runs in sublinear time and uses optimal working space. More precisely, the LZ-compression algorithm uses O(s(log σ + log logσs)logσs) bits working space and runs in O(s(log log s)2/(logσs log log log s)) worst-case time, which is sublinear when σ = 2o(log slog log log s/(log log s)2)).
Original languageEnglish
Title of host publicationFSTTCS 2007
Subtitle of host publicationFoundations of Software Technology and Theoretical Computer Science - 27th International Conference, Proceedings
Pages424-435
Number of pages12
Publication statusPublished - 1 Dec 2007
Externally publishedYes
Event27th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2007 - New Delhi, India
Duration: 12 Dec 200714 Dec 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4855 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference27th International Conference on the Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2007
Country/TerritoryIndia
CityNew Delhi
Period12/12/0714/12/07

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this