🔸허프만 코딩 Huffman Coding ⭐

• 문자열 압축 시 자주 사용하는 트리 알고리즘

1. 문자의 빈도수 구하기

   

2. 빈도수를 기준으로 내림차순으로 Node 정렬

   

3. 오른쪽에서부터 빈도수를 합치고 해당 node를 child node로 내리기 합친 후 다시 내림차순으로 정렬하는 과정을 반복해준다.

   

   

   

   

4. 코드 할당

   • 왼쪽으로 내려가면 1, 오른쪽은 0을 부여

     

     

⇒ 자주 등장하는 문자일수록 더 작은 bit로 표현함으로써 효율적인 정보 전달이 가능하다.