Local Editing in LZ-End Compressed Data

LZ-End builds on the LZ77 algorithm [16], such that LZ-End allows decompression of an arbitrary portion of compressed data without decompressing any other part of the compressed data. This section gives a rough overview of LZ-End, as presented in [3].

The compressed output of the LZ-End algorithm is a series of phrases, each represented conceptually as a tuple $\langle q,l,s\rangle$:

• •

  $q$: a pointer to the previous phrase which the current phrase builds upon.

• •

  $l$: the number of symbols encoded by the current phrase.

• •

  $s$: the final symbol of the current phrase.

Each phrase encodes either:

• •

  a single symbol. In this case, $q$ is null and $s$ is the symbol encoded.

• •

  a series of symbols. $q$ points to the last phrase which the current phrase extends. By making $l-1$ greater than the length of the phrase at index $q$, this pointer may reference multiple adjacent phrases, and the remaining symbols of the current phrase are derived from phrases $q-1$, $q-2$, etc. As in LZ77, $s$ extends this sequence of symbols from the previous phrases [3].

Unlike LZ77, LZ-End parsing does not use a sliding window [3], but parses by reading the whole string into memory and constructing a suffix array of the data [3]. Three arrays store the compressed data. To compress a string ${\bf T}$ of $n$ symbols ${\bf T}=T_{1}T_{2}\dots T_{n}$ into $n^{\prime}$ phrases:

• •

  char[$n^{\prime}$] stores $s$ in the tuple above for each phrase,

• •

  source[$n^{\prime}$] stores $q$ in the tuple for each phrase, and

• •

  $\mathbf{B}[n]$, where $\mathbf{B}[i]=1$ if $T_{i}$ is at the end of a phrase, 0 otherwise. This array is sparse and stored as a list of indices to the non-zero elements (see [17]). This supports two constant-time operations:

  • –

    $\mathit{rank}_{B}(p)$: The number of 1’s in $\mathbf{B}$ at indices up to $p$, i.e., the number of phrases preceding $T_{p}$.

  • –

    $\mathit{select}_{B}(p)$: The position of the $p$-th 1 in $\mathbf{B}$, i.e., the index of the last symbol in $\mathbf{T}$ encoded by the $p$-th phrase.

  Collectively, $\mathit{rank}_{B}()$ and $\mathit{select}_{B}()$ yield the length $l$ of each phrase.

When a phrase $y$ points back to a phrase $x$, we say that $y$ depends on $x$, and we call $y$ a dependent of $x$. Note that $y$ may depend on any number of symbols from $x$ and its immediate predecessors. A phrase may have any number of dependents, including none. Let $[a,b]$ denote the range of integers between $a$ and $b$ inclusive. When referring to a range of variables in an array, we use $T[i,j]$ to refer to the symbols $T_{i}\dots T_{j}$ inclusive, and $T[i,j)$ to refer to symbols $T_{i}\dots T_{j-1}$ inclusive. For arrays of phrases, $||$ denotes the append operation : ${\bf b}\leftarrow{\bf b}||a$ appends a variable $a$ to array $\bf b$. Let $p.q$ denote the index, $p.l$ the length, and $p.s$ the innovation of a phrase $p$. Angle brackets denote the tuple of a phrase: $\langle q,l,s\rangle$.

The compression performance of the LZ-End algorithm has already been extensively evaluated theoretically and empirically [3]. We therefore focus on evaluating the effect which the $\mathit{modify}()$ operation has on the compressed data. The evaluation considers the following factors:

• •

  the type of modification – that is, insertions, deletions, and replacements.

• •

  the size of the modification (as a fraction of overall file size).

• •

  the effect of successive modifications.

• •

  the characteristics of the file being modified.

To this end, the experiments consisted of applying the same set of modifications to two different sets of files. The first set was the Canterbury Corpus [19], which is well-known in literature. The second part of the evaluation consisted of generating a set of files of calibrated entropy, as described by Ebeling et al. [20]. These two sets of experiments allow the evaluation of the $\mathit{modify}()$ function on a set of well-known and easily accessed files, as well as extrapolation of the results to files of various entropy.

The effect of $\mathit{modify}()$ is measured by the modification ratio (MR). This is calculated as the size of the compressed data following the application of $\mathit{modify}()$, divided by the size of the compressed data if it had been decompressed, modified and recompressed.

The following set of modifications were carried out on the files:

• •

  Incremental modifications (Figure 1(a) and left column of Table II).

  The ratio reported is the mean MR of each file following 100 insertions, 100 deletions, or 100 replacements. Each modification was 0.5% of the original file size, so that each set of insertions, deletions, and replacements affected 50% of the original file.

• •

  Size of the modification (Figure 1(b) and middle columns of Table II).

  The reported MR is the mean MR of insertions, deletions and replacements of various sizes between 5% and 95% of the file size.

