Huffman algorithm(호프만 알고리즘)
Posted at 2007/05/07 01:47// Posted in 나만의 작업저는 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
'나만의 작업' 카테고리의 다른 글
| 고슴도치플러스의 서비스 홍보... (4) | 2007/05/22 |
|---|---|
| Rss 주소 바꾸었습니다~ (12) | 2007/05/16 |
| 저도 Mac!을 씁니다. (4) | 2007/05/13 |
| 객체지향 프로그래밍. (0) | 2007/05/13 |
| Huffman algorithm(호프만 알고리즘) (9) | 2007/05/07 |
| OpenID 서버가,, 죽으면,, (16) | 2007/05/04 |
| firefox에서 원격 블로깅하기 (14) | 2007/04/15 |
| google에서의 flyburi를... (7) | 2007/04/12 |
| 스프링노트공간에 제 노트를 하나 마련했습니다. (12) | 2007/04/08 |
지금이라도 늦지 않았잖아요~
같이 해 보아요~ㅎㅎ
위키를 애용해보세요~ ㅋㅋ
http://apollonic.net/code/
여기에 자바 코드가 있네요. 제대로 돌아가는지는 모르겠지만요. ㅎㅎ
소스코드 정말 완전 감사드려요.
^^ BuildHeap님은 복 받으실거에요~
알고리즘, 컴파일러, 이산수학 등등은 아주 재미있었던거 같습니다. 흥미앞에 노력도 무너진다고 하니 열심히 재미를 가지고 다가서보세요~
수학에 재미붙이고 파요~ㅋㅋ