허프먼 부호화: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
앗, 죄송합니다. |
편집 요약 없음 |
||
4번째 줄:
허프만 부호화가 항상 최적의 접두 부호를 만들어 내기는 하지만, 접두 부호가 아닌 다른 종류의 부호가 더 효율적일 수도 있다. 예를 들어 여러 문자를 하나의 부호로 묶어 표현할 수 있는 [[산술 부호화]]나 [[LZW]] 등이 허프만 부호보다 효율적인 경우가 많으며, 특히 후자 같은 경우 문자들의 빈도를 정확히 알 수 없는 경우에도 적용할 수 있다.
위에서 아래로 진행하는 샤논파노방법과는 달리 허프만 알고리즘의 부호화 순서는 아래에서 위로 진행한다.
순서를 좀더 확실히 적어보자면..
1. 초기화 : 모든 기호를 출현 빈도수에 따라 나열한다.
2. 단 한가지 기호가 남을 때까지 아래 단계를 반복한다.
< 목록으로 부터 가장 빈도가 낮은것을 2개 고른다. 그아믕 허프만이 두가지 기호를 부모노드를 가지는 부트리를 구성하고 자식노드를 생성한다.
부모노드 단 기호들의 빈도수를 더하여 주노드에 할당하고 목록의 순서에 맞도록 목록에 삽입한다 .
목록에서 부모노드에 포함된 기호를 제거한다.
[[분류:무손실 압축 알고리즘]]
[[cs:Huffmanovo kódování]]
| |||