Linked Dynamic Tries with Applications to LZ-Compression in Sublinear Time and Space

Jesper Andreas Jansson, Kunihiko Sadakane, Wing Kin Sung

Research output: Journal article publicationJournal articleAcademic researchpeer-review

16 Citations (Scopus)

Abstract

The dynamic trie is a fundamental data structure with applications in many areas of computer science. This paper proposes a new technique for maintaining a dynamic trie T of size at most 2wnodes under the unit-cost RAM model with a fixed word size w. It is based on the idea of partitioning T into a set of linked small tries, each of which can be maintained efficiently. Our method is not only space-efficient, but also allows the longest common prefix between any query pattern P and the strings currently stored in T to be computed in o(|P|) time for small alphabets, and allows any leaf to be inserted into or deleted from T in o(log|T|) time. To demonstrate the usefulness of our new data structure, we apply it to LZ-compression. Significantly, we obtain the first algorithm for generating the lz78 encoding of a given string of length n over an alphabet of size σ in sublinear (o(n)) time and sublinear (o(nlogσ) bits) working space for small alphabets (Formula presented.). Moreover, the working space for our new algorithm is asymptotically less than or equal to the space for storing the output compressed text, regardless of the alphabet size.
Original languageEnglish
Pages (from-to)969-988
Number of pages20
JournalAlgorithmica
Volume71
Issue number4
DOIs
Publication statusPublished - 1 Jan 2015
Externally publishedYes

Keywords

  • Data structures
  • Dynamic trie
  • Longest common prefix query
  • LZ-compression

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Cite this