Código Huffman lento em Python puro

Question

Eu estava trabalhando para escrever uma implementação rápida de uma compressão simples de código Huffman de texto. A ideia era escrevê-lo usando apenas a biblioteca padrão, mas não consigo encontrar uma maneira de torná-lo mais rápido. Também estou procurando conselhos sobre como escrevê-lo mais "Pythonic", sem sacrificar a velocidade.

Estou ciente de que, se quero velocidade, não devo usar Python, mas considerei isso um exercício para testar o desempenho puro do 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

Comecei com seu código, adicionei sys.argvpara poder passar caminhos de arquivo na linha de comando, baixei um grande arquivo de texto ( guerra e paz , é claro), executei seu programa e verifiquei os tamanhos dos arquivos:

$ 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

Parece que você inventou inadvertidamente um algoritmo de expansão: ele cria um arquivo aproximadamente 12x maior! Além disso, 11 segundos parecem lentos para processar escassos 40M de texto. Normalmente, o Python pode processar dados desse tamanho muito mais rapidamente.

Atribuí temporariamente uma string curta ( huffman) à textvariável, ignorando a leitura do arquivo e imprimi algumas de suas variáveis ​​intermediárias. Embora letter_freqparecesse bom, alphabetera o oposto do que queremos:

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

O algoritmo de Huffman combina os 2 elementos com a frequência menos comum , mas você está fazendo o contrário. Então, ajustei seu código assim:

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

Com essa alteração, alphabetpelo menos parece mais plausível, o arquivo de saída acaba sendo menor que o arquivo de entrada (embora não tanto quanto eu esperava, então provavelmente há outros problemas em seu código) e termina em cerca de 1 segundo, em vez de 11 (provavelmente porque está gravando um arquivo de saída muito menor).

Algumas sugestões:

• Concentre-se primeiro na correção . Preocupe-se com a velocidade mais tarde - e apenas se isso realmente importa (e pode, mesmo que não seja educacional).

• Algoritmos e efeitos colaterais não se misturam . Reorganize seu código para facilitar o teste e a depuração. A huffman_compress()função em si não deve se preocupar com leitura e escrita de arquivos. Deve pegar um blob de texto e retornar um blob de bytes, ponto final. Código altamente algorítmico (como Huffman é) nunca deve ter efeitos colaterais; deve viver no reino das funções puras.

• Ida e volta os dados . Também escreva uma huffman_expand()função: pegue bytes, retorne texto. Sem isso, você não pode ter nenhuma confiança no processo. Em particular, você deseja ser capaz de fazer o seguinte: assert original_text == huffman_expand(huffman_compress(original_text)). Isso não prova que você implementou Huffman corretamente (talvez você invente seu próprio esquema de codificação especial, o que pode ser legal), mas pelo menos provará que você pode fazer uma viagem de ida e volta sem perdas.

Answer 2

Salve a transformação em ASCII para possíveis 256 caracteres

ASCII não tem 256 caracteres. Tem 128.

E você escreve com a codificação padrão, que é UTF-8, então você escreve a metade não ASCII de seus 256 caracteres como dois bytes sem nenhum motivo, tornando seu arquivo cerca de 1,5 vezes maior do que deveria ser.

Você realmente deve apenas produzir bytes .