sending repeated words very compactly. Decoding To decode an LZW-compressed archive, one needs to know in advance the initial dictionary used, but additional entries can be reconstructed as they are always simply concatenations of previous entries. At each stage, the decoder receives a code X; it looks X up in the table and outputs the sequence χ it codes, and it conjectures χ + ? as the entry the encoder just added – because the encoder emitted X for χ precisely because χ + ? was not in the table, and the encoder goes ahead and adds it. But what is the missing letter? It is the first letter in the sequence coded by the next code Z that the decoder receives. So the decoder looks up Z, decodes it into the sequence ω and takes the first letter z and tacks it onto the end of χ as the next dictionary entry. This works as long as the codes received are in the decoder's dictionary, so that they can be decoded into sequences. What happens if the decoder receives a code Z that is not yet in its dictionary? Since the decoder is always just one code behind the encoder, Z can be in the encoder's dictionary only if the encoder just generated it, when emitting the previous code X for χ. Thus Z codes some ω that is χ + ?, and the decoder can determine the unknown character as follows: The decoder sees X and then Z, where X codes the sequence χ and Z codes some unknown sequence ω. The decoder knows that the encoder just added Z as a code for χ + some unknown character c, so ω = χ + c. Since c is the first character in the input stream after χ, and since ω is the string appearing immediately after χ, c must be the first character of the sequence ω. Since χ is an initial substring of ω, c must also be the first character of χ. So even though the Z code is not in the table, the decoder is able to infer the unknown sequence and adds χ + (the first character of χ) to the table as the value of Z. This situation occurs whenever the encoder encounters input of the form cScSc, where c is a single character, S is a string and cS is already