3.6 Greedy Algorithms - 3.6.1 Huffman Coding

CS - 3. Common Algorithms - 3.6 Greedy Algorithms - 3.6.1 Huffman Coding 

Huffman Coding

💡Huffman coding is a lossless data compression algorithm. The idea is to assign variable-length codes to input characters, lengths of the assigned codes are based on the frequencies of corresponding characters. The most frequent character gets the smallest code and the least frequent character gets the largest code.

허프만 코딩은 무손실 데이터 압축 알고리즘입니다. 입력 문자에 가변 길이의 코드를 할당하고, 할당된 코드의 길이는 해당 문자의 빈도에 따라 달라집니다. 가장 빈도가 높은 문자는 가장 작은 코드를, 가장 빈도가 낮은 문자는 가장 큰 코드를 할당받습니다.

 

허프만 코딩(Huffman Coding)은 데이터를 효율적으로 압축하는 알고리즘 중 하나입니다.

이 방법은 문자 또는 심볼이 얼마나 자주 등장하는지에 따라 다른 길이의 비트를 사용합니다.

가장 자주 등장하는 문자는 가장 짧은 비트를, 가장 적게 등장하는 문자는 가장 긴 비트를 사용합니다.

이렇게 하면 데이터를 표현하는 데 필요한 전체 비트 수를 최소화 할 수 있습니다.

 

 

import heapq
import collections
import sys

def huffman_encoding(data):
    # 문자의 빈도수를 세어서 사전에 저장합니다.
    freq_dict = collections.defaultdict(int)
    for char in data:
        freq_dict[char] += 1

    # 빈도수를 기반으로 최소 힙을 만듭니다. 
    # 힙의 각 요소는 [문자 빈도수, [문자, 문자의 허프만 코드]] 형태입니다.
    heap = [[weight, [char, ""]] for char, weight in freq_dict.items()]
    heapq.heapify(heap)

    # 힙에 요소가 하나만 남을 때까지 아래의 과정을 반복합니다.
    while len(heap) > 1:
        # 힙에서 가장 빈도수가 적은 두 요소를 꺼냅니다.
        lo = heapq.heappop(heap)
        hi = heapq.heappop(heap)

        # 빈도수가 가장 적은 요소의 허프만 코드 앞에 '0'을 추가합니다.
        for pair in lo[1:]:
            pair[1] = '0' + pair[1]
        # 두 번째로 빈도수가 적은 요소의 허프만 코드 앞에 '1'을 추가합니다.
        for pair in hi[1:]:
            pair[1] = '1' + pair[1]

        # 두 요소를 합친 새 요소를 힙에 추가합니다.
        # 이 요소의 빈도수는 두 요소의 빈도수 합이며, 허프만 코드는 두 요소의 허프만 코드를 합친 것입니다.
        heapq.heappush(heap, [lo[0] + hi[0]] + lo[1:] + hi[1:])

    # 힙에 남은 마지막 요소가 전체 문자의 허프만 트리입니다. 
    # 이를 허프만 사전으로 변환하여 출력합니다.
    huff_dict = sorted(heapq.heappop(heap)[1:], key=lambda p: (len(p[-1]), p))
    print("Huffman Coding: ")
    for char, huff_code in huff_dict:
        print(f"{char} : {huff_code}")

 

위 코드는 사용자로부터 문자열을 입력받아 각 문자의 빈도수를 계산하고,

이를 기반으로 허프만 코딩 알고리즘을 적용해 각 문자에 대응하는 허프만 코드를 출력합니다.

 

이런식으로 문자열에서 각 문자의 빈도수를 카운트하고, 빈도수를 기반으로 허프만 트리를 구성합니다.

트리를 통해 각 문자에 대응하는 허프만 코드를 생성하고 출력합니다. 이렇게 생성된 허프만 코드는 그 문자의 빈도수에 반비례하는 길이를 가지므로, 빈도수가 높은 문자는 짧은 코드를, 빈도수가 낮은 문자는 긴 코드를 가지게 됩니다.

 

활용

정의에 따라서 '압축'에 강점을 지니기에 압축과 전송에 있어 큰 효율성을 지닙니다.

 

1. 파일 압축

허프만 코딩은 파일 압축에 많이 사용됩니다.

ZIP파일 압축은 허프만 코딩을 이용해 데이터를 효율적으로 압축합니다.

JPEG 이미지 압축에서도 허프만 코딩이 사용됩니다.

이미지 색상 정보를 압축하는 과정에서 허프만 코딩을 사용하여 데이터를 효율적으로 압축합니다.

 

2. 통신

허프만 코딩은 데이터를 효율적으로 전송하는 방법에 사용됩니다.

데이터 전송에 필요한 비트수를 줄여 최소화하는데 사용됩니다.

 

3. 웹 로딩

텍스트 데이터도 허프만 코딩을 통해 압축을 할수 있으며, 웹 페이지 로딩 속도를 높이는데 도움이 됩니다.