Сжатие с помощью алгоритма LZW на pytohn
Потребовалось написать реализацию алгоритма LZW на python. В результате выполнения программы на примере входного файла небольшого размера выходной файл имеет размер, превышающий размер входного. Код:
import argparse
from struct import *
mode = ''
file_paths = []
arch_path = ''
class Compressor:
def __init__(self, file_paths, arch_path):
self.file_paths = file_paths
self.arch_path = arch_path
def readFile(self, path):
input_file = open(path, 'rt')
data = input_file.read()
input_file.close()
return data
def compressData(self, data, dictionary, dict_size):
compessed_data = []
string = ''
for symbol in data:
new_string = string + symbol
if new_string in dictionary:
string = new_string
else:
compessed_data.append(dictionary[string])
dictionary[new_string] = dict_size
dict_size += 1
string = symbol
if string in dictionary:
compessed_data.append(dictionary[string])
return compessed_data
def writeFile(self, compressed_data):
output_file = open(self.arch_path, 'wb')
for data in compressed_data:
output_file.write(pack('>H', int(data)))
output_file.close()
def compress(self):
for path in self.file_paths:
dict_size = 256
dictionary = {chr(i): i for i in range(dict_size)}
data = self.readFile(path)
compressed_data = self.compressData(data, dictionary, dict_size)
self.writeFile(compressed_data)
if __name__ == '__main__':
args = parseCmdArgs(sys.argv)
if args.mode == 'pack':
Compressor(<путь к файлу>, <путь к архиву>).compress()
Текст в исходном файле: "abacabadabacabae" (16 bytes) Размер выходного файла - 22 bytes Почему выходной файл имеет больший размер?
Ответы (1 шт):
В алгоритме lzw происходит расширение алфавита. Например, вместо 8 бит на символ используется 16, но при этом 16 бит кодируют некоторую последовательность символов.
То есть строка "abcd", которая изначально весила 4 байта, будет весить в 2 раза больше (т.к. нет повторяющихся символом и невозможно расширить алфавит). Сжатие будет заметно только на больших данных, и чем больше будет повторяющихся последовательностей символов, тем эффективнее будет сжатие.