'허프만'에 해당되는 글 1건

  1. 2009.08.12 허프만 알고리즘 (5)
2009. 8. 12. 10:22

허프만 알고리즘

오늘은 무손실 압축의 대표적인 알고리즘인 허프만 알고리즘에 대해서 알아보겠습니다.

허프만 부호화, 허프만 압축, 허프만 알고리즘등으로 불리우는 이 알고리즘은 문자들의 빈도수에 따라 서로 다른 길이의 부호를 부여하여 압축하는 방식으로, 1952년 당시 박사과정 학생이던 데이비드 허프만이 A Method for the Construction of Minimum-Redundancy Codes란 제목의 논문으로 처음 발표했습니다.

허프만 알고리즘은 JPEG이나 MPEG 같은 영상처리에서 많이 사용되고 있으며 우리가 많이 쓰는 알집 역시 허프만 알고리즘으로 한번 압축을 한 다음에 Lempel 이라는 알고리즘으로 압축을 합니다.

허프만 알고리즘은 그렇게 어렵지 않은 알고리즘이면서도 꽤 괜찮은 압축율을 보입니다.

이번 포스팅에서는 허프만 알고리즘의 원리와 절차에 대해서 알아보고 다음 포스팅 쯤에서 실제로 구현해보도록 하겠습니다.



=======================================================================================================

허프만 부호화로 위키에서 검색을 해보면 간략한 설명과 함께 아래와 같은 간략한 절차가 나와있습니다.

  1. 초기화 : 모든 기호를 출현 빈도수에 따라 나열한다.
  2. 단 한 가지 기호가 남을 때까지 아래 단계를 반복한다.
    1. 목록으로부터 가장 빈도가 낮은 것을 2개 고른다.
    2. 그 다음 허프만이 두가지 기호를 부모 노드를 가지는 부트리를 구성하고 자식노드를 생성한다. 부모 노드 단 기호들의 빈도수를 더하여 주 노드에 할당하고 목록의 순서에 맞도록 목록에 삽입한다.
    3. 목록에서 부모노드에 포함된 기호를 제거한다.

문서를 허프만 알고리즘으로 압축하기 위해서는 먼저 문서안에 포함된 문자들의 빈도수를 조사하여 정렬하는 절차가 필요합니다.

만약 다음과 같은 데이터가 있다고 한다면 다음과 같은 빈도수를 줄 수 있습니다.

데이터: ACABFEAFDE

데이터
빈도수
등장확률(가중치)
A
3
0.3
B
1
0.1
C
1
0.1
D
1
0.1
E
2
0.2
F
2
0.2



위의 결과를 빈도수에 따라 오름차순으로 정렬을 합니다.




이제 이 값들을 이용하여 이진트리를 생성합니다.

먼저 가장 작은 빈도수의 값을 두개 선택해서 리프노드를 두개 만들고 두 노드의 가중치를 더해서 부모노드를 만듭니다. 그리고 정렬된 리스트에서 선택된 두개의 노드를 삭제하고 부모노드를 추가 시킵니다.

 




위의 과정을 리스트에 노드가 1.0 하나만 남을 때까지 반복합니다. (모든 빈도수 확률을 더하면 1.0이 되기 때문에)

=============================================================



=============================================================



=============================================================



=============================================================



=============================================================


이렇게 완성된 이진트리를 루트노드부터 왼쪽은 0, 오른쪽은 1을 부가해줍니다.


이렇게 완성된 허프만 트리를 가지고 각 문자에 대한 비트를 부가합니다.
A의 경우는 루트노드에서 왼쪽으로 한번 갔다가 다시 한번 왼쪽으로 갔기때문에 00 이 됩니다.
마찬가리로 B는 0110이 되겠지요.

이것을 정리하면 아래의 표와 같습니다.


데이터
치환될 비트
A
00
B
0110
C
0111
D
010
E
10
F
11


