Decompresses given data_bits using Lempel-Ziv-Welch compression algorithm and returns the result as a string
(data_bits: str)
| 25 | |
| 26 | |
| 27 | def decompress_data(data_bits: str) -> str: |
| 28 | """ |
| 29 | Decompresses given data_bits using Lempel-Ziv-Welch compression algorithm |
| 30 | and returns the result as a string |
| 31 | """ |
| 32 | lexicon = {"0": "0", "1": "1"} |
| 33 | result, curr_string = "", "" |
| 34 | index = len(lexicon) |
| 35 | |
| 36 | for i in range(len(data_bits)): |
| 37 | curr_string += data_bits[i] |
| 38 | if curr_string not in lexicon: |
| 39 | continue |
| 40 | |
| 41 | last_match_id = lexicon[curr_string] |
| 42 | result += last_match_id |
| 43 | lexicon[curr_string] = last_match_id + "0" |
| 44 | |
| 45 | if math.log2(index).is_integer(): |
| 46 | new_lex = {} |
| 47 | for curr_key in list(lexicon): |
| 48 | new_lex["0" + curr_key] = lexicon.pop(curr_key) |
| 49 | lexicon = new_lex |
| 50 | |
| 51 | lexicon[bin(index)[2:]] = last_match_id + "1" |
| 52 | index += 1 |
| 53 | curr_string = "" |
| 54 | return result |
| 55 | |
| 56 | |
| 57 | def write_file_binary(file_path: str, to_write: str) -> None: |