Code Huffman lent en Python pur

Question

Je travaillais sur l'écriture d'une implémentation rapide d'une simple compression de texte par code Huffman. L'idée était de l'écrire en utilisant uniquement la bibliothèque standard, mais je n'arrive pas à trouver un moyen de le rendre plus rapide. Je cherche également des conseils pour l'écrire plus "Pythonic", sans sacrifier la vitesse.

Je suis conscient que si je veux de la vitesse, je ne devrais pas utiliser Python, mais je l'ai pris comme un exercice pour tester les performances pures de Python.

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

J'ai commencé avec votre code, ajouté sys.argvpour pouvoir transmettre des chemins de fichiers sur la ligne de commande, téléchargé un gros fichier texte ( War and Peace , bien sûr), exécuté votre programme et vérifié la taille des fichiers :

$ 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

Il semble que vous ayez inventé par inadvertance un algorithme d'expansion : il crée un fichier environ 12 fois plus gros ! De plus, 11 secondes semblent lentes pour traiter un maigre 40M de texte. Normalement, Python peut traiter des données de cette taille beaucoup plus rapidement.

J'ai temporairement assigné une chaîne courte ( huffman) à la textvariable, en contournant la lecture de fichier, et j'ai imprimé certaines de vos variables intermédiaires. Bien qu'il ait letter_freql'air bien, alphabetc'était le contraire de ce que nous voulons :

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

L'algorithme de Huffman combine les 2 éléments avec la fréquence la moins commune , mais vous faites le contraire. J'ai donc peaufiné votre code comme ceci:

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

Avec ce changement, alphabetau moins semble plus plausible, le fichier de sortie finit par être plus petit que le fichier d'entrée (mais pas autant que je m'y attendais, il y a donc probablement d'autres problèmes dans votre code), et il se termine en environ 1 seconde plutôt supérieur à 11 (probablement parce qu'il écrit un fichier de sortie beaucoup plus petit).

Quelques suggestions:

• Concentrez-vous d'abord sur l'exactitude . Inquiétez-vous de la vitesse plus tard - et seulement si cela compte vraiment (et cela pourrait, si ce n'est pour une autre raison qu'éducative).

• Algorithmes et effets secondaires ne font pas bon ménage . Réorganisez votre code pour faciliter les tests et le débogage. La huffman_compress()fonction elle-même ne doit pas se préoccuper de la lecture et de l'écriture de fichiers. Il devrait prendre un blob de texte et renvoyer un blob d'octets, point final. Un code hautement algorithmique (comme l'est Huffman) ne devrait jamais avoir d'effets secondaires ; il devrait vivre dans le domaine des fonctions pures.

• Aller-retour des données . Écrivez également une huffman_expand()fonction : prend des octets, renvoie du texte. Sans cela, vous ne pouvez pas avoir confiance dans le processus. En particulier, vous souhaitez pouvoir effectuer les opérations suivantes : assert original_text == huffman_expand(huffman_compress(original_text)). Cela ne prouve pas que vous avez correctement implémenté Huffman (vous allez peut-être inventer votre propre schéma d'encodage spécial, ce qui pourrait être cool), mais au moins cela prouvera que vous pouvez faire un aller-retour sans perte.

Answer 2

Enregistrez la transformation en ascii pour les 256 caractères possibles

ASCII n'a pas 256 caractères. Il en a 128.

Et vous écrivez avec l'encodage par défaut, qui est UTF-8, donc vous écrivez la moitié non ASCII de vos 256 caractères sur deux octets sans aucune raison valable, ce qui rend votre fichier environ 1,5 fois plus volumineux qu'il ne devrait l'être.

Vous devriez vraiment juste produire bytes .