[알고리즘] 허프만 압축 알고리즘 (Huffman Coding Algorithm)

📹 YouTube - 허프만 압축 알고리즘 강좌 (Huffman Coding Algorithm Tutorial)

 

허프만 압축 알고리즘 (Huffman Coding Algorithm)은 문자열을 문자 단위로 쪼개 빈도수를 세어 ㉮ 빈도가 높은 정보는 적은 비트 수를 사용하여 표현하고, ㉯ 빈도가 낮은 정보는 비트 수를 많이 사용하여 표현해서 전체 데이터의 표현에 필요한 비트의 양을 줄이는 원리의 알고리즘입니다.

 

Huffman Coding ❘ Greedy Algo-3 (https://www.geeksforgeeks.org/huffman-coding-greedy-algo-3)

 

허프만 압축 알고리즘의 원리는 아래와 같습니다.

 

1. 문자열을 문자 단위로 빈도수에 따라 모두 나열합니다.
2. 단 한가지의 문자가 남을 때까지 아래의 작업을 반복합니다.
   • 나열 된 문자들로부터 가장 빈도가 낮은 것을 2가지 선택합니다.
   • 두 문자의 빈도수의 합을 부모 노드로 지정하고 문자를 자식 노드로 생성합니다.
   • 선택 된 두 노드를 트리에서 제거하고, 새로운 부모 노드를 트리에 추가합니다.

 

허프만 압축 알고리즘은 이미지, 음악, 파일 압축 및 통신 등에서 사용하여 데이터 효율성을 높이는데 자주 사용되고 있습니다.

---

🚀 REFERENCE

허프만 알고리즘

허프먼 부호화 - 위키백과, 우리 모두의 백과사전

Huffman Coding | Greedy Algo-3 - GeeksforGeeks

탐욕 알고리즘과 허프만 코딩 구현 방법 | 요즘IT