1
$\begingroup$

How does LZW decompress data with dictionary clearing/flushing? I understand that a space is reserved in the dictionary that represents a clear code (usually 256), but how is this code actually used when compressing and decompressing data? My thoughts for compression are that it checks the table size, and if the table size has reached the maximum size it appends the flush character to the output before resetting the dictionary. I'm not sure what it does for decompression though.

$\endgroup$

2 Answers 2

2
$\begingroup$

When the compressor clears the dictionary, it emits the clear code. This enables the decompressor to stay in sync: when it sees the clear code, the decompressor clears its own dictionary. In this way, the decompressor can reconstruct/infer the state of the encoder's dictionary at each step.

Wikipedia says:

Smart encoders can monitor the compression efficiency and clear the table whenever the existing table no longer matches the input well.

$\endgroup$
5
  • $\begingroup$ Okay, that makes sense. What does the decoder do with the data it's already processing? Does it clear that as well or does it "skip" to the next piece of data? $\endgroup$
    – hakmad
    Commented Mar 11, 2021 at 13:59
  • $\begingroup$ @hakmad, no? I'm not sure what it would mean to clear the data, though, so I might have misunderstood what you are asking. $\endgroup$
    – D.W.
    Commented Mar 11, 2021 at 19:24
  • $\begingroup$ My bad, I explained it incorrectly. During decompression, the algorithm will already have some data that it is working on (the previous string and current code). My question is what happens to that data? Does it also get flushed or does the algorithm do something else with it? $\endgroup$
    – hakmad
    Commented Mar 11, 2021 at 21:50
  • $\begingroup$ @hakmad, yup. Flushed. The same as whatever the encoder did. The encoder is just trying to stay in sync with the encoder and invert it. $\endgroup$
    – D.W.
    Commented Mar 11, 2021 at 23:15
  • $\begingroup$ Before sending the data clear code, the current code that was built up should be sent . After the data clear, A new data code is started from the current position in the data being compressed, as if it was the start of the data. all aspect are reset and starts rebuilding the compression tables anew. the main trick is when to decide to send the clear data . Most should process more data, even if no new codes can be added, Just because the decode table is full does not mean it is no longer useful. it is up to the compression side when to send the reset. $\endgroup$ Commented Mar 15, 2021 at 18:36
0
$\begingroup$

Anybody who has worked on BOTH parts of LZW, that is, Compression and Decompression, knows they operate identically, building the same translation table from the stream. There is no need to send a flag code. They would both decide to reset the table at the same point.

$\endgroup$
2
  • $\begingroup$ [Compression and Decompression] would both decide to reset the table at the same point They could. Compression can try to decrease information transmitted choosing and communicating an advantageous time to reset. $\endgroup$
    – greybeard
    Commented Apr 25 at 17:50
  • $\begingroup$ They have the same dictionary, but Compressor have to build some index for efficient search, and it may spend extra time analyzing the data and sending results of this analysis to Decompressor in order to reduce the decompression time. $\endgroup$
    – Bulat
    Commented Apr 26 at 20:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.