이것 저것 공부하다가

흘러흘러가서 결국은 허프만 코드까지 공부하는 지경에 이르렀다.

전기과 출신(게다가 자퇴)에 디자이너 출신인 내 배경을 생각해보면

정말 장족의 발전이 아닐 수 없다. 허허...

아무튼 압축알고리즘의 가장 인기있는 알고리즘이 아닌가 한다.

MPEG 의 기본 압축 알고리즘으로도 쓰이고 있고

우리가 자주 사용하는 알집 역시 허프만 알고리즘으로 한번 압축한후

Lempel 이라는 간단한 압축알고리즘으로 한번 더 압축하는 프로세스라고 하니

허프만 알고리즘은 그 효율을 인정받고 있는듯 하다.



머 알고리즘이라고 해서

엄청 복잡한 줄 알았던 본인이지만

호프만 알고리즘을 보고 나서는

정말 무릎을 탁~ 치는 그런 느낌이었다.

다른 동영상 알고리즘이나 음향 알고리즘은

무슨 주파수에 양자화니 빈도수 머 어쩌구 저쩌구...

먼말인지 하나도 모르겠지만

호프만 알고리즘의 핵심은 두가지로 설명할 수 있다.



1. 이론

자주 쓰이는 문자에 가장 작은 bit 를 할당하고

한두번 쓰이는 문자에는 큰 bit 를 할당한다라는 것이다.

즉 간단하게 예를 들어서

AABBAC

라는 문자열이 있다고 예를 들어보자.

영문자 하나는 1byte 이므로 총 6byte 의 크기를 가지는 문자열이다.

자 그럼

각 문자들이 사용된 횟수를 알아보자.

머 짧으니까 한눈에 알 수 있을 것이다.

A 는 3번

B 는 2번

C 는 1번 사용되었다.

그러면 가장 많이 사용된 A 에게 0 이라는 1bit 를 부여하고

B 는 10, C 는 11 을 부여할 수 있다.

그러면 위 문자열은

A(0)A(0)B(10)B(10)A(0)C(11)

합쳐보면 001010011 로 나타낼 수 있다.

총 9 bit = 1 byte + 1 bit 으로 압축을 할 수 있다.

원래 문자열이 6 byte 즉 48 bit 를 차지하였는데 9/48 = 0.19

즉 약 20% 로 압축이 되었다. 압축률이 80% 라는 이야기다.

뭐 조금 띄엄띄엄 살펴본것 같지만 허프만 알고리즘의 핵심은 바로 이것이다.

물론 헤더도 붙고 하다보면 조금더 커지겠지만

큰 파일일 수록, 텍스트 기반일 수록, 자주 쓰이는 문자가 많을 수록 압축률은 높아지게 되어 있다.



2. 이진 트리

자 그렇다면 이론은 알겠는데

실제로는 어떻게 적용해야하는 걸까?

순서대로 한번 살펴보자.

대상 문자열 : CDDCACBCBCCCBBCDA

1. 각 문자열별로 빈도수를 검사한다.

사용자 삽입 이미지






2. 빈도수 순서대로 정렬한다. (repeat 1/2)

사용자 삽입 이미지






3. 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만든다. (repeat 2/2)

사용자 삽입 이미지









4. 빈도수 순서대로 정렬한다. (repeat 1/2)

사용자 삽입 이미지









5. 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만든다. (repeat 2/2)

사용자 삽입 이미지











6. 빈도수 순서대로 정렬한다. (repeat 1/2)

사용자 삽입 이미지











7. 가장 낮은 두 그룹을 묶어서 하나의 그룹으로 만든다. (repeat 2/2) 트리완성.

사용자 삽입 이미지














8. 이제 트리가 완성되었다.

가장 윗 트리에서부터 빈도수가 큰 트리에 0을 작은 트리에 1을 부여한다.

사용자 삽입 이미지














9. 위 트리를 기준으로 각 문자열의 비트를 참조한다.

부모노드에서 출발하여 문자열에 다다를때까지 비트를 더하여 참조한다. 즉,

사용자 삽입 이미지














A - 001 이 된다.

이와 같은 방법으로

B - 01, C - 1, D - 000 로 비트를 할당 할 수 있게 된다.

그러면 초기 문자열을 할당된 비트로 치환하여 보자.

1000000100110110111101011000001

위와 같이 치환되었다.

총 17문자, 17 byte 였던 원래 문자열이 31 bit 즉, 8 byte 로 압축이 된것이다.

