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("a
(self, text: str)
| 67 | self.search_buffer_size = self.window_size - self.lookahead_buffer_size |
| 68 | |
| 69 | def compress(self, text: str) -> list[Token]: |
| 70 | """ |
| 71 | Compress the given string text using LZ77 compression algorithm. |
| 72 | |
| 73 | Args: |
| 74 | text: string to be compressed |
| 75 | |
| 76 | Returns: |
| 77 | output: the compressed text as a list of Tokens |
| 78 | |
| 79 | >>> lz77_compressor = LZ77Compressor() |
| 80 | >>> str(lz77_compressor.compress("ababcbababaa")) |
| 81 | '[(0, 0, a), (0, 0, b), (2, 2, c), (4, 3, a), (2, 2, a)]' |
| 82 | >>> str(lz77_compressor.compress("aacaacabcabaaac")) |
| 83 | '[(0, 0, a), (1, 1, c), (3, 4, b), (3, 3, a), (1, 2, c)]' |
| 84 | """ |
| 85 | |
| 86 | output = [] |
| 87 | search_buffer = "" |
| 88 | |
| 89 | # while there are still characters in text to compress |
| 90 | while text: |
| 91 | # find the next encoding phrase |
| 92 | # - triplet with offset, length, indicator (the next encoding character) |
| 93 | token = self._find_encoding_token(text, search_buffer) |
| 94 | |
| 95 | # update the search buffer: |
| 96 | # - add new characters from text into it |
| 97 | # - check if size exceed the max search buffer size, if so, drop the |
| 98 | # oldest elements |
| 99 | search_buffer += text[: token.length + 1] |
| 100 | if len(search_buffer) > self.search_buffer_size: |
| 101 | search_buffer = search_buffer[-self.search_buffer_size :] |
| 102 | |
| 103 | # update the text |
| 104 | text = text[token.length + 1 :] |
| 105 | |
| 106 | # append the token to output |
| 107 | output.append(token) |
| 108 | |
| 109 | return output |
| 110 | |
| 111 | def decompress(self, tokens: list[Token]) -> str: |
| 112 | """ |
no test coverage detected