calgorithmcompressionpseudocodelz77

Could you give me some explain of LZ77 Algorithm?

I'm trying to learn LZ77 algorithm with my friend, and some case give us a confusion.

for example)

init

What I thought the LLD tuple is : Literal: 'a' Length: 4 Distance: 4

What my friend thought the LLD tuple is : Literal: 'c' Length: 6 Distance: 4

I thought the algorithm to find longest match string only checks in search buffer, but he says there is no limit to find match string.

Who's answer is correct?

Solution

  • I can't give you a definitive answer, but I can show there's no reason LZ77 couldn't support "overly long" tuples.

    I believe you're asking if the length component of a tuple can be larger than its distance component.

    In other words, I believe you're asking which of the following streams of tuples would be produced:

    1. ( Length: 0, Distance: 0, Char: 'a' )
    2. (0,0,'b')
    3. (0,0,'c')
    4. (2,3,'b')
    5. (4,4,'c')[1] Length capped to distance.
    6. (2,4,'c')
    7. (0,0,'a')

    or

    1. (0,0,'a')
    2. (0,0,'b')
    3. (0,0,'c')
    4. (2,3,'b')
    5. (7,4,'c')[2] Length larger than distance.
    6. (0,0,'a')

    Obviously, the latter would produce better compression.

    I can't give you a definitive answer, but I can show that the decoder can handle "overly long" tuples just as easily as the encoder can produce them. As such, there's no reason LZ77 couldn't support them.

    Reconstructing the input from the first stream

    1. (0,0,'a'): "" + "a" ⇒ "a"
    2. (0,0,'b'): "" + "b" ⇒ "ab"
    3. (0,0,'c'): "" + "c" ⇒ "abc"
    4. (2,3,'b'): "ab" + "b" ⇒ "abcabb"
    5. (4,4,'c'): "cabb" + "c" ⇒ "abcabbcabbc"
    6. (2,4,'c'): "ab" + "c" ⇒ "abcabbcabbcabc"
    7. (0,0,'a'): "" + "a" ⇒ "abcabbcabbcabca"

    Simple.

    Reconstructing the input from the second stream

    1. (0,0,'a'): "" + "a" ⇒ "a"

    2. (0,0,'b'): "" + "b" ⇒ "ab"

    3. (0,0,'c'): "" + "c" ⇒ "abc"

    4. (2,3,'b'): "ab" + "b" ⇒ "abcabb"

    5. (7,4,'c')

      So far, we've produced abcabb. The tuple says the next 7 characters start 4 characters from the end of abcabb.

      a b c c a b b _ _ _ _ _ _ _ c
      | | | | ^ ^ ^ ^ ^ ^ ^
      | | | | | | | | | | |
      +-)-)-)-+ | | | ? ? ?
        +-)-)---+ | |
          +-)-----+ |
            +-------+

      We're missing three characters! Are are we? If it's all one buffer and we copy from left to right, we just have to keep going.

                        +-------+
                +-)-----+ |
              +-)-)---+ | |
              | | |   | | |
              | | |   v v v
a b c c a b b _ _ _ _ _ _ _ c
      | | | | ^ ^ ^ ^
      | | | | | | | |
      +-)-)-)-+ | | |
        +-)-)---+ | |
          +-)-----+ |
            +-------+

      So this works with no extra effort!

      (7,4,'c'): "cabbcab" + "c" ⇒ "abcabbcabbcabc"

    6. (0,0,'a'): "" + "a" ⇒ "abcabbcabbcabca"

    1. You incorrectly said (4,4,'a').
    2. You incorrectly said (6,4,'c').