LZ77 Match Bit Savings

Problem

Each LZ77 token is a triple [offset, length, next_char]. A token with length > 0 replaces that many literal characters, so its saving is length * literal_bits - offset_bits - length_bits, while pure literals save nothing. Return the total savings in bits over all triples, which may be negative for short matches.

Hint

Only matched runs replace literals, and each reference costs a fixed offset plus length field.

Test cases

case 1

in: [[[0,3,"x"],[0,0,"y"],[2,4,""]],5,4,8]

expected: 38

case 2

in: [[[1,1,"a"]],8,8,8]

expected: -8

case 3

in: [[],5,4,8]

expected: 0

case 4

in: [[[0,0,"a"]],5,4,8]

expected: 0

Starter codePython

def lz77_match_savings(triples, offset_bits, length_bits, literal_bits):
    # Your code here
    pass

4 test cases · run your code against them in the editor