lempel_ziv_decompress.py

"""
One of the several implementations of Lempel-Ziv-Welch decompression algorithm
https://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch
"""

importmath
importsys


defread_file_binary(file_path: str) ->str:
"""
 Reads given file as bytes and returns them as a long string
 """
result=""
try:
withopen(file_path, "rb") asbinary_file:
data=binary_file.read()
fordatindata:
curr_byte=f"{dat:08b}"
result+=curr_byte
returnresult
exceptOSError:
print("File not accessible")
sys.exit()


defdecompress_data(data_bits: str) ->str:
"""
 Decompresses given data_bits using Lempel-Ziv-Welch compression algorithm
 and returns the result as a string
 """
lexicon= {"0": "0", "1": "1"}
result, curr_string="", ""
index=len(lexicon)

foriinrange(len(data_bits)):
curr_string+=data_bits[i]
ifcurr_stringnotinlexicon:
continue

last_match_id=lexicon[curr_string]
result+=last_match_id
lexicon[curr_string] =last_match_id+"0"

ifmath.log2(index).is_integer():
new_lex= {}
forcurr_keyinlist(lexicon):
new_lex["0"+curr_key] =lexicon.pop(curr_key)
lexicon=new_lex

lexicon[bin(index)[2:]] =last_match_id+"1"
index+=1
curr_string=""
returnresult


defwrite_file_binary(file_path: str, to_write: str) ->None:
"""
 Writes given to_write string (should only consist of 0's and 1's) as bytes in the
 file
 """
byte_length=8
try:
withopen(file_path, "wb") asopened_file:
result_byte_array= [
to_write[i : i+byte_length]
foriinrange(0, len(to_write), byte_length)
 ]

iflen(result_byte_array[-1]) %byte_length==0:
result_byte_array.append("10000000")
else:
result_byte_array[-1] +="1"+"0"* (
byte_length-len(result_byte_array[-1]) -1
 )

foreleminresult_byte_array[:-1]:
opened_file.write(int(elem, 2).to_bytes(1, byteorder="big"))
exceptOSError:
print("File not accessible")
sys.exit()


defremove_prefix(data_bits: str) ->str:
"""
 Removes size prefix, that compressed file should have
 Returns the result
 """
counter=0
forletterindata_bits:
ifletter=="1":
break
counter+=1

data_bits=data_bits[counter:]
data_bits=data_bits[counter+1 :]
returndata_bits


defcompress(source_path: str, destination_path: str) ->None:
"""
 Reads source file, decompresses it and writes the result in destination file
 """
data_bits=read_file_binary(source_path)
data_bits=remove_prefix(data_bits)
decompressed=decompress_data(data_bits)
write_file_binary(destination_path, decompressed)


if__name__=="__main__":
compress(sys.argv[1], sys.argv[2])