물론 문자열 테이블도 붙고 헤더도 붙으면 약간 더 늘어나겠지만

이번 테스트에서의 압축률은 약 50%로 나타났다.



3. 디코딩은?

호프만 알고리즘을 이용하여 압축을 하면

어떤 문자가 어떤 bit 로 치환되었는지를 판단해야되기 때문에

호프만 테이블이라고 불리는 테이블을 추가해야한다.

호프만 테이블은 방금 우리가 만든 그 이진 트리를 말한다.

그 트리를 보고 복호화하는것이다.

사용자 삽입 이미지













한 bit 단위로 읽어서 테이블대로

문자가 나올때까지 트리를 타고 가면서 치환하는것이다.

예를 들어 00101 이라는 데이타는

AB 를 나타낸다는 것이다.

 - 00101 을 복호화해보자

 - 첫 비트 0 은 17로 표시되어 있는 트리에서 왼쪽, 즉 9 로 표시되어 있는 트리로 내려간다.
 - 다음 0 은 역시 왼쪽, 5 로 표시되어 있는 트리로 내려간다.
 - 다음 1 비트는 오른쪽, 즉 2로 표시되어 있는 트리, A 를 나타낸다.
 - 문자를 하나 찾았으니 자 그럼 다시 처음부터
 - 다음 0 은 17 트리에서 9 트리로
 - 다음 1 은 오른쪽 4 트리로, 즉 B 를 나타낸다.

이런식으로 문자열을 치환해주면된다.

대단하지 않은가??

이게 바로 허프만 알고리즘의 원리인것이다.


