허프만 코딩 1 – 허프만 코드 구하기: 태미네이터의 이런저런 삶

허프만 코딩 1 – 허프만 코드 구하기 – 태미네이터의 이런저런 삶

허프만 코딩은 데이터 압축 알고리즘 중 하나로, 자주 사용되는 문자에 짧은 코드를, 덜 사용되는 문자에 긴 코드를 할당하여 데이터 크기를 줄이는 방식입니다. 이번 글에서는 허프만 코드를 구하는 방법에 대해 자세히 알아보겠습니다.

첫 번째 단계는 문자열을 구성하는 문자들의 빈도수를 구하는 것입니다. 예를 들어 “banana”라는 문자열을 살펴보면, “b”는 1번, “a”는 3번, “n”은 2번 등장합니다. 이 빈도수를 기반으로 각 문자에 대한 노드를 생성합니다. 각 노드는 문자와 해당 문자의 빈도수를 가지고 있습니다.

두 번째 단계는 부모 노드가 없는 노드들 중 빈도수가 가장 낮은 두 개의 노드를 선택하여 새로운 부모 노드를 만드는 것입니다. 새로운 부모 노드의 빈도수는 두 자식 노드의 빈도수 합계가 됩니다.

세 번째 단계는 부모 노드가 없는 노드들 중 빈도수가 가장 낮은 두 개의 노드를 다시 선택하여 새로운 부모 노드를 만드는 것입니다. 이 과정을 반복하면서 최종적으로 하나의 루트 노드만 남을 때까지 진행합니다.

마지막 단계는 루트 노드에서 각 잎 노드까지의 경로를 따라 내려가면서 0과 1로 이루어진 코드를 할당하는 것입니다. 왼쪽으로 이동할 때마다 “0”을, 오른쪽으로 이동할 때마다 “1”을 할당하면 각 문자에 대한 허프만 코드를 얻을 수 있습니다.

예를 들어, “banana” 문자열의 허프만 코드를 구해보면 다음과 같습니다.

* “b” : 100
* “a” : 0
* “n” : 11

이렇게 구해진 허프만 코드를 사용하여 문자열을 압축하면 원래 문자열보다 더 작은 크기로 저장할 수 있습니다.

허프만 코딩의 장점은 다음과 같습니다.

높은 압축률: 자주 사용되는 문자에 짧은 코드를 할당하여 압축률을 높입니다.
적응력: 데이터의 빈도수 변화에 따라 코드를 재구성할 수 있어 다양한 데이터에 적용 가능합니다.

허프만 코딩의 단점은 다음과 같습니다.

복잡한 알고리즘: 코드를 구하는 과정이 다소 복잡할 수 있습니다.
큰 파일의 경우 효율성 저하: 파일 크기가 매우 큰 경우 코드 구축에 시간이 오래 걸릴 수 있습니다.

허프만 코딩은 데이터 압축 기술 중 하나로, 데이터의 빈도수 분포를 기반으로 효율적인 압축을 제공합니다. 다양한 분야에서 데이터 압축 및 전송에 활용되고 있으며, 특히 텍스트 데이터의 압축에 효과적입니다.