File LZ77Linear.h

↰ Parent directory (ADS/compression)

The parse of LZ77 with no window in O( n ) time, the algorithm of Karkkainen, Kempa and Puglisi, beyond the parse of the notes [see File LempelZiv.h], which searches the window for each phrase, in :math:` O( n w ) ` time.

Definition (ADS/compression/LZ77Linear.h)

Detailed Description

The phrases are those of lz77Parse() with an unbounded window: at the place i the longest prefix of :math:` s[ i , n ) ` that starts at an earlier place (and may overlap s[ i , n )), its length :math:` ell , the distance back to one such start, and the symbol after it; the parse moves :math: ell + 1 ` places.

Among the suffixes that start before i, the one that shares the longest prefix with the suffix i is next to it in the order of the suffixes: it is either the previous smaller value or the next smaller value of i, :math:`[ PSV( i ) = SA[ max { j < rSA[ j ] < i } ] , qquad

NSV( i ) = SA[ min { j > r : SA[ j ] < i } ] , ` r the rank of i in the suffix array SA [see File SuffixArray.h], since the longest common prefix of two suffixes is the least over the suffixes between them; so :math:` ell = max( lcp( i , PSV( i ) ) , lcp( i ,

NSV( i ) ) ) . Both are computed for all i in one scan of SA with a stack, each place pushed and popped once, and the two prefixes of a phrase are compared symbol by symbol, :math: ell + 1 ` comparisons each, which sum to O( n ) over the phrases. Hence O( n ) time with the suffix array of SA-IS, and 4n + 8n bytes besides the text; the source found is the previous or the next smaller value, not the closest one of the notes, with the same lengths.

The contracts [see File Contract.h]: :math:` n < 2^{32} ; the audit is that the phrases decode to the text [see :ref:`file_ADS_compression_LempelZiv.h]. The function is defined in LZ77Linear.tpp.

  1. Karkkainen, D. Kempa, S. J. Puglisi, Linear time Lempel-Ziv factorization: simple, fast, small, Proc. 24th CPM, LNCS 7922, 189-200, 2013, doi:10.1007/978-3-642-38905-4_19

  1. Chen, S. J. Puglisi, W. F. Smyth, Lempel-Ziv factorization using less time & space, Mathematics in Computer Science 1(4), 605-623, 2008, doi:10.1007/s11786-007-0024-4

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 13, doi:10.1017/9781009128933

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions