(새 문서: ==개요== ;Huffman coding ;허프만 부호화 * 무손실 압축에 쓰이는 엔트로피 부호화의 일종 * 데이터 문자의 등장 빈도에 따라서 다른 길이의 부...) |
(→개요) |
||
| (같은 사용자의 중간 판 하나는 보이지 않습니다) | |||
| 1번째 줄: | 1번째 줄: | ||
==개요== | ==개요== | ||
;Huffman coding | ;Huffman coding | ||
;허프만 부호화 | ;허프만 부호화. 허프만 코딩 | ||
* 무손실 압축에 쓰이는 엔트로피 부호화의 일종 | * 무손실 압축에 쓰이는 엔트로피 부호화의 일종 | ||
* 데이터 문자의 등장 빈도에 따라서 다른 길이의 부호를 사용하는 알고리즘 | * 데이터 문자의 등장 빈도에 따라서 다른 길이의 부호를 사용하는 알고리즘 | ||
| 14번째 줄: | 14번째 줄: | ||
:예: 여러 문자를 하나의 부호로 묶어 표현할 수 있는 산술 부호화나 LZW 등이 허프만 부호보다 효율적인 경우가 많음 | :예: 여러 문자를 하나의 부호로 묶어 표현할 수 있는 산술 부호화나 LZW 등이 허프만 부호보다 효율적인 경우가 많음 | ||
:대체로 하나의 기호를 정수개의 길이를 가진 부호로서 표현하도록 되어 있는 한계에서 기인함 | :대체로 하나의 기호를 정수개의 길이를 가진 부호로서 표현하도록 되어 있는 한계에서 기인함 | ||
https://upload.wikimedia.org/wikipedia/commons/thumb/8/82/Huffman_tree_2.svg/625px-Huffman_tree_2.svg.png | |||
==같이 보기== | ==같이 보기== | ||
2017년 11월 8일 (수) 20:42 기준 최신판
1 개요[ | ]
- Huffman coding
- 허프만 부호화. 허프만 코딩
- 무손실 압축에 쓰이는 엔트로피 부호화의 일종
- 데이터 문자의 등장 빈도에 따라서 다른 길이의 부호를 사용하는 알고리즘
- 1952년, 박사과정 학생 데이비드 허프만이 논문 《A Method for the Construction of Minimum-Redundancy Codes》으로 처음 발표함
- 문자들의 빈도로부터 접두 부호를 만들어 냄
- 접두 부호: 어떤 한 문자에 대한 부호가 다른 부호들의 접두어가 되지 않는 부호
- 적게 나오는 문자일수록 더 긴 부호를 쓰고 많이 나올수록 더 짧은 부호를 씀
- 주어진 빈도에 대해서 항상 최적의 접두 부호를 만들어 냄
- 이 과정은 빈도가 정렬되어 있을 경우 O(n)만에 가능함
- 각 문자들의 빈도가 2의 거듭제곱 꼴이거나 모두 같을 경우 이 접두 부호는 간단한 이진 블록 부호와 동일함
- 허프만 부호화가 항상 최적의 접두 부호를 만들어 내기는 하지만, 접두 부호가 아닌 다른 종류의 부호가 더 효율적일 수도 있음
- 예: 여러 문자를 하나의 부호로 묶어 표현할 수 있는 산술 부호화나 LZW 등이 허프만 부호보다 효율적인 경우가 많음
- 대체로 하나의 기호를 정수개의 길이를 가진 부호로서 표현하도록 되어 있는 한계에서 기인함
2 같이 보기[ | ]
3 참고[ | ]
네이버백과 "허프만 부호화"
편집자
로그인하시면 댓글을 쓸 수 있습니다.
{{ comment.name }}
{{ comment.created | snstime }}
-
{{comment.page_title}} ―{{comment.name}}