ML p(r)ior | Lempel-Ziv Decoding in External Memory

Lempel-Ziv Decoding in External Memory

2016-01-31
Simple and fast decoding is one of the main advantages of LZ77-type text encoding used in many popular file compressors such as gzip and 7zip. With the recent introduction of external memory algorithms for Lempel-Ziv factorization there is a need for external memory LZ77 decoding but the standard algorithm makes random accesses to the text and cannot be trivially modified for external memory computation. We describe the first external memory algorithms for LZ77 decoding, prove that their I/O complexity is optimal, and demonstrate that they are very fast in practice, only about three times slower than in-memory decoding (when reading input and writing output is included in the time).
PDF

Highlights - Most important sentences from the article

Login to like/save this paper, take notes and configure your recommendations

Related Articles

2017-10-30
1710.10964 | cs.DS

A well-known fact in the field of lossless text compression is that high-order entropy is a weak mod… show more
PDF

Highlights - Most important sentences from the article

2019-05-13
1905.04897 | cs.DS

Problems involving the efficient arrangement of simple objects, as captured by bin packing and makes… show more
PDF

Highlights - Most important sentences from the article

2018-12-11
1812.04261 | cs.DS

Lossless data compression has been widely studied in computer science. One of the most widely used l… show more
PDF

Highlights - Most important sentences from the article

2016-06-18

Order-preserving pattern matching was introduced recently but it has already attracted much attentio… show more
PDF

Highlights - Most important sentences from the article

2016-07-19

We present a new streaming algorithm for the $k$-Mismatch problem, one of the most basic problems in… show more
PDF

Highlights - Most important sentences from the article

2018-08-02
1808.00963 | cs.DS

This dissertation focuses on two fundamental sorting problems: string sorting and suffix sorting. Th… show more
PDF

Highlights - Most important sentences from the article

2018-03-29

High-throughput sequencing technologies have led to explosive growth of genomic databases; one of wh… show more
PDF

Highlights - Most important sentences from the article

2019-03-05

Lempel-Ziv (LZ77 or, briefly, LZ) is one of the most effective and widely-used compressors for repet… show more
PDF

Highlights - Most important sentences from the article

2018-07-30
1807.11328 | cs.DS

A new algorithm, Guidesort, for sorting in the uniprocessor variant of the parallel disk model (PDM)… show more
PDF

Highlights - Most important sentences from the article

2018-07-10

While FPGAs have been used extensively as hardware accelerators in industrial computation, no theore… show more
PDF

Highlights - Most important sentences from the article

2016-06-15

The pattern matching problem with swaps is to find all occurrences of a pattern in a text while allo… show more
PDF

Highlights - Most important sentences from the article

2018-11-04

Sorting extremely large datasets is a frequently occuring task in practice. These datasets are usual… show more
PDF

Highlights - Most important sentences from the article

2019-01-16
1901.05226 | cs.DS

We show that the Longest Common Prefix Array of a text collection of total size n on alphabet [1, {\… show more
PDF

Highlights - Most important sentences from the article

2017-06-15

The {\em compressed stack} is a data structure designed by Barba {\em et al.} (Algorithmica 2015) th… show more
PDF

Highlights - Most important sentences from the article

2018-04-24
1804.08978 | cs.CC

A noticeable fraction of Algorithms papers in the last few decades improve the running time of well-… show more
PDF

Highlights - Most important sentences from the article

2014-04-18

In this paper, we develop semi-external and external memory algorithms for graph partitioning and cl… show more
PDF

Highlights - Most important sentences from the article