Código lento de Huffman en Python puro

Question

Estaba trabajando en escribir una implementación rápida de una compresión de texto de código Huffman simple. La idea era escribirlo usando solo la biblioteca estándar, pero parece que no puedo encontrar una manera de hacerlo más rápido. También estoy buscando consejos sobre cómo escribirlo más "Pythonic", sin sacrificar la velocidad.

Soy consciente de que si quiero velocidad no debería usar Python, pero lo he tomado como un ejercicio para probar el rendimiento puro de 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

Comencé con su código, sys.argvlo agregué para poder pasar las rutas de los archivos en la línea de comando, descargué un archivo de texto grande ( Guerra y paz , por supuesto), ejecuté su programa y verifiqué los tamaños de los archivos:

$ 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 inadvertidamente ha inventado un algoritmo de expansión: ¡crea un archivo aproximadamente 12 veces más grande! Además, 11 segundos parecen lentos para procesar unos escasos 40M de texto. Normalmente, Python puede procesar datos de ese tamaño mucho más rápido.

Asigné temporalmente una cadena corta ( huffman) a la textvariable, sin pasar por la lectura del archivo, e imprimí algunas de sus variables intermedias. Aunque letter_freqse veía bien, alphabetera todo lo contrario de lo que queríamos:

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

El algoritmo de Huffman combina los 2 elementos con la frecuencia menos común , pero estás haciendo lo contrario. Así que modifiqué tu código de esta manera:

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

Con ese cambio, alphabetal menos parece más plausible, el archivo de salida termina siendo más pequeño que el archivo de entrada (aunque no tanto como esperaba, por lo que probablemente haya otros problemas en su código), y termina en aproximadamente 1 segundo en lugar de que 11 (probablemente porque está escribiendo un archivo de salida mucho más pequeño).

Algunas sugerencias:

• Enfóquese primero en la corrección . Preocúpese por la velocidad más tarde, y solo si realmente importa (y podría serlo, aunque no sea por otra razón que educativa).

• Los algoritmos y los efectos secundarios no se mezclan . Reorganice su código para facilitar las pruebas y la depuración. La huffman_compress()función en sí no debería preocuparse por la lectura y escritura de archivos. Debería tomar una gota de texto y devolver una gota de bytes, punto. El código altamente algorítmico (como lo es Huffman) nunca debería tener efectos secundarios; debe vivir en el reino de las funciones puras.

• Ida y vuelta de los datos . También escribe una huffman_expand()función: toma bytes, devuelve texto. Sin eso, no puede tener ninguna confianza en el proceso. En particular, desea poder hacer lo siguiente: assert original_text == huffman_expand(huffman_compress(original_text)). Eso no prueba que haya implementado Huffman correctamente (quizás invente su propio esquema de codificación especial, lo que podría ser genial), pero al menos probará que puede hacer un viaje de ida y vuelta sin pérdidas.

Answer 2

Guarde la transformación a ascii para posibles 256 caracteres.

ASCII no tiene 256 caracteres. tiene 128

Y escribe con la codificación predeterminada, que es UTF-8, por lo que escribe la mitad que no es ASCII de sus 256 caracteres como dos bytes sin razón alguna, lo que hace que su archivo sea aproximadamente 1,5 veces más grande de lo que debería ser.

Realmente deberías producir bytes .