Kode Huffman Lambat dengan Python murni

Question

Saya sedang menulis implementasi cepat dari kompresi teks kode Huffman sederhana. Idenya adalah menulisnya hanya dengan menggunakan pustaka standar, tetapi sepertinya saya tidak dapat menemukan cara untuk membuatnya lebih cepat. Saya juga mencari nasihat tentang bagaimana menulisnya lebih "Pythonic", tanpa mengorbankan kecepatan.

Saya sadar bahwa jika saya menginginkan kecepatan, saya tidak boleh menggunakan Python, tetapi saya telah menganggapnya sebagai latihan untuk menguji performa Python murni.

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

Saya mulai dengan kode Anda, ditambahkan sys.argvsehingga saya bisa melewati jalur file pada baris perintah, mengunduh file teks besar ( War and Peace , tentu saja), menjalankan program Anda, dan memeriksa ukuran 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

Sepertinya Anda secara tidak sengaja menemukan algoritme perluasan: ini membuat file kira-kira 12x lebih besar! Selain itu, 11 detik tampaknya lambat untuk memproses teks yang hanya berjumlah 40 juta. Biasanya Python dapat mengolah data sebesar itu dengan lebih cepat.

Saya untuk sementara menetapkan string pendek ( huffman) ke textvariabel, melewati pembacaan file, dan mencetak beberapa variabel perantara Anda. Meski letter_freqterlihat baik-baik saja, alphabetternyata kebalikan dari apa yang kita inginkan:

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

Algoritme Huffman menggabungkan 2 elemen dengan frekuensi yang paling tidak umum , tetapi Anda melakukan yang sebaliknya. Jadi saya mengubah kode Anda seperti ini:

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

Dengan perubahan itu, alphabetsetidaknya terlihat lebih masuk akal, file output akhirnya menjadi lebih kecil dari file input (meskipun tidak sebanyak yang saya harapkan, jadi mungkin ada masalah lain dalam kode Anda), dan selesai dalam waktu sekitar 1 detik. dari 11 (kemungkinan besar karena itu menulis file output yang jauh lebih kecil).

Beberapa saran:

• Fokus pada kebenaran dulu . Khawatir tentang kecepatan nanti - dan hanya jika itu benar-benar penting (dan mungkin, jika tidak ada alasan lain yang mendidik).

• Algoritma dan efek samping tidak bercampur . Atur ulang kode Anda untuk memfasilitasi pengujian dan debugging. The huffman_compress()fungsi itu sendiri tidak harus perhatian itu sendiri dengan berkas membaca dan menulis. Ini harus mengambil sekumpulan teks dan mengembalikan sekumpulan byte, titik. Kode yang sangat algoritmik (seperti Huffman) seharusnya tidak memiliki efek samping; ia harus hidup dalam dunia fungsi murni.

• Lakukan bolak-balik data . Juga tulis sebuah huffman_expand()fungsi: take bytes, return text. Tanpa itu, Anda tidak dapat memiliki keyakinan dalam prosesnya. Secara khusus, Anda ingin dapat melakukan hal berikut: assert original_text == huffman_expand(huffman_compress(original_text)). Itu tidak membuktikan bahwa Anda telah menerapkan Huffman dengan benar (mungkin Anda akan menemukan skema pengkodean khusus Anda sendiri, yang mungkin keren), tetapi setidaknya itu akan membuktikan bahwa Anda dapat membuat perjalanan pulang pergi tanpa kerugian.

Answer 2

Simpan transformasi ke ascii untuk kemungkinan 256 karakter

ASCII tidak memiliki 256 karakter. Ini memiliki 128.

Dan Anda menulis dengan pengkodean default, yaitu UTF-8, jadi Anda menulis setengah non-ASCII dari 256 karakter Anda sebagai dua byte tanpa alasan yang jelas, membuat file Anda sekitar 1,5 kali lebih besar dari yang seharusnya.

Anda seharusnya hanya menghasilkan byte .