• •

  Position of the modification (Figure 1(c) and rightmost columns of Table II).

  The reported MR is the mean MR after a modification of size 0.5% of the file size, made at various points between 0.05 and 0.95 of the file length. For a file of 100 bytes, an edit made at 0.05 starts at the 5^th byte, while an edit made at 0.95 starts at the 95^th byte.

Although not particularly time efficient, this algorithm represents the first step in a new and interesting direction to improve the efficiency of compression functions in the future.

The $\mathit{modify}()$ operation does not require any change to the LZ-End parsing or decoding algorithms. The phrases following an application of $\mathit{modify}()$ are valid LZ-End phrases (except that the phrases are no longer unique). This means that the decoder does not need to be changed at all.

The implementation of the LZ-End parser did not optimise the encoding for short phrases. Rather, the implementation encodes even single characters in its own phrase. This is similar to the original LZ77 parsing [16], and is unlike the more optimised version of Strorer and Szymanski [21]. Whether or not fast local decoding of LZ-End data is still possible under an LZSS-type parsing applied to the LZ-End algorithm has not been investigated.

The calibrated entropy strings were produced by a bipartition $c\in[0,1]$ of the logistic map, as proposed by Ebeling et al. in [20]. To further demonstrate dependence on entropy, one can apply an FIR filter to the bit streams generated by the logistic map to correlate subsequent bits and obtain a lower entropy string. $F_{n}$, the $n$-th output value produced by the FIR filter, results from the logistic map bit sequence $S_{n}$ via an equation such as the following:

The value of the $n$-th bit is then set using a bipartition at 0.4, similar to that of the Logistic Map. This means that the FIR filter string will have a bit value of 1 wherever the logistic map string has a bit value of 1 or wherever four or more of the preceding five bits in the logistic map string are set to 1. Note that the order and the coefficients of the FIR filter above are chosen somewhat arbitrarily – all we need is some correlation. This can be achieved with a large range of FIR designs.

Ten strings of 50000 bytes each were generated for each value of the noise amplitude $\xi$ in Table I with calibration $c=0.5$ [20]. The table shows the average, minimum and maximum size in KiB to which these strings compressed. At low entropies, FIR filtering has little impact on the compressed size, but as expected reduces the compressed size somewhat for larger entropies. This shows that the effects seen cannot be mere artefacts of the logistic map generation.

Each experiment was run with three kinds of $\mathbf{str}$:

• •

  a low-entropy $\mathbf{str}$ consisting only of a series of ASCII symbols “a”,

• •

  a medium-entropy $\mathbf{str}$ which compresses to half its size, and

• •

  a high-entropy $\mathbf{str}$ which doesn’t compress.

The mean MR for these three values of $\mathbf{str}$ is reported.

We have conducted extensive validation to confirm correctness of $\mathit{modify}()$. This involved incrementally making a series of 100 random modifications of random sizes and in random positions within each file of the Canterbury Corpus [19], and confirming that each file decompressed correctly.

The first column in Table II shows the effect of 100 incremental modifications. The values reported are the mean ratio for insertions, deletions and replacements, for high, medium and low entropy $\mathbf{str}$ sources. Figure 1(a) shows the breakdown of how these operations and the entropy of the $\mathbf{str}$ relate to one another. As expected, modification most negatively affects the lowest entropy files (e.g., aaa.txt or alphabet.txt). This is because a single phrase of data from a low-entropy source encodes much more data than for a higher entropy source. We see from Figure 1(a) that the insertion of a low entropy $\mathbf{str}$ has a much smaller effect than for a $\mathbf{str}$ of higher entropy. We also see that insertion has less of an effect than the replacement and deletion operations. This is because the degradation of the compression ratio occurs mainly in the replacement of dependent phrases. An insertion will have few dependent phrases, since no phrases are being removed. The replacement operation can be viewed as a deletion followed by an insertion. This explains the greater degradation in the MR which occurs as a result of replacements compared to insertions.

The middle columns of Table II shows the effect of the size of the edit on the MR. Figure 1(b) demonstrates how the deletion, insertion and replacement operations compare for different size edits. Insertion has a constant effect on the MR, whereby the MR stays just above 1 for any size modification. Deletion has the highest MR for all sizes of edit, with the MR for replacements sandwiched between that of deletion and insertion. The MR of a deletion and replacement generally increases for larger edits. However, the experiments on the Canterbury Corpus show that this is not a universal rule, and depends on the characteristics of the individual file.

Finally, the rightmost colums of Table II shows the effect of the position of the edit on the MR. Figure 1(c) shows how the insertions, deletions and replacements relate to one another for the strings of calibrated entropy. Generally, insertions have constant effect, while replacements and deletions have almost identical effect. Deletions and replacements at the start of a file have the greatest effect on MR, and this quickly tapers off. This is due to the fact that the initial phrases at the very start of a file have many dependencies. However, specific files such as bible.txt demonstrate exceptions to this principle. The edits made in these tests are very small (0.5% of the file size), hence the small effect on MR. Once again, files of low entropy (aaa.txt and alphabet.txt) have the greatest MR.