Медленный код Хаффмана на чистом Python

Question

Я работал над быстрой реализацией простого сжатия текста кодом Хаффмана. Идея заключалась в том, чтобы написать его, используя только стандартную библиотеку, но я не могу найти способ сделать это быстрее. Я также ищу совета, как написать более "питонический", не жертвуя скоростью.

Я знаю, что если мне нужна скорость, мне не следует использовать Python, но я использовал это как упражнение для проверки производительности чистого Python.

from collections import Counter, defaultdict

def huffman_compress(input_file, output_file, encoding='utf8'):
    """This functions compresses a txt file using Huffman code compression."""
    
    # Store the text in memory since it is faster than reading twice
    text = open(input_file, "r", encoding=encoding).read()
    
    # Count the times each letter appears on the text
    letter_freq = Counter(text)
    alphabet = defaultdict(str)
    
    # Obtain the huffman code for each letter
    while len(letter_freq) > 1:
        (letter1, count1), (letter2, count2) = letter_freq.most_common(2)
        letter_freq[letter1+letter2] = count1 + count2
        for bit, combination in enumerate([letter1, letter2]):
            for letter in combination:
                alphabet[letter] = str(bit) + alphabet[letter]
            del letter_freq[combination]
    
    # Save the transformation to ascii for possible the 256 characters
    bit_to_ascii = {format(x, '08b'): chr(x) for x in range(256)}
    
    with open(output_file, 'w') as output:
        # Transform each letter to its huffman code
        me = ''.join(alphabet[ch] for ch in text)
        
        # Add 0's so that the string is multiple of 8
        extra_bits = 8 - len(me) % 8
        me +=  extra_bits * '0'
        
        # Write the number of letters compressed and the number of bits added
        output.write(f'{chr(len(alphabet))}{extra_bits}')
        
        # Write the letters compressed and their huffman code for the decompression
        output.write('|'.join(c for item in alphabet.items() for c in item))
        
        # Transform the huffman bits to ascii and save them on the compressed file.
        output.write(''.join(bit_to_ascii[me[j:j+8]] for j in range(0, len(me), 8)))

Answer 1

Я начал с вашего кода, добавил, sys.argvчтобы я мог передавать пути к файлам в командной строке, загрузил большой текстовый файл ( конечно, « Война и мир» ), запустил вашу программу и проверил размеры файлов:

$ curl 'https://www.gutenberg.org/files/2600/2600-0.txt' -o war-peace.txt -k $ time python huffman.py war-peace.txt encoded

real    0m11.052s
user    0m10.462s
sys 0m0.389s

$ ls -lh
-rw-r--r-- 1 fmc staff  40M Aug 24 13:51 encoded
-rw-r--r-- 1 fmc staff 3.3M Aug 24 13:50 war-peace.txt

Похоже, вы случайно изобрели алгоритм расширения: он создает файл примерно в 12 раз больше! Кроме того, 11 секунд кажутся медленными для обработки скудных 40 Мб текста. Обычно Python может обрабатывать данные такого размера намного быстрее.

Я временно присвоил переменной короткую строку ( huffman) text, минуя чтение файла, и распечатал некоторые из ваших промежуточных переменных. Несмотря на то, что letter_freqвыглядело хорошо, это alphabetбыло противоположно тому, что мы хотели

f 00000     # The most frequent letter has the longest code.
h 00001
u 0001
m 001
a 01
n 1

Алгоритм Хаффмана объединяет 2 элемента с наименьшей общей частотой, но вы делаете наоборот. Итак, я изменил ваш код следующим образом:

(letter1, count1), (letter2, count2) = letter_freq.most_common()[:-3:-1]

С этим изменением, alphabetпо крайней мере, выглядит более правдоподобно, выходной файл оказывается меньше, чем входной файл (хотя и не настолько, насколько я ожидал, поэтому в вашем коде, вероятно, есть другие проблемы), и он заканчивается примерно через 1 секунду, а чем 11 (скорее всего, потому, что он записывает гораздо меньший выходной файл).

Некоторые предложения:

• Сосредоточьтесь в первую очередь на правильности . О скорости побеспокоитесь позже - и только в том случае, если это действительно имеет значение (а может, хотя бы по той причине, что образовательная).

• Алгоритмы и побочные эффекты несовместимы . Реорганизуйте свой код, чтобы облегчить тестирование и отладку. Сама huffman_compress()функция не должна заниматься чтением и записью файлов. Он должен взять кусок текста и вернуть большой кусок байтов, точка. Высокий алгоритмический код (как Хаффман) никогда не должен иметь побочных эффектов; он должен жить в сфере чистых функций.

• Получите данные в оба конца . Также напишите huffman_expand()функцию: взять байты, вернуть текст. Без этого у вас не может быть никакой уверенности в процессе. В частности, вы хотите , чтобы быть в состоянии сделать следующее: assert original_text == huffman_expand(huffman_compress(original_text)). Это не доказывает, что вы правильно реализовали Хаффмана (возможно, вы изобрете свою собственную специальную схему кодирования, что может быть круто), но, по крайней мере, это докажет, что вы можете совершить обход без потерь.

Answer 2

Сохраните преобразование в ascii для возможных 256 символов

В ASCII нет 256 символов. В нем 128.

И вы пишете с кодировкой по умолчанию, то есть UTF-8, поэтому вы пишете не-ASCII половину ваших 256 символов как два байта без какой-либо уважительной причины, делая ваш файл примерно в 1,5 раза больше, чем он должен быть.

Вам действительно нужно просто производить байты .