신고
  1. 이전 댓글 더보기
  2. Favicon of http://www.d-magic.co.kr D.Magic 2008.02.05 12:18 신고

    다봐도 전혀 무릎이 탁 쳐지지 않는군요 ㅎㅎㅎ

    • Favicon of http://wooyaggo.tistory.com 우야꼬  2008.02.05 14:24 신고

      ㅋㅋ 제가 설명이 부족했나봐요~
      그치만 허프만 알고리즘은 대단한거라구욧!! ㅎㅎ

  3. Favicon of http://apollocation.tistory.com 원강민 2008.03.08 02:13 신고

    허프만..시간 좀 들여서 구현해봤는데..떱..그냥 ByteArray의 compress()를 쓰는 것만 못하더라구요..API를 이기려 들면 안된다는걸 다시 한번 느꼈네요..ㅎㅎ

    • Favicon of http://wooyaggo.tistory.com 우야꼬  2008.03.08 12:23 신고

      C 로 만든걸 이기려고 만든게 아니라
      플래시가 앞으로 이런것도 가능하다는걸
      눈으로 확인하고 싶었어요^^
      혹시 모르죠. AIR 로 로컬에서 H.264/AVC 로 녹화하면서
      인코딩까지 하는날이 올지도^^
      그때는 반드시 필요한 기술이죠^^
      그만큼 허프만은 모든 압축기술의 거의 필수니까요.

    • Favicon of http://apollocation.tistory.com 원강민 2008.03.08 14:53 신고

      하긴 그렇죠..영상처리쪽도 보니까 허프만 알고리즘과 유사한 방식들이 많이 쓰이더라구요..훌륭한 아이디어에요..

  4. dreamcatcher 2008.03.23 12:30 신고

    우아 정말 쉽게 설명해주셔서 감사해요. ^^ 완벽하게 이해해서 가요~ ㅋ

  5. 2008.06.13 02:43

    비밀댓글입니다

    • Favicon of http://wooyaggo.tistory.com 우야꼬  2008.06.13 10:20 신고

      어익후 과찬이십니다.
      그리고 밥 사주신다면 어디든지 달려갑니다 ㅇ_ㅇ!

  6. Favicon of http://www.83rpm.com/blog 동범이 2008.07.24 13:25 신고

    플생사모에서 보고 왔어요.

    평소에도 궁금했는데 읽어보니까 딱 이해가 되네요. ^^

    즐겨찾기 해놓고 나중에 필요할 때 읽어볼꼐요.

    그런데 플래시에서 이 알고리즘을 쓸수 있도록 이런 클래스나 혹은 공개된 소스가 있을까요?;;

    • Favicon of http://wooyaggo.tistory.com 우야꼬  2008.07.24 13:40 신고

      Java 나 C 코도는 공개된 코드가 굉장히 많은데요.
      ActionScript 도 몇몇 공개된 코드가 있었는데
      정확하게 북마킹을 해놓지 않아서 잘 >.<

      제가 만들어놓은건 아직 깔끔하지가 않아서 공개하기가 좀 부끄럽네요.

  7. Aldaris[tem] 2008.07.26 17:28 신고

    와 허프만 숙제있어서 숙제해야되는데 살았다

    ㄳ 기대하고 있겠습니다.

    • Favicon of http://wooyaggo.tistory.com 우야꼬  2008.07.28 08:55 신고

      어익후 이미 웹에 잇는 걸
      머리 나쁜 제가 이해하도록 함 그려본건데 도움되셨다니
      다행이네요!!

  8. 옛날꿀호떡 2008.10.14 14:31 신고

    완전 잘 배우고 갑니다~~
    즐겨 찾기 추가해 놓고 자주 들려야 겠네요

    • Favicon of http://wooyaggo.tistory.com 우야꼬  2008.10.14 21:58 신고

      요즘 게을러서 포스팅 못하고 있었는데
      꿀호떡님 읽을거리 올리려면 분발해야겠습니다!!

  9. DroPlet 2010.01.02 11:56 신고

    글 잘 읽었습니다 ^^
    지금 연구 주제가 압축이라서
    허프만 코딩에 대한거 찾고 있었는데

    감사합니다~

    • Favicon of http://wooyaggo.tistory.com 우야꼬  2010.01.04 03:34 신고

      앗 다행입니다^^ 두고두고 도움 되시는 분들이 있다니까 무지 뿌듯하네요~

  10. pat 2010.12.20 09:58 신고

    감사합니다! 잘보고 갑니다 :)

  11. Cat 2011.11.06 21:30 신고

    좋은 자료 보고 갑니다! 이 허프만 알고리즘을 통하여 결과물을 도출하여
    확인하는 방법은 이진트리를 사용하여 인코딩후 변화된 비트를 비교함
    으로써 가능한건가요~? 아직 많이 초보라서 궁금한게 많이있네요!

  12. 그렇다면ㅇㅂㅇ 2012.03.14 11:27 신고

    그렇다면 압축율이 80프로가 안되는게 아닌가요? 허프만 트리도 용량이 있을테니까요.

  13. BK 2012.10.02 20:47 신고

    좋은자료 감사합니다!!! 퍼갈게요~~!!

  14. diseney80 2013.07.11 14:47 신고

    좋은 자료 보고 갑니다.
    리버싱에서 비손실 압축 부분 설명이 나오면서 , 허프만 알고리즘이 뭘까 고민하고, 다른 자료를 봐도 잘 이해가 않되었는데, 님이 작성한 자료를 보고, 특히 이진 트리 보고 정말 무릎 탁!! 쳤네요.
    출력해서 자주 보겠습니다.

    • Favicon of http://wooyaggo.tistory.com 우야꼬  2013.07.15 17:57 신고

      저도 몇년전에 써두고 많은 분들이 읽어주시니까 뿌듯하네요 ㅎㅎ

      근데 저도 다시 읽으니까... 새롭게 느껴지네요 ㅋㅋ

  15. rt 2014.05.06 22:08 신고

    고맙습니다 덕분에 정말 좋은 자료 보고갑니다!! 수업 시간 때 듣긴 했지만 다시 혼자 공부하면서 보니깐 훨씬 머릿속에 잘 들어왔네요 그림설명이 정말 고마워요!!!

  16. 데이브 2015.06.15 00:00 신고

    감사합니다 덕분에 이해가 슉 됬습니다

  17. DK 2016.01.16 18:40 신고

    명쾌! 감사요~!

  18. 라도파 2016.01.27 15:12 신고

    명쾌한 설명이네요.

  19. snorlax 2016.05.04 17:07 신고

    정말 무릎을 탁 치는 설명이네요 감사합니다.

  20. error found 2016.06.06 00:20 신고

    안녕하세요 지나가나 몇자 적습니다.
    글쓰신분께서 살짝 실수를 하신것 같은데 허프만 코드는 probability ascending order 가 되어야 합니다.
    앞뒤가 바뀌었네요.
    레퍼런스는 아주 많이 찾아볼수 있으나
    이사이트가 정확히 알고리즘이 어떻게 동작하는지 보여줍니다.
    http://algoviz.org/OpenDSA/AV/Binary/huffmanBuildAV.html

  21. 안녕하세요 2017.09.04 18:54 신고

    감사합니다~!!

+ Recent posts