lz77 compression algorithm lossless data compression published in papers by abraham lempel and jacob ziv in 1977 also known as lz1 or slidingwindow compression form the basis for many variations including lzw lzss lzma and others it uses a sliding window method within the sliding window we have search buffer look ahead buffer lenslidingwindow lensearchbuffer lenlookaheadbuffer lz77 manages a dictionary that uses triples composed of offset into search buffer it s the distance between the start of a phrase and the beginning of a file length of the match it s the number of characters that make up a phrase the indicator is represented by a character that is going to be encoded next as a file is parsed the dictionary is dynamically updated to reflect the compressed data contents and size examples cabracadabrarrarrad 0 0 c 0 0 a 0 0 b 0 0 r 3 1 c 2 1 d 7 4 r 3 5 d ababcbababaa 0 0 a 0 0 b 2 2 c 4 3 a 2 2 a aacaacabcabaaac 0 0 a 1 1 c 3 4 b 3 3 a 1 2 c sources en wikipedia orgwikilz77andlz78 dataclass representing triplet called token consisting of length offset and indicator this triplet is used during lz77 compression token token1 2 c reprtoken 1 2 c strtoken 1 2 c class containing compress and decompress methods using lz77 compression algorithm compress the given string text using lz77 compression algorithm args text string to be compressed returns output the compressed text as a list of tokens lz77compressor lz77compressor strlz77compressor compressababcbababaa 0 0 a 0 0 b 2 2 c 4 3 a 2 2 a strlz77compressor compressaacaacabcabaaac 0 0 a 1 1 c 3 4 b 3 3 a 1 2 c while there are still characters in text to compress find the next encoding phrase triplet with offset length indicator the next encoding character update the search buffer add new characters from text into it check if size exceed the max search buffer size if so drop the oldest elements update the text append the token to output convert the list of tokens into an output string args tokens list containing triplets offset length char returns output decompressed text tests lz77compressor lz77compressor lz77compressor decompresstoken0 0 c token0 0 a token0 0 b token0 0 r token3 1 c token2 1 d token7 4 r token3 5 d cabracadabrarrarrad lz77compressor decompresstoken0 0 a token0 0 b token2 2 c token4 3 a token2 2 a ababcbababaa lz77compressor decompresstoken0 0 a token1 1 c token3 4 b token3 3 a token1 2 c aacaacabcabaaac finds the encoding token for the first character in the text tests lz77compressor lz77compressor lz77compressor findencodingtokenabrarrarrad abracad offset 7 lz77compressor findencodingtokenadabrarrarrad cabrac length 1 lz77compressor findencodingtokenabc xyz offset 0 lz77compressor findencodingtoken xyz offset traceback most recent call last valueerror we need some text to work with lz77compressor findencodingtokenabc offset 0 initialise result parameters to default values if the found length is bigger than the current or if it s equal which means it s offset is smaller update offset and length calculate the longest possible match of text and window characters from textindex in text and windowindex in window args text description window sliding window textindex index of character in text windowindex index of character in sliding window returns the maximum match between text and window from given indexes tests lz77compressor lz77compressor13 6 lz77compressor matchlengthfromindexrarrad adabrar 0 4 5 lz77compressor matchlengthfromindexadabrarrarrad cabrac 0 1 1 initialize compressor class example dataclass representing triplet called token consisting of length offset and indicator this triplet is used during lz77 compression token token 1 2 c repr token 1 2 c str token 1 2 c class containing compress and decompress methods using lz77 compression algorithm compress the given string text using lz77 compression algorithm args text string to be compressed returns output the compressed text as a list of tokens lz77_compressor lz77compressor str lz77_compressor compress ababcbababaa 0 0 a 0 0 b 2 2 c 4 3 a 2 2 a str lz77_compressor compress aacaacabcabaaac 0 0 a 1 1 c 3 4 b 3 3 a 1 2 c while there are still characters in text to compress find the next encoding phrase triplet with offset length indicator the next encoding character update the search buffer add new characters from text into it check if size exceed the max search buffer size if so drop the oldest elements update the text append the token to output convert the list of tokens into an output string args tokens list containing triplets offset length char returns output decompressed text tests lz77_compressor lz77compressor lz77_compressor decompress token 0 0 c token 0 0 a token 0 0 b token 0 0 r token 3 1 c token 2 1 d token 7 4 r token 3 5 d cabracadabrarrarrad lz77_compressor decompress token 0 0 a token 0 0 b token 2 2 c token 4 3 a token 2 2 a ababcbababaa lz77_compressor decompress token 0 0 a token 1 1 c token 3 4 b token 3 3 a token 1 2 c aacaacabcabaaac finds the encoding token for the first character in the text tests lz77_compressor lz77compressor lz77_compressor _find_encoding_token abrarrarrad abracad offset 7 lz77_compressor _find_encoding_token adabrarrarrad cabrac length 1 lz77_compressor _find_encoding_token abc xyz offset 0 lz77_compressor _find_encoding_token xyz offset traceback most recent call last valueerror we need some text to work with lz77_compressor _find_encoding_token abc offset 0 initialise result parameters to default values if the found length is bigger than the current or if it s equal which means it s offset is smaller update offset and length calculate the longest possible match of text and window characters from text_index in text and window_index in window args text _description_ window sliding window text_index index of character in text window_index index of character in sliding window returns the maximum match between text and window from given indexes tests lz77_compressor lz77compressor 13 6 lz77_compressor _match_length_from_index rarrad adabrar 0 4 5 lz77_compressor _match_length_from_index adabrarrarrad cabrac 0 1 1 initialize compressor class example
from dataclasses import dataclass

