One Way To Output LZ77 Codes

Giganews Newsgroups
Subject: One Way To Output LZ77 Codes
Posted by:  Gerald Tamayo (comp…@gmail.com)
Date: Sun, 2 Sep 2018

LZ77:

LZ77 coding transmits <offset, length> codes. Many times in the compression=
process, the same matching string is coded with the same <length> code. We=
can avoid transmitting the <length> code for many strings as well as not o=
utputting a bit to identify a literal (as in LZSS) by the following:=20

Instead, read the whole input or block (or history buffer) and gather match=
ing strings and encode the <<the whole string>> e.g., <<offset>> plus <<len=
gth of the string (n>=3D2)>> only this one time, <<the number of the same m=
atching strings (ie., number of following offset codes)>>, and its succeedi=
ng occurrences in the input block by transmitting only the said <<offset>> =
codes. This is actually a "Reduced Length LZ (RLLZ).=20

The literals are outputted last *without bit flags* since they fall into th=
e block buffers not covered or "not activated" by encoded strings.=20

During decoding, the strings are written first in the output buffer using t=
he offsets, and the literals "fill in" the unwritten positions in the outpu=
t buffer.=20

-- Gerald R. Tamayo=20

Replies