Slow Huffman Code w czystym Pythonie

Question

Pracowałem nad napisaniem szybkiej implementacji prostej kompresji kodu Huffmana tekstu. Pomysł polegał na napisaniu go przy użyciu tylko standardowej biblioteki, ale nie mogę znaleźć sposobu, aby to przyspieszyć. Szukam też rady jak napisać to bardziej "Pythonic", bez poświęcania szybkości.

Zdaję sobie sprawę, że jeśli chcę szybkości, nie powinienem używać Pythona, ale potraktowałem to jako ćwiczenie do testowania wydajności czystego Pythona.

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

Zacząłem od twojego kodu, dodałem sys.argv, żebym mógł przekazać ścieżki do plików w wierszu poleceń, pobrać duży plik tekstowy ( oczywiście War and Peace ), uruchomiłem program i sprawdziłem rozmiary plików:

$ 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

Wygląda na to, że przypadkowo wymyśliłeś algorytm rozszerzania: tworzy on plik około 12 razy większy! Ponadto 11 sekund wydaje się powolne, aby przetworzyć skromne 40 MB tekstu. Zwykle Python może znacznie szybciej przetwarzać dane o takim rozmiarze.

Tymczasowo przypisałem huffmando textzmiennej krótki ciąg ( ) , pomijając odczyt plików i wydrukowałem niektóre z twoich zmiennych pośrednich. Chociaż letter_freqwyglądał dobrze, alphabetbył przeciwieństwem tego, czego chcieliśmy:

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

Algorytm Huffmana łączy 2 elementy z najmniejszą częstością, ale robisz odwrotnie. Więc poprawiłem twój kod w ten sposób:

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

Z tą zmianą, alphabetprzynajmniej wygląda bardziej wiarygodnie, plik wyjściowy jest mniejszy niż plik wejściowy (chociaż nie tak bardzo, jak się spodziewam, więc prawdopodobnie są inne problemy w twoim kodzie) i kończy się raczej za około 1 sekundę niż 11 (najprawdopodobniej dlatego, że zapisuje znacznie mniejszy plik wyjściowy).

Jakieś sugestie:

• Najpierw skup się na poprawności . Martw się o prędkość później - i tylko wtedy, gdy naprawdę ma to znaczenie (i może, jeśli nie ma innego powodu do edukacji).

• Algorytmy i efekty uboczne nie mieszają się . Zreorganizuj swój kod, aby ułatwić testowanie i debugowanie. Sama huffman_compress()funkcja nie powinna zajmować się odczytywaniem i zapisywaniem plików. Powinien zająć fragment tekstu i zwrócić blob bajtów, kropka. Wysoce algorytmiczny kod (jak Huffman) nigdy nie powinien mieć skutków ubocznych; powinien żyć w sferze czystych funkcji.

• Przejrzyj dane . Napisz także huffman_expand()funkcję: weź bajty, zwróć tekst. Bez tego nie możesz mieć zaufania do tego procesu. W szczególności, chcesz być w stanie wykonać następujące czynności: assert original_text == huffman_expand(huffman_compress(original_text)). To nie dowodzi, że poprawnie zaimplementowałeś Huffmana (być może wymyślisz własny specjalny schemat kodowania, który może być fajny), ale przynajmniej udowodni, że możesz wykonać bezstratną podróż w obie strony.

Answer 2

Zapisz transformację do ascii dla możliwych 256 znaków

ASCII nie ma 256 znaków. Ma 128.

Piszesz z domyślnym kodowaniem, którym jest UTF-8, więc zapisujesz połowę swoich 256 znaków innych niż ASCII jako dwa bajty bez żadnego powodu, dzięki czemu plik jest około 1,5 razy większy niż powinien.

Naprawdę powinieneś po prostu produkować bajty .