
Originally Posted by
Malcolm Taylor
There is also for lz77 several different optimal parsing methods. One
(used by quantum IIRC) parses all the matches in the file, and then
passes backwards over them finding the best match to reach each byte.
The result is optimal for a static encoding (much like FP).
Another one (used by 7zip and ROLZ and others), is a dynamic programming
approach which can cope with adaptive encodings. This often leads to
some fantastic results. Although I call this optimal, it is still only a
near optimal method. It always converges to a local minimum, so may not
always hit the global minimum.