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$
0
$\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 Mar 11 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. Mar 11 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 Mar 11 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. Mar 11 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$ – Phillip Williams Mar 15 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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