Compression (1)
Huffman Coding
- 가장 대표적인 데이터 압축 알고리즘 중 하나이다. 또한 무손실 압축 알고리즘이기도 하다.
- 압축의 방식에는 무손실과 손실 압축이 있다.
- 이미지나 소리, 동영상 등의 멀티미디어 데이터들은 원본에 비해 약간의 손실이 있더라도 사람이 인지하기 힘들기 때문에 손실 압축 기법을 주로 이용하며 이 방식은 압축률 측면에서 효율적인 알고리즘이다.
- 텍스트나 수치 데이터의 경우에는 데이터의 손실이 있으면 의미가 완전히 달라지기 때문에 무손실 압축 기법을 사용해야만 한다.
위 그림은 문자가 5개 있을 경우를 가정하였으며 각 문자는 빈도의 퍼센티지로 표현하고 있다. 이렇게 표현해도 상관이 없는 이유는 허프만 코드 자체가 실제 빈도가 아니라 상대적 빈도에 의해 결정되는 알고리즘이기 때문이다.
우선 다섯개의 빈도값중 가장 작은 두개를 찾는다. 그 후 이 두 문자를 자식으로 하는 트리를 만들어 두 문자의 빈도를 더한 값을 부모 노드로 삼는다.
그 후 남은 네개의 빈도 중 가장 작은 두 숫자를 찾으며 계속 트리를 만들어나간다.
최종적으로 완성된 트리의 왼쪽 가지는 0으로, 오른쪽은 1로 하여 최종적으로 각 문자들의 비트를 정해준다.
Huffman Coding Example
- 6가의 문자 a, b, c, d, e, f로 이루어진 파일이 있다. 문자의 총 개수는 100,000개이며 각 문자의 등장 횟수는 아래 그림과 같다.
- 고정길이 코드를 이용하면 각 문자를 표현하기 위해 3비트가 필요하며, 따라서 파일의 길이는 300,000비트가 된다.
- 위 그림의 테이블에 표시되어 있는 가변길이 코드를 이용하면 224,000비트로 압축할 수 있다.
Prefix Code
- 디코딩할 수 있도록 만든 일정한 규칙이다.
- 어떠한 codeword도 다른 codeword의 prefix가 되지 않도록 하는 코드다. 즉 한 문자에 숫자가 등록되면 다음 문자의 숫자를 등록할때 이미 등록된 문자의 숫자가 지금 문자가 지정할 숫자의 맨 앞에 들어가면 안된다.
- codeword : 하나의 문자에 부여된 이진코드 (Ex : a = 000 등)
- 모호함이 없어 디코딩이 가능하다.
- prefix code는 하나의 이진트리를 이용하여 표현할 수 있다.
- 위 그림의 왼쪽은 고정길이, 오른쪽은 가변길이 코드를 이진 트리를 통해 표현한 것이다.
Run-Length Encoding
- 무손실 데이터 압축 기법의 하나이다.
- 런(run)은 동일한 문자가 하나 또는 그 이상으로 연속해 나오는 것을 뜻한다.
- Ex) String s = "aaabba"는 3개의 런으로 구성 => "aaa", "bb", "a"
- run-length encoding에서는 각 run을 "run을 구성하는 문자"와 "run의 길이"의 순서쌍인 (n, ch)로 encoding한다. 위 예시를 인코딩한다 하면 3a2b1a가 된다.
- Run-Length encoding은 길이가 긴 런들이 많을 때 효율적이다. 이를테면 이미지 데이터의 픽셀들을 압축할 때나 이럴때 효율적인 압축을 할 수 있다.
