순수 Python의 느린 Huffman 코드

Aug 22 2020

저는 텍스트의 간단한 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)))

답변

8 FMc Aug 25 2020 at 05:08

코드로 시작 sys.argv하여 명령 줄에서 파일 경로를 전달하고 큰 텍스트 파일 ( 물론 War and Peace )을 다운로드하고 프로그램을 실행하고 파일 크기를 확인할 수 있도록 추가했습니다.

$ 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 배 더 큰 파일을 생성합니다! 또한 4 천만 개의 텍스트를 처리하는 데 11 초가 느려 보입니다. 일반적으로 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 알고리즘은 최소 공통 주파수를 가진 두 요소를 결합 하지만, 그 반대입니다. 그래서 다음과 같이 코드를 수정했습니다.

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

이 변경 alphabet으로 적어도 그럴듯 해 보이며 출력 파일은 입력 파일보다 작아지고 (예상 만큼은 아니므로 코드에 다른 문제가있을 수 있음) 약 1 초만에 완료됩니다. 11보다 (훨씬 더 작은 출력 파일을 작성하기 때문에)

몇 가지 제안 :

먼저 정확성에 중점을 둡니다 . 나중에 속도에 대해 걱정하세요. 진정으로 중요한 경우에만 (다른 이유없이 교육적인 경우) 가능합니다.
알고리즘과 부작용은 섞이지 않습니다 . 테스트 및 디버깅을 용이하게하기 위해 코드를 재구성합니다. huffman_compress()기능 자체가 파일 읽기와 쓰기 자체를 고려한다. 텍스트 한 덩어리를 가져 와서 바이트 한 덩어리, 기간을 반환해야합니다. 고도의 알고리즘 코드 (허프만처럼)는 부작용이 없어야합니다. 순수한 기능의 영역에 있어야합니다.
데이터를 왕복합니다 . 또한 huffman_expand()함수를 작성하십시오 : 바이트를 취하고 텍스트를 리턴하십시오. 그것 없이는 그 과정에 대해 어떤 확신도 가질 수 없습니다. 특히 다음을 수행 할 수 있습니다 assert original_text == huffman_expand(huffman_compress(original_text)).. 그렇다고 허프만 (Huffman)을 올바르게 구현했음을 증명하지는 못하지만 (아마도 자신 만의 특별한 인코딩 체계를 개발할 것입니다. 멋질 수 있습니다) 적어도 무손실 왕복을 할 수 있다는 것을 증명할 것입니다.

2 superbrain Aug 25 2020 at 14:49

가능한 256 문자를 위해 변환을 ascii로 저장하십시오.

ASCII에는 256자가 없습니다. 128 개가 있습니다.

그리고 기본 인코딩 인 UTF-8로 작성하므로 별다른 이유없이 256 자의 비 ASCII 절반을 2 바이트로 작성하여 파일 크기를 약 1.5 배로 만듭니다.