รหัส Huffman ช้าใน Python แท้

Question

ฉันกำลังทำงานเกี่ยวกับการเขียนการใช้งานการบีบอัดโค้ด Huffman แบบง่ายๆอย่างรวดเร็วของข้อความ ความคิดคือการเขียนโดยใช้ไลบรารีมาตรฐานเท่านั้น แต่ดูเหมือนว่าฉันจะหาวิธีทำให้เร็วขึ้นไม่ได้ ฉันกำลังมองหาคำแนะนำเกี่ยวกับวิธีการเขียน "Pythonic" เพิ่มเติมโดยไม่ต้องลดความเร็ว

ฉันรู้ว่าถ้าฉันต้องการความเร็วฉันไม่ควรใช้ Python แต่ฉันได้ใช้มันเป็นแบบฝึกหัดเพื่อทดสอบประสิทธิภาพของ 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

ฉันเริ่มต้นด้วยรหัสของคุณเพิ่มsys.argvเพื่อให้ฉันสามารถส่งเส้นทางไฟล์ในบรรทัดคำสั่งดาวน์โหลดไฟล์ข้อความขนาดใหญ่ ( แน่นอนว่าสงครามและสันติภาพ ) รันโปรแกรมของคุณและตรวจสอบขนาดไฟล์:

$ 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

ดูเหมือนว่าคุณได้คิดค้นอัลกอริธึมการขยายโดยไม่ได้ตั้งใจมันสร้างไฟล์ที่ใหญ่ขึ้นประมาณ 12 เท่า! นอกจากนี้ 11 วินาทีดูเหมือนช้าในการประมวลผลข้อความเพียง 40 ล้านข้อความ โดยปกติ Python สามารถบีบอัดข้อมูลขนาดนั้นได้เร็วกว่ามาก

ฉันกำหนดสตริงสั้น ๆ ( huffman) ให้กับtextตัวแปรชั่วคราวโดยข้ามการอ่านไฟล์และพิมพ์ตัวแปรกลางบางตัวออกมา แม้ว่าจะletter_freqดูดี แต่alphabetก็ตรงกันข้ามกับที่เราต้องการ:

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

อัลกอริทึม Huffman รวม 2 องค์ประกอบที่มีความถี่ทั่วไปน้อยที่สุดแต่คุณกำลังทำสิ่งที่ตรงกันข้าม ดังนั้นฉันจึงปรับแต่งโค้ดของคุณดังนี้:

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

ด้วยการเปลี่ยนแปลงนั้นalphabetอย่างน้อยก็ดูเป็นไปได้มากขึ้นไฟล์เอาต์พุตจะมีขนาดเล็กกว่าไฟล์อินพุต (แม้ว่าจะไม่มากเท่าที่ฉันคาดไว้ดังนั้นอาจมีปัญหาอื่น ๆ ในโค้ดของคุณ) และจะเสร็จสิ้นในเวลาประมาณ 1 วินาที มากกว่า 11 (ส่วนใหญ่เป็นเพราะเขียนไฟล์เอาต์พุตที่เล็กกว่ามาก)

คำแนะนำบางประการ:

• มุ่งเน้นไปที่ความถูกต้องครั้งแรก กังวลเกี่ยวกับความเร็วในภายหลัง - และเฉพาะในกรณีที่มีความสำคัญอย่างแท้จริง (และอาจไม่มีเหตุผลอื่นใดที่เป็นการศึกษา)

• อัลกอริทึมและผลข้างเคียงไม่ผสมกัน จัดระเบียบรหัสของคุณใหม่เพื่ออำนวยความสะดวกในการทดสอบและแก้ไขข้อบกพร่อง huffman_compress()ฟังก์ชั่นตัวเองไม่ควรกังวลตัวเองด้วยการอ่านและการเขียนไฟล์ ควรใช้เวลาหนึ่งหยดของข้อความและส่งคืน blob ของไบต์จุด รหัสอัลกอริทึมสูง (อย่างที่ Huffman เป็น) ไม่ควรมีผลข้างเคียง มันควรอยู่ในขอบเขตของฟังก์ชันที่บริสุทธิ์

• บินข้อมูล เขียนhuffman_expand()ฟังก์ชันด้วย: ใช้ไบต์ส่งคืนข้อความ หากไม่มีสิ่งนั้นคุณจะไม่มีความมั่นใจในกระบวนการนี้ assert original_text == huffman_expand(huffman_compress(original_text))โดยเฉพาะอย่างยิ่งคุณต้องการที่จะสามารถที่จะทำต่อไปนี้: นั่นไม่ได้พิสูจน์ว่าคุณใช้ Huffman อย่างถูกต้อง (บางทีคุณอาจจะคิดค้นรูปแบบการเข้ารหัสพิเศษของคุณเองซึ่งอาจเป็นเรื่องที่น่าสนใจ) แต่อย่างน้อยก็จะพิสูจน์ได้ว่าคุณสามารถเดินทางไปกลับได้โดยไม่สูญเสีย

Answer 2

บันทึกการแปลงเป็น ascii สำหรับอักขระ 256 ตัวที่เป็นไปได้

ASCII ไม่มีอักขระ 256 ตัว มี 128

และคุณเขียนด้วยการเข้ารหัสเริ่มต้นซึ่งก็คือ UTF-8 ดังนั้นคุณจึงเขียนครึ่งหนึ่งที่ไม่ใช่ ASCII ของอักขระ 256 ตัวของคุณเป็นสองไบต์โดยไม่มีเหตุผลที่ดีใด ๆ ทำให้ไฟล์ของคุณมีขนาดใหญ่ประมาณ 1.5 เท่าที่ควรจะเป็น

คุณควรสร้างไบต์จริงๆ