Exercise 2.4Z: LZW Coding and Decoding again

Two snapshots of the LZW dictionary ⇒ "Wörterbuch";
"Inhalt" ⇒ "Content"

The graph shows snapshots of the dictionary created during LZW coding of the input symbol sequence.

The upper graph is for input symbol sequence ABABABBAA.
The lower dictionary is created during LZW coding of the sequence ABABABABA.

In both cases, it is assumed that no characters other than A and B can occur at later times.

In LZW decoding, the same dictionaries are created, but then the dictionary entries occur one step later. In subtask (3) the question is asked for which coding step or for which decoding step the two snapshots shown are valid.

In LZW coding, an index $I$ is selected for each coding step $i$ and transmitted (binary). The character pair AB is represented by the index $I = 2$ in the two dictionaries. Here we consider the index $I$ as a decimal number and leave the binary representation out of consideration for this task.

With LZW decoding, a character or character sequence is generated in the same way from each index $I$ with the help of the dictionary, for example $I = 1$ leads to the character B and $I = 2$ to the character pair AB.

If a dictionary entry with the desired index $I$ is actually found, the decoding runs smoothly. However, this is not always the case:

If a new index $I$ is entered during encoding at step $i$ and this $I$ is at the same time the encoding result of the step, this index is not yet occupied in the dictionary at decoding step $i$ . The reason for this is that with the decoder the entries are made one step later than with the coder.
In the case of a "binary" input sequence $($all characters are A or B$)$, a special rule must always be applied in LZW decoding if the entry with index $I = i$ was made in coding step $i$ .

This special rule shall be illustrated by an example:

For step $i$ there is no entry in the decoder dictionary matching index $I$ .
We assume that in the previous step $(i- 1)$ the decoding result was ABBABA .
Then we add the first character of the sequence to this string. Here: ABBABAA.
Then one enters the sequence ABBABAA into the dictionary under index $I$ .

Hints:

The exercise belongs to the chapter Compression according to Lempel, Ziv and Welch.
In particular, reference is made to the pages

LZ77 - the basic form of Lempel-Ziv algorithms,

Lempel-Ziv coding with variable index bit length,

Decoding of the LZW algorithm.

Also, when solving this task, note that the LZW algorithm does not assume an empty dictionary.
Rather, the indices $I = 0$ to $I = M- 1$ contain all $M$ permissible characters of the alphabet.

Questions

$I_1 \ = \ $

$I_2 \ = \ $

$I_3 \ = \ $

$I_4 \ = \ $

$I_5 \ = \ $

$I_4 \ = \ $

$I_5 \ = \ $

$\text{Encoding:} \ \ i \ = \ $

$\text{Decoding:} \ \ i \ = \ $

	When decoding ABABABBAA in step $i = 4$.
	When decoding ABABABABA in step $i = 4$.
	When decoding ABABABABA in step $i = 5$.

Solution

(1) We use $W(I)$ to denote a field (array), that describes the dictionary and whose elements contain characters or strings.

The encoding of ABABABBAA proceeds as follows:

$i = 1$: A → $\underline{I=0}$, $W(I = 2) =$ AB,

$i = 2$: B → $\underline{I=1}$, $W(I = 3) =$ BA,

$i = 3$: AB → $\underline{I=2}$, $W(I = 4) =$ ABA,

$i = 4$: AB → $\underline{I=2}$, $W(I = 5) =$ ABB,

$i = 5$: BA → $\underline{I=3}$, $W(I = 6) =$ BAA.

Note that the last character $($A$)$ of the input string ABABABBAA at time $i = 5$ is already considered in the dictionary entry but has not yet been encoded.

(2) For the steps $i = 1$ to $i = 3$ nothing changes compared to subtask (1).

Afterwards, the following applies:

$i = 4$: ABA → $\underline{I=4}$, $W(I = 5) =$ ABAB,

$i = 5$: BA → $\underline{I=3}$, encoding completed, no new dictionary entry possible.

(3) The comparison with above results shows:

The dictionary of the encoder has the entries shown exactly after $\underline{i=4}$ encoding steps.
With the decoder, on the other hand, there is a time delay of one step: $\underline{i=5}$.

(4) Solution suggestion 2 is correct:

The special case regulation of the decoding is necessary (in the present example) if the index $I =i$ is output in the coding step $i$ .
During decoding, it then does not find the required assignment "Index → String" since the generated dictionary at time $i$ only contains entries with $I < i$ .
For the sequence ABABABBAA ⇒ $I < i$ always applies according to subtask (1) .
In contrast, the following indices would result for the sequence ABABABABA :

$$i = 1\hspace{-0.15cm}: \hspace{0.15cm} I = 0\hspace{0.05cm}, \hspace{0.5cm}i = 2\hspace{-0.15cm}: \hspace{0.15cm}I = 1\hspace{0.05cm}, \hspace{0.5cm}i = 3\hspace{-0.15cm}: \hspace{0.15cm}I = 2\hspace{0.05cm}, \hspace{0.5cm}\underline{i = 4\hspace{-0.15cm}: \hspace{0.15cm}I = 4}\hspace{0.05cm}, \hspace{0.5cm}i = 5\hspace{-0.15cm}: \hspace{0.15cm}I = 3\hspace{0.05cm}. $$

Here is a summary of the entire decoding process of ABABABABA:

The pre-assignment of the dictionary includes $(I=0$: A$)$ and $(I=1$: B$)$.

Then with the dictionary array $W(I)$:

$i = 1$: Decoding $I=0$ → A,

$i = 2$: Decoding $I=1$ → B, $W(I = 2) =$ AB,

$i = 3$: Decoding $I=2$ → AB, $W(I = 3) =$ BA,

$i = 4$: An entry with index $I = 4$ is not present ⇒ Special case rule:
One takes the last decoding result $($here AB$)$ and adds the first character of this sequence at the end ⇒ ABA.
Then ABA is stored in the dictionary under index $I = 4$ .

$i = 5$: Decoding $I=3$ → BA. End of the decoder input sequence.