Range predecessor and Lempel-Ziv parsing

DOI10.1137/1.9781611974331.CH143zbMATH Open1410.68116arXiv1507.07080OpenAlexW2241126083MaRDI QIDQ4575728FDOQ4575728

Authors: Djamal Belazzougui, Simon J. Puglisi 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Abstract: The Lempel-Ziv parsing of a string (LZ77 for short) is one of the most important and widely-used algorithmic tools in data compression and string processing. We show that the Lempel-Ziv parsing of a string of length $n$ on an alphabet of size $sigma$ can be computed in $O(nloglogsigma)$ time ($O(n)$ time if we allow randomization) using $O(nlogsigma)$ bits of working space; that is, using space proportional to that of the input string in bits. The previous fastest algorithm using $O(nlogsigma)$ space takes $O(n(logsigma+loglogn))$ time. We also consider the important rightmost variant of the problem, where the goal is to associate with each phrase of the parsing its most recent occurrence in the input string. We solve this problem in $O(n(1+(logsigma/sqrtlogn))$ time, using the same working space as above. The previous best solution for rightmost parsing uses $O(n(1+logsigma/loglogn))$ time and $O(nlogn)$ space. As a bonus, in our solution for rightmost parsing we provide a faster construction method for efficient 2D orthogonal range reporting, which is of independent interest.

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

Recommendations

• Faster lightweight Lempel-Ziv parsing
• Lempel-Ziv Compression in a Sliding Window
• Linear Time Lempel-Ziv Factorization: Simple, Fast, Small
• Lempel-Ziv factorization using less time \& space
• Lempel-Ziv-like parsing in small space

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Cited In (24)

• Developments in Language Theory
• Title not available (Why is that?)
• Redundancy of the Lempel-Ziv incremental parsing rule
• Lempel-Ziv factorization powered by space efficient suffix trees
• LZ77 computation based on the run-length encoded BWT
• On optimal parsing for LZ78-like compressors
• Lempel-Ziv-like parsing in small space
• LZRR: LZ77 parsing with right reference
• Refining the \(r\)-index
• Space-efficient fully dynamic DFS in undirected graphs
• Internal pattern matching queries in a text and applications
• Practical evaluation of Lempel-Ziv-78 and Lempel-Ziv-Welch tries
• Relations between greedy and bit-optimal LZ77 encodings
• Fully dynamic connectivity oracles under general vertex updates
• Range selection and predecessor queries in data aware space and time
• Faster lightweight Lempel-Ziv parsing
• Computing runs on a trie
• Universal compressed text indexing
• LZ-End Parsing in Linear Time
• New advances in rightmost Lempel-Ziv
• Sublinear time Lempel-Ziv (LZ77) factorization
• Space-efficient conversions from SLPs
• An upper bound and linear-space queries on the LZ-End parsing
• Dynamic index and LZ factorization in compressed space

This page was built for publication: Range predecessor and Lempel-Ziv parsing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575728)