본문 바로가기

나만의 작업

Huffman algorithm(호프만 알고리즘)

저는 C/C++에 많은 관심을 가져보지도 않고, 특히나 응용 프로그램은 많이 안해봐서
작년에 압축은 어떻게 되는것일까, 의문이 든적이 있었습니다.
그때 아는분께 여쭈었더니, 가장 빈도수가 높은 기호를 가장 적은 비트로 표현하여 압축을 한다고 대충 들었습니다.

그땐 이 알고리즘인지 몰랐는데, 그 알고리즘이 호프만 알고리즘이었는지 이제 알았습니다.
쉬워보이는듯 하면서 트리로 가니깐 복잡해 보이는 알고리즘.

이번에 자바로 한번 짜볼려고 하는데 C/C++ 자료는 많은데 자바는 없네요..
저에겐 마냥 어렵네요..ㅎㅎ

  • 자주 사용되는 문자는 짧은 코드를, 자주 사용하지 않는 문자는 긴 코드를 지정
    실제 평균 문자 코드 길이를 줄여 압축하는 방법 
     

Making binary codes from probabilities

We have a text like "aaabc", with the probabilities you can see below. Because we can output bits, what about if we make a binary decision? the most probable or the rest, 0 or 1. In our example, 0 for 'a', then 1 for the rest, 'b' and 'c', and then we have to choose again: 0 for 'b' and 1 for 'c'. Using that codes we can output "01001110" and the decoder will correctly decode "abacb". That is because the codes have the prefix property and also are instantaneously decodable. Notice too that they are close to the entropy.
 

Symbol Probability Code Entropy (ideal code length)
a 3/5 0 (1 bit) 0.737 bits
b 1/5 10 (2 bits) 2.322 bits
c 1/5 11 (2 bits) 2.322 bits

Because we are doing a binary decision, we could represent it with a binary tree. A binary tree is a data structure, whose shape is like a tree (but upside down). It has an starting node called root. The root has two children (pointers to two other nodes), in our case we assign 0 to one child and 1 to the other. If a node has no child it's called a leaf, here it is where there are the symbols. In the example you can see the probability of the node in brackets.

 


참고 :
http://www.arturocampos.com/cp_ch3-1.html#Making%20binary%20codes%20from%20probabilities

  • 개인사정이 있어서(학원다니느라) 알고리즘 수업을 못들었는데 완전 OTL 이네요... ;ㅁ;

    • 버리 2007.05.07 13:32 댓글주소 수정/삭제

      저도 알고리즘은 많이 몰라서
      지금이라도 늦지 않았잖아요~
      같이 해 보아요~ㅎㅎ

  • http://en.wikipedia.org/wiki/Huffman_coding
    위키를 애용해보세요~ ㅋㅋ

    http://apollonic.net/code/
    여기에 자바 코드가 있네요. 제대로 돌아가는지는 모르겠지만요. ㅎㅎ

    • BlogIcon 버리 2007.05.07 23:25 댓글주소 수정/삭제

      wiki사이트도 한번 보긴했지만,
      소스코드 정말 완전 감사드려요.
      ^^ BuildHeap님은 복 받으실거에요~

  • cetaurui 2009.11.09 23:19 댓글주소 수정/삭제 댓글쓰기

    양질의 자료가 많이 있구만..

  • Belle 2009.11.14 02:47 댓글주소 수정/삭제 댓글쓰기

    저도 다 까먹어서 아무것도 머릿속에 남아있는게 없지만..

    알고리즘, 컴파일러, 이산수학 등등은 아주 재미있었던거 같습니다. 흥미앞에 노력도 무너진다고 하니 열심히 재미를 가지고 다가서보세요~

    • 버리 2007.05.08 02:21 댓글주소 수정/삭제

      저도 알고리즘, 이산수학 공부할려구요
      수학에 재미붙이고 파요~ㅋㅋ

  • 컴공녀 2010.05.12 16:51 댓글주소 수정/삭제 댓글쓰기

    자료 잘 보구갑니다..^^ 근데 정말 자바코드 찾기힘들지않아요? 죽겠네요 정말..ㅠ..ㅠ