optimal parsing

[flounder]

Hello everyone . Just thought I'd say this forum seems to be full of neat compressors, and I feel awkward asking such a basic question...

I've got a fully functioning lz compressor with greedy parsing. I'm trying to upgrade it to optimal parsing, which has led me to lazy parsing. All the explanations of lazy parsing seem to explain it as this:

1. start from the beginning of the file
2. find the longest match at the current position
3. If the match overlaps with a longer match, ignore it and proceed to the next position
4. do this until you reach the end of the file

But this seems far from optimal to me. If there's chains of matches only overlapping by one byte, a lot of matches will discarded. The next idea would be to just shorten the shorter of the 2 overlapping matches, but this also is sub-optimal for certain chains of matches.

Is this the correct way of interpreting lazy parsing? It seems too simple to get it confused. Maybe I was mistaken thinking it was optimal?

Anyways, thanks for all the other insightful posts you guys have made

[Simon Berger]

Isn?t the word "lazy" saying all? - Optimal parsing is optimal parsing :-D but I cannot say the characteristics of them to you. I would be interested too.

[thometal]

Me is interested too.

A wiki would be nice for such things!

TT

[Shelwien]

1. "Lazy" usually means "delayed"

2. "Optimal" means that you're trying to find the most compressible
sequence of matches/literals, while its possible to encode each
symbol as literal or as a part of several matches (not only length, but
offset can be different too)

3. Google is your friend: http://www.cbloom.com/algs/dictionary.html

[encode]

Well, the so called ?Lazy Matching? or ?Lazy Evaluation? is a heuristic for more optimal LZ-coding. Obviously, if at each step we will grab the longest match, we may loose even longer match within the reach of a current match. Such thing called ?Greedy Parsing?. With the original ?Lazy Matching?, we delay the coding by one-step to see, is even longer match followed by the current match? If so, we drop a literal and this new even longer match. In addition to that, we may do a ?Lazy Matching? with a few bytes lookahead. This means that we delay the coding decision for a few, not just one step/byte.
Examples:

  Greedy Parsing:
  Len := GetMatchLen(CurPos);
  // ..
  if (Len >= MINMATCH)
    Encode(Len);
  // ..
   
  Lazy Matching:
  Len = GetMatchLen(CurPos);
  if (Len >= MINMATCH) {
    NextLen = GetMatchLen(CurPos + 1);
    if (NextLen > Len)
      Len = 0; // Drop current match
  }
  // ..
  if (Len >= MINMATCH)
    Encode(Len);
  // ..
   
  Lazy Matching with a few-byte lookahead:
  Len = GetMatchLen(CurPos);
  if (Len >= MINMATCH) {
    for (i = 1; i <= LOOKAHEAD; i++) {
      NextLen = GetMatchLen(CurPos + i);
      if (NextLen >= (Len + i)) {
        Len = 0; // Drop current match
        break;
      }
    }
  }
  if (Len >= MINMATCH)
    Encode(Len);
  // ..

The ?Optimal Parsing? is more complicated. We getting ALL matches at EACH position. After, we try to build so called ?Optimal Path? or optimal sequence of literals and matches. Here are many variants on how we examine the cost or price of each choice, how we build/optimize path, etc.

[Bulat Ziganshin]

lazy evaluation is other thing

[encode]

lazy evaluation is other thing

AFAIK, it's a synonym...

[flounder]

Simon Berger wrote:
Isn?t the word "lazy" saying all? - Optimal parsing is optimal parsing :-D but I cannot say the characteristics of them to you. I would be interested too.

Whenever I looked up optimal parsing I ran into lazy parsing, so I began to think they meant the same thing

Shelwien wrote:
3. Google is your friend: http://www.cbloom.com/algs/dictionary.html

Thanks! I came across his name a lot, but skipped over it because I thought I'd already read it. This has helped clear things up.

encode wrote:
The ‘Optimal Parsing’ is more complicated. We getting ALL matches at EACH position. After, we try to build so called ‘Optimal Path’ or optimal sequence of literals and matches. Here are many variants on how we examine the cost or price of each choice, how we build/optimize path, etc.

My first attempt at optimal parsing was to find the longest possible matches and try each one of them at different lengths, but as you can probably guess that would take years to fully complete . Looks like lazy parsing is just optimal parsing without the brute force approach, hence "lazy".

[Arkanosis]

lazy evaluation is other thing

AFAIK, it's a synonym...

Not for a Haskell programmer

[Bulat Ziganshin]

Ilia, use google

[encode]

Read the Deflate specs.:

deflate() also defers the selection of matches with a lazy evaluation
mechanism. After a match of length N has been found, deflate() searches for
a longer match at the next input byte. If a longer match is found, the
previous match is truncated to a length of one (thus producing a single
literal byte) and the process of lazy evaluation begins again. Otherwise,
the original match is kept, and the next match search is attempted only N
steps later.