Constructing LZ78 tries and position heaps in linear time for large alphabets

DOI10.1016/j.ipl.2015.04.002zbMath1329.68087arXiv1501.06619OpenAlexW2087800203MaRDI QIDQ2346553

Shunsuke Inenaga, Hideo Bannai, Masayuki Takeda, Yuto Nakashima, Tomohiro I.

Publication date: 2 June 2015

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1501.06619

zbMATH Keywords

algorithmsdata structuressuffix treesLempel-Ziv 78 factorizationnearest marked ancestor queriesposition heaps

Mathematics Subject Classification ID

Data structures (68P05)

Related Items (5)

Factorizing strings into repetitions ⋮ Lempel Ziv Computation in Small Space (LZ-CISS) ⋮ Engineering Practical Lempel-Ziv Tries ⋮ Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries ⋮ Lempel-Ziv factorization powered by space efficient suffix trees

Cites Work

• Position heaps: a simple and dynamic text indexing data structure
• The level ancestor problem simplified
• The suffix tree of a tree and minimizing sequential transducers
• Finding level-ancestors in trees
• Improved dynamic dictionary matching
• Linked dynamic tries with applications to LZ-compression in sublinear time and space
• Compressing and indexing labeled trees, with applications
• Compression of individual sequences via variable-rate coding
• A Subquadratic Sequence Alignment Algorithm for Unrestricted Scoring Matrices
• Efficient LZ78 Factorization of Grammar Compressed Text
• New Algorithms for Position Heaps
• Fast incremental planarity testing

This page was built for publication: Constructing LZ78 tries and position heaps in linear time for large alphabets