Saf Python'da Yavaş Huffman Kodu

Question

Metnin basit bir Huffman kodu sıkıştırmasının hızlı bir uygulamasını yazmak için çalışıyordum. Fikir, onu yalnızca standart kitaplığı kullanarak yazmaktı, ancak daha hızlı hale getirmenin bir yolunu bulamıyorum. Ayrıca hızdan ödün vermeden onu nasıl daha fazla "Pythonic" yazacağıma dair tavsiyeler de arıyorum.

Hız istiyorsam Python kullanmamam gerektiğinin farkındayım, ancak bunu saf Python performansını test etmek için bir egzersiz olarak aldım.

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

Kodunuzla başladım, ekledim, sys.argvböylece komut satırındaki dosya yollarını geçebilirim, büyük bir metin dosyası indirdim (tabii ki Savaş ve Barış ), programınızı çalıştırdım ve dosya boyutlarını kontrol ettim:

$ 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

Görünüşe göre yanlışlıkla bir genişletme algoritması icat etmişsiniz: kabaca 12 kat daha büyük bir dosya oluşturur! Ayrıca 11 saniye, yetersiz 40M'lik bir metni işlemek için yavaş görünüyor. Normalde Python bu büyüklükteki verileri çok daha hızlı sıkıştırabilir.

Değişkene geçici olarak kısa bir dize ( huffman) textatadım, dosya okumayı atladım ve bazı ara değişkenlerinizi yazdırdım. İyi letter_freqgörünmesine rağmen alphabet, istediğimizin tam tersi oldu:

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

Huffman algoritması, 2 öğeyi en az yaygın frekansla birleştiriyor, ancak siz tam tersini yapıyorsunuz. Bu yüzden kodunuzu şu şekilde değiştirdim:

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

Bu değişiklikle, alphabeten azından daha makul görünüyor, çıktı dosyası giriş dosyasından daha küçük hale geliyor (beklediğim kadar olmasa da, muhtemelen kodunuzda başka sorunlar var) ve yaklaşık 1 saniye içinde bitiyor 11'den (büyük olasılıkla çok daha küçük bir çıktı dosyası yazdığı için).

Bazı öneriler:

• Önce doğruluğa odaklanın . Daha sonra hız hakkında endişelenmek - ve yalnızca gerçekten önemliyse (ve eğitici başka bir neden yoksa olabilir).

• Algoritmalar ve yan etkiler birbirine karışmaz . Test ve hata ayıklamayı kolaylaştırmak için kodunuzu yeniden düzenleyin. huffman_compress()Fonksiyon kendisi dosya okuma ve yazma ile kendisini ilgilendiren olmamalıdır. Bir metin bloğu almalı ve bir bayt bloğu, nokta döndürmelidir. Yüksek algoritmik kodun (Huffman olduğu gibi) hiçbir zaman yan etkileri olmamalıdır; saf işlevler aleminde yaşamalıdır.

• Verileri gidiş geliş . Ayrıca bir huffman_expand()işlev yazın: bayt al, metni döndür. Bu olmadan sürece güvenemezsiniz. Özellikle, aşağıdakileri yapmanız mümkün istiyorum: assert original_text == huffman_expand(huffman_compress(original_text)). Bu, Huffman'ı doğru bir şekilde uyguladığınızı kanıtlamaz (belki de kendi özel kodlama şemanızı icat edeceksiniz, bu harika olabilir), ancak en azından kayıpsız bir gidiş dönüş yapabileceğinizi kanıtlayacaktır.

Answer 2

Olası 256 karakter için dönüşümü ascii'ye kaydedin

ASCII, 256 karaktere sahip değildir. 128 tane var.

Ve varsayılan kodlama olan UTF-8 ile yazarsınız, böylece 256 karakterinizin ASCII olmayan yarısını iki bayt olarak hiçbir iyi sebep olmadan yazarsınız ve dosyanızı olması gerekenden 1,5 kat daha büyük hale getirirsiniz .

Gerçekten sadece bayt üretmelisiniz .