1
$\begingroup$

The LZ77 compression algorithm uses a sliding window technique, where the window consists of a look-ahead puffer and a search-buffer. What I am wondering is how the algorithm handles the case if the match of the word in the search-buffer is the entire word in the look-ahead buffer? According to the desriptions I find, the algorithm matches as long as it can, and then outputs the offset, the length of the match and the next token after the matched portion in the look-ahead buffer, but in case the entire look-ahead buffer is matched we do not have a next token to output?

I nowhere find this case described, for example the pseudocode just states "X first char after p in view", but I am asking about the case where we have no char after p in the view, as p is entire view?

For example, consider a search buffer of size 5 and a look-ahead buffer of size 4 and we read in

|abrar|rarr|ad

then we find a match at offset 3, and the match (which extends behind the boundary between both puffers, but this is no problem) goes up to all of rarr, even the next a could be matched, but what we should do now, should we output (3,4, C(a)) where C(a) denotes the code of a which is not in the look-ahead buffer, or should we just match the first 3 tokens?

$\endgroup$
1
$\begingroup$

A simple solution: your look ahead buffer is no smaller than your longest match length. As long as the start position is in the Search Buffer(a min of 1 byte), then the look-ahead buffer will have that one extra byte available to use as the follow byte

$\endgroup$
  • $\begingroup$ Yes, also thought to just reserve one more token in the look-a-head buffer, but this was nowhere mentioned so I asked here. $\endgroup$ – StefanH Jun 2 '17 at 16:54

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.