Huffman 코드들은 데이터를 매우 효과적으로 압축한다: 20%에서 90%의 절약은 일반적이다, 압축되는 데이터의 특징에 따라. 우리는 그 데이터를 문자들의 한 연속으로 고려한다. Huffman의 그리디 알고리즘은 binary string으로서 각 문자들을 나타내는 최적의 방법을 구성하기 위해서, 각 문자들이 얼마나 종종 발생하는지를 (즉, 그것의 빈번함) 주는 테이블을 사용한다.
우리가 compact하게 저장하기를 원하는 100,000개의 문자 데이터 파일을 가진다고 가정하자. 우리는 파일에서 그 문자들이 그림 16.3으로 주어진 빈번함과 함께 발생한다고 관찰한다. 즉, 오직 6개의 다른 문자들만이 나타나고, 그리고 그 문자 a는 45,000번 발생한다.
우리는 그러한 정보 파일을 어떻게 나타내는지에 대해 많은 옵션들을 가진다. 여기에서, 우리는 binary character code (또는 짧게해서 code)를 설계하는 문제를 고려한다. 거기에서 각 문자는 unique binary string으로 나타내어지는데, 우리는 그것을 codeword라고 부른다. 만약 우리가 fixed-length code를 사용한다면, 우리는 6개의 문자를 나타내는데 3개의 비트들이 필요하다. 이 방법은 전체 파일을 코딩하는데 300,000 비트들을 요구한다. 우리가 더 잘할 수 있는가?
variable-length code는 (가변-길이 코드) 상당히 고정 길이 코드보다 더 잘할 수 있다. 이것은 frequent characters에 짧은 codewords를 주고, infrequent characters에 긴 codewords를 준다. 그림 16.3은 그러한 코드를 보여준다; 여기에서 1-bit string 0은 a를 나타내고, 4-bit string 1100은 f를 나타낸다. 이 코드는
(45 * 1 + 13 * 3 + 12 * 3+ 16 * 3 + 9 * 4 + 5 * 4) * 1000 = 224,000 bits
를 요구한다, 그 파일을 나타내기 위해, 약 25%의 절약이다. 사실, 이것은 이 파일에 대한 최적의 character code이다, 우리게 보게 되듯이.
Prefix codes
우리는 여기에서 오직 코드들을 고려하는데, 어떠한 codewords가 어떤 다른 codeword의 prefix가 아닌 것이다. 그러한 코드들을 prefix codes라고 불려진다. 비록 우리가 그것을 여기에서 증명하지 않을지라도, 한 prefix code는 항상 어떤 character code사이의 최적의 데이터 압축을 얻을 수 있고, 그래서 우리는 우리의 관심을 prefix codes에 제한하여 일반성의 손실을 겪지 않는다.
Encoding은 항상 어떤 binary character code에 대해서 간단하다; 우리는 file의 각 문자를 나타내는 codewords를 연결시킨다. 예를들어, 그림 16.3의 가변 길이 prefix code와 함께, 우리는 3개의 문자 파일 abc를 0 * 101 * 100 = 0101100 으로 코드하고, dot은 concatenation을 표기한다.
Prefix 코드들은 그것들이 decoding을 간단하게 하기 때문에 바람직하다. 어떠한 codeword도 어떤 다른 것의 prefix가 아니기 때문에, encoded file을 시작하는 codeword는 명백하다. 우리는 간단히 초기의 codeword를 확인할 수 있고, 그것을 원래 문자로 바꿀 수 있고, 그리고 인코딩된 파일의 나머지에 디코딩 프로세스를 반복한다. 우리의 예제에서, 그 문자열 001011101은 uniquely하게 0 0 101 1101 로 파싱되고, 그것은 aabe이다.
그 디코딩 프로세스는 prefix code에 대한 편리한 표기를 필요하는데, 우리가 쉽게 초기 codeword를 고를 수 있게 하기 위해서이다. leaves가 주어진 문자들인 binary tree는 한 가지 그러한 표기법을 제공한다. 우리는 한 문자에 대핸 binary codeword를 root에서 그 문자로 가는 간단한 경로로 해석한다. 거기에서 0은 "왼쪽 자식으로 가라'이고 1은 "오른쪽 자식으로 가라"이다. 그림 16.4는 우리의 예제의 두 코드들에 대한 트리들을 보여준다. 이러한 것들이 이진 탐색들이 아니라는 것에 주목해라, 그 leaves가 정렬된 순서로 나타날 필요가 없고, 내부 노드들은 character keys를 포함하고 있지 않기 때문이다.
한 file에 대한 optimal code는 항상 full binary tree로 나타내어진다, 거기에서 모든 leaf가 아닌 노드는 두 개의 자식을 가진다 (see Exercise 16.3-2). 우리의 예제에서 그 고정 길이 코드는 그림 16.4(a) 에서 보여지듯이 그것의 트리가 full binary tree가 아니기 때문에 최적ㄱ이 아니다: 그것은 10으로 시작하는 codewords를퐇마하지만, 어떠한 것도 11로 시작하지 않는다. 우리는 우리의 관심을 full binary trees로 제한하기 때문에, 만약 C가 문자들이 그려지고 모든 문자 frequencies가 양수인 알파벳이라면, 최적의 optimal prefix code에 대한 트리는 정확히 |C|개의 leaves를 가진다. 그 알파벳의 각 문자에 대해 하나씩, 그리고 정확히 |C| - 1개의 내부 노드들이 있다 (see Exercise B.5-3).
prefix code에 되응되는 tree T가 주어진다면,우리는 쉽게 한 파일을 인코딩하는데 요구되는 비트의 개수를 연산할 수 있다. 알파벳 C에 있는 각 문자 c에 대해, attribute c.freq가 파일에서 c의 frequency를 표기한다고 하고, d_T(c)는 tree에서 c의 leaf의 깊이를 나타낸다고 하자. d_T(c)는 또한 문자 c에 대한 codeword의 길이이다. 한 파일을 인코딩하는데 요구되는 비트들의 개수는 따라서
그리고 이것은 그것을 tree T의 cost로서 정의한다.
Constructing a Huffman code
Huffman은 Huffman code라고 불려지는 optimal prefix code를 구성하는 그리디 알고리즘을 발명했다. Section 16.2에서 우리의 관찰과 함께, 옳음에 대한 그것의 증명은 그리디 선택 특징과 optimal substructure에 의존한다. 이러한 특성들이 유효한 것을 증명하고 그러고나서 슈도코드를 개발하기 보다는, 우리는 그 슈도코드를 처음에 보여준다. 그렇게 하는 것은 그 알고리즘이 그리디 선택을 어떻게 하는지를 명료하게 하는데 도움이 될 것이다.
다음의 슈도코드에서, 우리는 C가 n개의 문자들의 한 집합인 것을 가정하고, C에 있는 각 문자 c는 c.freq라는 한 attribute가 그것의 frequency를 주는 한 오브젝트라고 가정한다. 그 알고리즘은 optimal code와 대응되는 tree T를 bottom-up 방식으로 만든다. 그것은 |C| leaves의 한 집합으로 시작하고, 최종 tree를 만들기 위해 |C| - 1개의 "merging" 연산의 한 순서를 수행한다. 그 알고리즘은 min-priority queue Q를 사용하는데, freq attribute를 특성으로하는데, 함께 합치기 위해 두 개의 least-frequen objects를 확인하기위해서이다. 우리가 두 오브젝트들을 merge할 때, 그 결과는 한 새로운 오브젝트인데, 그것의 frequency는 합쳐졌던 두 오브젝트들의 frequencies의 합이다.
HUFFMAN(C) 1 n = |C| 2 Q = C 3 for i = 1 to n - 1 4 allocate a new node z 5 z.left = x = EXTRACT-MIN(Q) 6 z.right = y= EXTRACT-MIN(Q) 7 z.freq = x.freq + y.freq 8 INSERT(Q,z) 9 return EXTRACT-MIN(Q) // return the root of the tree
우리의 예제에 대해, 허프만 알고리즘은 그림 16.5에서 보여지듯이 진행한다. 그 알파벳이 6개의 문자들을 포함하기 때문에, 그 초기의 큐 사이즈는 n = 6이고, 5개의 merge steps이 그 트리를 구성한다. 그 마지막 트리는 optimal prefix code를 나타낸다. 한 문자에 대한 codeword는 root에서 letter로 가는 간단한 경로에서 edge labels의 순서이다.
Line 2는 min-priority queue를 C에 있는 문자들로 초기화한다. lines 3-8에서 for loop는 반복적으로 가장 낮은 frequency를 가진 두 개의 노드들을 큐로부터 x와 y를 추출한다. 그리고 그것들을 그것들의 merger를 나타내는 한 새로운 노드 z로 대체한다. z의 frequency는 x와 y의 frequencies의 sum으로서 line 7에서 정의된다. 그 node z는 x를 그것의 왼쪽 child로 y를 그것의 오른쪽 child로 가즌ㄴ다. (이 순서는 임의적이다; ㅓ떤 노드의 왼쪽과 오른쪽 자식을 바꾸는 것은 같은 비용의 다른 코드를 만들어낸다.) n - 1개의 mergers 후에, line 9는 queue에 남은 한 노드를 반환하고, 그것이 코드 트리의 root이다.
비록 그 알고리즘은 같은 결과를 만들어낼 것이지만, 만약 우리가 그 변수 x와 y를 excise(?)하려한다면, - 직접적으로 z.left와 z.right에 할당하고, z.freq = z.left.freq + z.right.freq 로 바꾼다면 - 우리는 옳음의 증명에서 노드 이름들 x와 y를 사용할 것이다. 그러므로, 우리는 그것들을 그냥 두는게 편리한 것으로 안다.
~~~
댓글 없음:
댓글 쓰기