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