Codice lento di Huffman in puro Python

Aug 22 2020

Stavo lavorando alla scrittura di una rapida implementazione di una semplice compressione del testo in codice Huffman. L'idea era di scriverlo utilizzando solo la libreria standard, ma non riesco a trovare un modo per renderlo più veloce. Sto anche cercando consigli su come scriverlo più "Pythonic", senza sacrificare la velocità.

Sono consapevole che se voglio la velocità non dovrei usare Python, ma l'ho preso come esercizio per testare le prestazioni di Python puro.

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)))

Risposte

8 FMc Aug 25 2020 at 05:08

Ho iniziato con il tuo codice, aggiunto sys.argvin modo da poter passare i percorsi dei file sulla riga di comando, scaricato un grosso file di testo ( War and Peace , ovviamente), eseguito il tuo programma e controllato le dimensioni dei file:

$ 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

Sembra che tu abbia inavvertitamente inventato un algoritmo di espansione: crea un file circa 12 volte più grande! Inoltre, 11 secondi sembrano lenti per elaborare un misero 40 M di testo. Normalmente Python può scricchiolare dati di quelle dimensioni molto più rapidamente.

Ho temporaneamente assegnato una breve stringa ( huffman) alla textvariabile, ignorando la lettura del file e stampato alcune delle tue variabili intermedie. Anche se letter_freqsembrava a posto, alphabetera l'opposto di quello che volevamo:

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

L'algoritmo di Huffman combina i 2 elementi con la frequenza meno comune , ma stai facendo il contrario. Quindi ho modificato il tuo codice in questo modo:

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

Con quella modifica, alphabetalmeno sembra più plausibile, il file di output finisce per essere più piccolo del file di input (anche se non tanto quanto mi aspetto, quindi probabilmente ci sono altri problemi nel tuo codice), e finisce in circa 1 secondo piuttosto di 11 (molto probabilmente perché sta scrivendo un file di output molto più piccolo).

Alcuni suggerimenti:

  • Concentrati prima sulla correttezza . Preoccupati della velocità in seguito - e solo se conta davvero (e potrebbe, se non altro per quello educativo).

  • Gli algoritmi e gli effetti collaterali non vanno d'accordo . Riorganizza il tuo codice per facilitare test e debug. La huffman_compress()funzione stessa non dovrebbe occuparsi della lettura e della scrittura dei file. Dovrebbe prendere un blob di testo e restituire un blob di byte, punto. Il codice altamente algoritmico (come lo è Huffman) non dovrebbe mai avere effetti collaterali; dovrebbe vivere nel regno delle funzioni pure.

  • Roundtrip dei dati . Scrivi anche una huffman_expand()funzione: prendi byte, restituisci testo. Senza quello, non puoi avere alcuna fiducia nel processo. In particolare, vuoi essere in grado di fare quanto segue: assert original_text == huffman_expand(huffman_compress(original_text)). Ciò non dimostra che hai implementato correttamente Huffman (forse inventerai il tuo schema di codifica speciale, che potrebbe essere interessante), ma almeno dimostrerà che puoi fare un viaggio di andata e ritorno senza perdite.

2 superbrain Aug 25 2020 at 14:49

Salva la trasformazione in ascii per eventuali 256 caratteri

ASCII non ha 256 caratteri. Ne ha 128.

E scrivi con la codifica predefinita, che è UTF-8, quindi scrivi la metà non ASCII dei tuoi 256 caratteri come due byte senza una buona ragione, rendendo il tuo file circa 1,5 volte più grande di quanto dovrebbe essere.

Dovresti davvero produrre solo bytes .