LZ77 Coding

LZ77.py

class LZ77Coding:
    SLIDING_WINDOW_SIZE = 4096
    LOOKHEAD_BUFFER_SIZE = 32

    def search_longest_match(self, data, cursor):
        best_position, best_length, next_char = 0, 0, 0
        search_index = max(cursor - self.SLIDING_WINDOW_SIZE, 0)
        end_buffer_index = min(len(data) - 1,
                               cursor + self.LOOKHEAD_BUFFER_SIZE - 1)

        while search_index < cursor:
            if data[search_index] == data[cursor]:
                length = 0
                while (search_index + length) < cursor \
                        and (cursor + length) < end_buffer_index:
                    if data[search_index + length] == data[cursor + length]:
                        length += 1
                    else:
                        break

                if length > best_length:
                    best_position = search_index
                    best_length = length
                    next_char = data[cursor + length]

            search_index += 1

        if not best_length:
            next_char = data[cursor]

        return best_position, best_length, next_char

    def encoding(self, data):
        result = []

        cursor = 0
        while cursor < len(data):
            match = self.search_longest_match(data, cursor)
            result.append(match)
            cursor += max(match[1] + 1, 1)

        return result

    def decoding(self, data):
        result = []

        for pair in data:
            if not pair[1]:
                result.append(pair[2])
            else:
                chars = result[pair[0]:pair[0] + pair[1]]
                result.extend(chars)
                result.append(pair[2])

        return ''.join(result)