__version__ = "0.1"
__author__ = "Lucia Harcekova"


@dataclass
class Token:
    

    offset: int
    length: int
    indicator: str

    def __repr__(self) -> str:
        
        return f"({self.offset}, {self.length}, {self.indicator})"


class LZ77Compressor:
    

    def __init__(self, window_size: int = 13, lookahead_buffer_size: int = 6) -> None:
        self.window_size = window_size
        self.lookahead_buffer_size = lookahead_buffer_size
        self.search_buffer_size = self.window_size - self.lookahead_buffer_size

    def compress(self, text: str) -> list[Token]:
        

        output = []
        search_buffer = ""

        
        while text:
            
            
            token = self._find_encoding_token(text, search_buffer) 
            search_buffer += text[: token.length + 1]
            if len(search_buffer) > self.search_buffer_size:
                search_buffer = search_buffer[-self.search_buffer_size :]

            
            text = text[token.length + 1 :]

            output.append(token)

        return output

    def decompress(self, tokens: list[Token]) -> str:
    
        output = ""

        for token in tokens:
            for _ in range(token.length):
                output += output[-token.offset]
            output += token.indicator

        return output

    def _find_encoding_token(self, text: str, search_buffer: str) -> Token:
        

        if not text:
            raise ValueError("We need some text to work with.")

        
        length, offset = 0, 0

        if not search_buffer:
            return Token(offset, length, text[length])

        for i, character in enumerate(search_buffer):
            found_offset = len(search_buffer) - i
            if character == text[0]:
                found_length = self._match_length_from_index(text, search_buffer, 0, i)
                
                
                if found_length >= length:
                    offset, length = found_offset, found_length

        return Token(offset, length, text[length])

    def _match_length_from_index(
        self, text: str, window: str, text_index: int, window_index: int
    ) -> int:
        
        if not text or text[text_index] != window[window_index]:
            return 0
        return 1 + self._match_length_from_index(
            text, window + text[text_index], text_index + 1, window_index + 1
        )


if __name__ == "__main__":
    from doctest import testmod

    testmod()
    
    lz77_compressor = LZ77Compressor(window_size=13, lookahead_buffer_size=6)

    
    TEXT = "cabracadabrarrarrad"
    compressed_text = lz77_compressor.compress(TEXT)
    print(lz77_compressor.compress("ababcbababaa"))
    decompressed_text = lz77_compressor.decompress(compressed_text)
    assert decompressed_text == TEXT, "The LZ77 algorithm returned the invalid result."