허프먼 부호화: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
ㄴㄷ |
잔글 110.70.51.200(토론)의 편집을 Ykhwong의 마지막 판으로 되돌림 |
||
1번째 줄:
[[전산학]]과 [[정보 이론]]에서 '''허프만 부호화'''(Huffman coding)는 [[무손실 압축]]에 쓰이는 [[엔트로피 부호화]]의 일종으로, 데이터 문자의 등장 빈도에 따라서 다른 길이의 부호를 사용하는 [[알고리즘]]이다. [[1952년]] 당시 박사과정 학생이던 [[데이비드 허프만]]이 《{{lang|en|A Method for the Construction of Minimum-Redundancy Codes}}》<ref>http://compression.ru/download/articles/huff/huffman_1952_minimum-redundancy-codes.pdf</ref>란 제목의 논문으로 처음 발표했다.
허프만 부호화는 문자들의 빈도로부터 [[접두 부호]](어떤 한 문자에 대한 부호가 다른 부호들의 접두어가 되지 않는 부호)를 만들어 내는 알고리즘으로, 적게 나오는 문자일수록 더 긴 부호를 쓰고 많이 나올수록 더 짧은 부호를 쓴다. 허프만 부호화는 주어진 빈도에 대해서 항상 최적의 접두 부호를 만들어 내며, 이 과정은 빈도가 [[정렬 알고리즘|정렬]]되어 있을 경우 [[대문자 O 표기법|O]](''n'')만에 가능하다. 각 문자들의 빈도가 2의 거듭제곱 꼴이거나 모두 같을 경우 이 접두 부호는 간단한 이진 [[블록 부호]]와 동일하다.
만들어 내기는 하지만, 접두 부호가 아닌 다른 종류의 부호가 더 효율적일 수도 있다. 예를 들어 여러 문자를 하나의 부호로 묶어 표현할 수 있는 나 등이 허프만 부호보다 효율적인 경우가순서는 아래에서 위로 진행한다.▼
▲허프만 부호화가 항상 최적의 접두 부호를 만들어 내기는 하지만, 접두 부호가 아닌 다른 종류의 부호가 더 효율적일 수도 있다. 예를 들어 여러 문자를 하나의 부호로 묶어 표현할 수 있는 [[산술 부호화]]나 [[LZW]] 등이 허프만 부호보다 효율적인
위에서 아래로 진행하는 샤논파노방법과는 달리 허프만 알고리즘의 부호화 순서는 아래에서 위로 진행한다.
== 알고리즘 ==
# 초기화 : 모든 기호를 출현 빈도수에 따라 나열한다.
# 단 한 가지 기호가 남을 때까지 아래 단계를 반복한다.
## 목록으로부터 가장 빈도가 낮은 것을 2개 고른다.
## 그 다음 허프만이 두가지 기호를 부모 노드를 가지는 부트리를 구성하고 자식노드를 생성한다. 부모 노드 단 기호들의 빈도수를 더하여 주 노드에 할당하고 목록의 순서에 맞도록 목록에 삽입한다.
## 목록에서 부모노드에 포함된 기호를 제거한다.
## 리프 노드로 하는 를 만들어서 접두 부호를 만들어 내는 알고리즘이다.▼
== 참조 ==
| |||