Access Restriction

Author Krkkinen, Juha ♦ Kempa, Dominik ♦ Puglisi, Simon J.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Burrows-Wheeler transform ♦ LZ77 ♦ Lempel-Ziv factorization ♦ Lempel-Ziv parsing ♦ Data compression ♦ String processing ♦ Suffix array
Abstract For decades the Lempel-Ziv (LZ77) factorization has been a cornerstone of data compression and string processing algorithms, and uses for it are still being uncovered. For example, LZ77 is central to several recent text indexing data structures designed to search highly repetitive collections. However, in many applications computation of the factorization remains a bottleneck in practice. In this article, we describe a number of simple and fast LZ77 factorization algorithms, which consistently outperform all previous methods in practice, use less memory, and still offer strong worst-case performance guarantees. A common feature of the new algorithms is that they compute longest common prefix information in a lazy fashion, with the degree of laziness in preprocessing characterizing different algorithms.
Description Author Affiliation: Helsinki Institute of Information Technology, Department of Computer Science, University of Helsinki, Finland (Krkkinen, Juha; Kempa, Dominik; Puglisi, Simon J.)
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-10-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 21
Page Count 19
Starting Page 1
Ending Page 19

Open content in new tab

   Open content in new tab
Source: ACM Digital Library