Mã Huffman chậm bằng Python thuần túy

Question

Tôi đang làm việc để viết triển khai nhanh cách nén văn bản bằng mã Huffman đơn giản. Ý tưởng là chỉ viết nó bằng thư viện tiêu chuẩn, nhưng tôi dường như không thể tìm ra cách để làm cho nó nhanh hơn. Tôi cũng đang tìm lời khuyên về cách viết nó "Pythonic" hơn, mà không làm giảm tốc độ.

Tôi biết rằng nếu tôi muốn tốc độ, tôi không nên sử dụng Python, nhưng tôi đã coi nó như một bài tập để kiểm tra hiệu suất Python thuần túy.

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

Tôi bắt đầu với mã của bạn, đã thêm vào sys.argvđể tôi có thể chuyển đường dẫn tệp trên dòng lệnh, tải xuống tệp văn bản lớn (tất nhiên là Chiến tranh và Hòa bình ), chạy chương trình của bạn và kiểm tra kích thước tệp:

$ 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

Có vẻ như bạn đã vô tình phát minh ra một thuật toán mở rộng: nó tạo ra một tệp lớn hơn khoảng 12 lần! Ngoài ra, 11 giây có vẻ chậm để xử lý 40 triệu văn bản ít ỏi. Thông thường Python có thể xử lý dữ liệu có kích thước đó nhanh hơn nhiều.

Tôi đã tạm thời gán một chuỗi ngắn ( huffman) cho textbiến, bỏ qua việc đọc tệp và in ra một số biến trung gian của bạn. Mặc dù letter_freqtrông ổn, nhưng alphabetđiều ngược lại với những gì chúng tôi muốn:

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

Thuật toán Huffman kết hợp 2 yếu tố có tần suất ít phổ biến nhất , nhưng bạn đang làm ngược lại. Vì vậy, tôi đã chỉnh sửa mã của bạn như thế này:

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

Với thay đổi đó, alphabetít nhất là trông hợp lý hơn, tệp đầu ra cuối cùng nhỏ hơn tệp đầu vào (mặc dù không nhiều như tôi mong đợi, vì vậy có thể có các vấn đề khác trong mã của bạn) và nó kết thúc sau khoảng 1 giây thì đúng hơn. hơn 11 (rất có thể vì nó đang ghi một tệp đầu ra nhỏ hơn nhiều).

Một số gợi ý:

• Tập trung vào tính đúng đắn trước tiên . Lo lắng về tốc độ sau này - và chỉ khi nó thực sự quan trọng (và nó có thể, nếu không vì lý do gì khác mà giáo dục).

• Thuật toán và tác dụng phụ không trộn lẫn . Tổ chức lại mã của bạn để tạo điều kiện cho việc kiểm tra và gỡ lỗi. Bản huffman_compress()thân hàm không nên quan tâm đến việc đọc và ghi tệp. Nó sẽ mất một đốm văn bản và trả về một đốm màu byte, dấu chấm. Mã thuật toán cao (như Huffman) không bao giờ có tác dụng phụ; nó nên sống trong lĩnh vực của các chức năng thuần túy.

• Làm tròn dữ liệu . Đồng thời viết một huffman_expand()hàm: lấy byte, trả về văn bản. Nếu không có điều đó, bạn không thể có bất kỳ sự tự tin nào trong quá trình này. Đặc biệt, bạn muốn để có thể làm những điều sau đây: assert original_text == huffman_expand(huffman_compress(original_text)). Điều đó không chứng minh rằng bạn đã triển khai chính xác Huffman (có lẽ bạn sẽ phát minh ra lược đồ mã hóa đặc biệt của riêng mình, điều này có thể tuyệt vời), nhưng ít nhất nó sẽ chứng minh rằng bạn có thể thực hiện một chuyến đi vòng không mất dữ liệu.

Answer 2

Lưu chuyển đổi thành ascii để có thể có 256 ký tự

ASCII không có 256 ký tự. Nó có 128.

Và bạn viết bằng mã hóa mặc định, là UTF-8, vì vậy bạn viết một nửa không phải ASCII của 256 ký tự dưới dạng hai byte mà không có lý do chính đáng nào, làm cho tệp của bạn lớn gấp khoảng 1,5 lần so với bình thường.

Bạn thực sự chỉ nên tạo ra các byte .