이 표를 보고 눈치채신 분도 있으실텐데 허프만 알고리즘의 핵심은 바로 이 표에 있습니다.

가장 많은 빈도수의 데이터는 적은 비트, 상대적으로 적은 빈도수의 데이터들은 더 긴 비트를 서로 접두어가 겹치지 않도록 부가하여 압축하는 것입니다.

즉, 비트의 앞에서부터 순서대로 탐색했을 때 유일의 리프노드로 갈 수 있도록 비트의 등장 순서를 유일하도록 해주는 것입니다.(말이 어려운가;;; 압축을 풀 때 트리를 탐색해보시면 이해하실 수 있을 겁니다=ㅅ=)

그런데 위의 경우는 같은 빈도수의 노드들이 몇개 있기 때문에 다른 모양의 트리로 만들어질 수도 있습니다. 같은 노드가 존재할 때 어떤 순서로 트리에 추가하느냐나 트리의 왼쪽, 오른쪽 어느쪽에 붙이느냐에 따라 조금 달라질 수도 있습니다. 하지만 결과적으로 부가되는 비트의 개수는 같기때문에 압축율은 같습니다.



이제 처음에 압축하려고 했던 데이터를 압축하면 다음과 같아질 것입니다.

데이터: ACABFEAFDE

압축된 데이터: 0001110001101110001101010

처음의 데이터는 10글자이므로 10바이트 = 80비트 입니다. 압축된 데이터는 25글자이지만 비트데이터이므로 25비트 입니다. 25 / 80 * 100 = 31.25% 의 압축율을 보이는 군요.

물론 위의 예는 텍스트 문서일 때이고, 다른 종류의 파일이라면 약간 달라질 수 도 있습니다. 실제로는 트리정보에 대한 헤더도 추가해야되고 하니 조금 더 늘어나겠지만, 그래도 꽤 괜찮은 압축율을 보입니다.




압축을 해제하는 것은 아주 쉽습니다.
비트데이터를 허프만 트리에 넣고 루트노드부터 탐색해서 리프노드가 나오면 치환해주고, 다시 루트부터 탐색하는 식으로 데이터를 끝까지 읽으면 됩니다. 디코딩 과정은 생략하도록 하겠습니다.

'공부합시다 > 데이터 압축' 카테고리의 다른 글

허프만 알고리즘  (5) 2009.08.12
데이터 압축이란?  (0) 2009.08.05
Trackback 0 Comment 5
  1. sujkim2201 2011.01.01 22:35 address edit & del reply

    정말 감사해요 !! 이걸로 연구계획서 쓰기로 했는데 유용하게 쓰겠습니다 ^^ 감사해용 ^^

  2. ㅎㅇㄷㄷ 2012.10.02 20:26 address edit & del reply

    감사합니다 ㅎㅎ 퍼갈게용

  3. 박재범 2014.03.12 01:27 address edit & del reply

    블로그 잘 읽어보았습니다! 정말 쉽게 잘 알려주셧는데, 잠시 헷갈리는 점이 있어 이렇게 물어봅니다!, 위에 허프만 트리 만드실때 확률로 나타내셔서 결국엔 합이 1. 이라고 하셧는데, 책에서 보기엔 보통 샤넌코드에서 보통 확률의 합으로 나타내구, 허프만은 그냥 나타나는 빈도수의 합이던데, 뭐 굳이 큰차이는 아니겠으나, 둘다 맞는 것인지요? 그리고 샤넌 코드와 허프만코드의 차이점을 아직 잘 모르겠습니다. 좀 간단하게라도 설명해주실수있으신지요??

  4. Favicon of http://kjuns1.blog.me BlogIcon kjuns1 2014.07.14 15:48 address edit & del reply

    감사합니다 !
    이해했어요! 이거 블로그 담아갈게요 ^^

  5. 피즈피즈 2014.07.21 16:57 address edit & del reply

    마지막에 0.4와 0.6만 남은 경우에 작은 확률이 왼쪽으로 가야하는것 아닌가요??