Langsamer Huffman-Code in reinem Python

Question

Ich arbeitete daran, eine schnelle Implementierung einer einfachen Huffman-Code-Komprimierung von Text zu schreiben. Die Idee war, es nur mit der Standardbibliothek zu schreiben, aber ich kann anscheinend keinen Weg finden, es schneller zu machen. Ich suche auch nach Ratschlägen, wie ich es "pythonischer" schreiben kann, ohne die Geschwindigkeit zu beeinträchtigen.

Mir ist bewusst, dass ich Python nicht verwenden sollte, wenn ich Geschwindigkeit will, aber ich habe es als Übung genommen, um die reine Python-Leistung zu testen.

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

Ich begann mit Ihrem Code, fügte hinzu, sys.argvdamit ich Dateipfade auf der Befehlszeile übergeben konnte, lud eine große Textdatei herunter ( natürlich War and Peace ), führte Ihr Programm aus und überprüfte die Dateigrößen:

$ 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

Sieht so aus, als hätten Sie versehentlich einen Expansionsalgorithmus erfunden: Er erstellt eine Datei, die ungefähr 12-mal größer ist! Außerdem scheinen 11 Sekunden langsam zu sein, um magere 40 MB Text zu verarbeiten. Normalerweise kann Python Daten dieser Größe viel schneller verarbeiten.

Ich habe der Variablen vorübergehend einen kurzen String ( huffman) zugewiesen text, das Lesen der Datei umgangen und einige Ihrer Zwischenvariablen ausgedruckt. Obwohl letter_freqes gut aussah, alphabetwar es das Gegenteil von dem, was wir wollten:

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

Der Huffman-Algorithmus kombiniert die 2 Elemente mit der am wenigsten gemeinsamen Frequenz, aber Sie tun das Gegenteil. Also habe ich deinen Code wie folgt angepasst:

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

Mit dieser Änderung alphabetsieht es zumindest plausibler aus, die Ausgabedatei wird kleiner als die Eingabedatei (wenn auch nicht so viel wie ich erwartet habe, also gibt es wahrscheinlich andere Probleme in Ihrem Code), und es endet eher in etwa 1 Sekunde als 11 (höchstwahrscheinlich, weil es eine viel kleinere Ausgabedatei schreibt).

Einige Vorschläge:

• Konzentrieren Sie sich zuerst auf die Korrektheit . Machen Sie sich später Gedanken über die Geschwindigkeit – und nur, wenn es wirklich wichtig ist (und es könnte sein, wenn auch aus keinem anderen Grund als lehrreich).

• Algorithmen und Seiteneffekte passen nicht zusammen . Reorganisieren Sie Ihren Code, um das Testen und Debuggen zu erleichtern. Die huffman_compress()Funktion selbst sollte sich nicht mit dem Lesen und Schreiben von Dateien befassen. Es sollte einen Textklecks nehmen und einen Byteklecks zurückgeben, Punkt. Hochgradig algorithmischer Code (wie Huffman) sollte niemals Nebenwirkungen haben; es sollte im Reich der reinen Funktionen leben.

• Roundtrip der Daten . Schreiben Sie auch eine huffman_expand()Funktion: Bytes nehmen, Text zurückgeben. Ohne das können Sie kein Vertrauen in den Prozess haben. Insbesondere möchten Sie Folgendes können: assert original_text == huffman_expand(huffman_compress(original_text)). Das beweist nicht, dass Sie Huffman korrekt implementiert haben (vielleicht erfinden Sie Ihr eigenes spezielles Codierungsschema, das cool sein könnte), aber es beweist zumindest, dass Sie einen verlustfreien Roundtrip machen können.

Answer 2

Speichern Sie die Umwandlung in ASCII für möglichst 256 Zeichen

ASCII hat keine 256 Zeichen. Es hat 128.

Und Sie schreiben mit der Standardcodierung UTF-8, also schreiben Sie die Nicht-ASCII-Hälfte Ihrer 256 Zeichen ohne triftigen Grund als zwei Bytes, wodurch Ihre Datei etwa 1,5-mal so groß wird, wie sie sein sollte.

Sie sollten wirklich nur Bytes produzieren .