Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries

DOI10.1007/978-3-319-67428-5_16zbMath1454.68046arXiv1706.03035OpenAlexW2625167461MaRDI QIDQ5150931

Johannes Fischer, Dominik Köppl

Publication date: 16 February 2021

Published in: String Processing and Information Retrieval (Search for Journal in Brave)

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

zbMATH Keywords

hashingLempel-Ziv compressiondynamic tries

Mathematics Subject Classification ID

Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Data structures (68P05)

Related Items

Fast and simple compact hashing via bucketing ⋮ c-trie++: a dynamic trie tailored for fast prefix searches ⋮ Dynamic Path-decomposed Tries ⋮ Engineering Practical Lempel-Ziv Tries

Uses Software

• LZ77

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The universality of iterated hashing over variable-length strings
• Space-efficient construction of Lempel-Ziv compressed text indexes
• An analysis of the Karp-Rabin string matching algorithm
• Universal classes of hash functions
• Constructing LZ78 tries and position heaps in linear time for large alphabets
• Linked dynamic tries with applications to LZ-compression in sublinear time and space
• Alphabet-Dependent String Searching with Wexponential Search Trees
• Lempel Ziv Computation in Small Space (LZ-CISS)
• Compact Hash Tables Using Bidirectional Linear Probing
• Efficient randomized pattern-matching algorithms
• A universal algorithm for sequential data compression
• Compression of individual sequences via variable-rate coding
• Range Predecessor and Lempel-Ziv Parsing
• Space-Efficient Construction of Compressed Indexes in Deterministic Linear Time
• Efficient LZ78 Factorization of Grammar Compressed Text
• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
• Dynamic Space Efficient Hashing.
• Compact Dynamic Rewritable (CDRW) Arrays
• Lazy Lempel-Ziv Factorization Algorithms
• Implementing the LZ-index
• Mersenne and Fermat Numbers

This page was built for publication: Practical Evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch Tries