Huffman & Arithmetic coding

소개

Huffman & Arithmetic coding

목차

▶Huffman Coding
1-1. 허프만 코딩의 배경
1-2. 허프만 코딩의 특징
1-3. Huffman 코딩의 방법
1-4. Huffman 코딩의 장점의 예
1-5. Adaptive Huffman coding(=dynamic Huffman coding)
3. Arithmetic 코딩
5. Number==0이므로 Stop

본문내용

▶Huffman Coding
1-1. 허프만 코딩의 배경
이 방법은 1954년 Huffman이라는 사람이 고안하였다. 문서 내에서 모든 글자가 같은 빈도로 사용되지는 않는 것에 착안한 것이다. 가장 많은 횟수로 사용된 글자를 가장 짧은 부호어에 대응시키는 것이다. 이 방법을 사용하면 통계적으로 통신이미지 정보를 1/8의 크기로 만든다한다. 이렇게 압축률이 좋다보니 요즘에도 많이 사용되고 있다.
예를 들어 JPEG 나 MPEG 포맷의 형태가 Huffman coding을 이용한 포맷이다. 이들은 그림에서 가장 많이 사용된 색을 가장 짧은 부호어로 표시하는 방식을 이용한다.

1-2. 허프만 코딩의 특징
￭ 출현 빈도가 높은 문자에 짧은 코드를 할당
￭ 출현빈도가 낮은 문자에 긴 코드를 할당
￭ 압축된 코드 길이가 다양(variable length coding)

1-3. Huffman 코딩의 방법
☞ Algorithm 4.1:Huffman 2진트리 구성 알고리즘
￭ Leaf 노드의 문자는 압축하여야 할 데이터를 나타낸다.
￭ 모든 노드는 출현빈도를 나타내는 확률 값 p를 가지고 있다.
◦ 루트노드의 확률값은 1이다.
￭ 트리는 다음 방법에 의하여 구성한다.
◦ 가장 낮은 확률값을 가지는 두 개의 ㅊ를 결합하며 2진서브트리를 만든다.
◦ 이과정을 루트를 만날 때 까지 반복한다.
◦ 트리를 완성한 후에 모든 엣지(edge)에 0과 1 값을 임의로 지정한다.
￭ Huffman 코드는 루트로부터 leaf 노드까지의 레이블 값이다.

참고자료

· 없음