For decoding a sequence of dictionary indices, we start with the same dictionary as the encoder.
As indices are processed, this dictionary is updated, but usually one step behind the updates of the encoder.
I = index sequence <i1, i2, ... ik>
D = dictionary of symbol sequences, initially
containing all one-symbol sequences
s = D[i1] # s stores the sequence of the
# most recently-received index
output s
for i in i2, i3, ..., ik
# t stores the sequence to output
if i is in D
t = D[i]
add s + first_symbol(t) to D
else
t = s + first_symbol(s)
add t to D
output t
s = t
There are two cases in each iteration:
Case 1
For an index that is in the dictionary (i.e. "i is in D"): We look up that index's sequence from the dictionary and output that sequence. Then we add a new entry to the dictionrary, which is the previously output sequence plus the first symbol of the next sequence. That corresponds to
add s+x to D
in the encoder, where s is the previously output sequence and x is the first symbol of the next sequence; this next sequence is started on the
s = <x>
line of the encoder. At that point in the encoder, the sequence has only one symbol, x, but will later get more symbols. In the final sequence, x will be the first symbol, hence first_symbol(t) in the decoder.
Case 2
For an index that is not in the dictionary, the decoder still knows what that index should hold. Here's how this happens:
- Initially, the encoder and decoder both have the same dictionary with indices $0 \ldots k-1$.
- In the encoder: With the next x,
sequence s+x is not in the dictionary,
so the index of s is
output, s+x is added to the
dictionary at index $\mathbf{k}$,
and x is used as the first symbol in the
next sequence:
So we know that the next index output from the encoder will be for a sequence that starts with x.
- If the next index output from the encoder is not
$k$, the decoder will add s +
first_symbol(t) to the decoder's dictionary
at index $k$ and $k$ will henceforth be
recognized. But that's not what happened.
So $k$ is not recognized only if it is the next index output immediately after s+x was added to the dictionary at index $k$.
- If the next index output from the
encoder is $k$, the decoder knows that
sequence s is immediately followed by
sequence s+x. Since the first symbol
in the next sequence is x (from step 2
above), the decoder can extract x as
the first symbol of s. Then decoder
can add s+x to its dictionary at index
$k$.
Here's an example:
The sequence is "abababab".
The dictionary initially contains
| index | sequence |
|---|---|
| 0 | a |
| 1 | b |
The encoding proceeds as follows:
| s before | x | s+x in D | s after | output | dictionary new entry |
|---|---|---|---|---|---|
| a | yes | a | |||
| a | b | no | b | 0 | 2: ab |
| b | a | no | a | 1 | 3: ba |
| a | b | yes | ab | ||
| ab | a | no | a | 2 | 4: aba |
| a | b | yes | ab | ||
| ab | a | yes | aba | ||
| aba | b | no | b | 4 | 5: abab |
| b | 1 |
The sequence "abababab" is encoded as 1,0,2,4,1.
In the decoder, this sequence of indices is processed as follows:
| s before | i | i is in D | t after | output | dictionary new entry |
|---|---|---|---|---|---|
| 0 | a | ||||
| a | 1 | yes | b | b | 2: ab |
| b | 2 | yes | ab | ab | 3: ba |
| ab | 4 | no | aba | aba | 4: aba |
| aba | 1 | yes | b | b |
The "no" line above corresponds to an index that is not in the decoder's dictionary.