Сжатие с помощью алгоритма 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 шт):

Автор решения: tewboat

В алгоритме lzw происходит расширение алфавита. Например, вместо 8 бит на символ используется 16, но при этом 16 бит кодируют некоторую последовательность символов.

То есть строка "abcd", которая изначально весила 4 байта, будет весить в 2 раза больше (т.к. нет повторяющихся символом и невозможно расширить алфавит). Сжатие будет заметно только на больших данных, и чем больше будет повторяющихся последовательностей символов, тем эффективнее будет сжатие.

→ Ссылка