허프만 코딩
- 압축
- 무손실:원본과 완벽하게 동일 ex)허프만
- 손실:손실이 되나 사람에게 티가 안되게
- 가령 6개의 문자 a,b,c,d,e,f로 이루어진 파일이 있다ㅏ고 하자. 문자의 총 개수는 십만개이고 각 문자의 등장 횟수는 다음과 같다
0 1 00 01 10 11=> 이런식으로 인코딩을 해서 압축
- 고정길이 코드를 사용하면 각각의 문자를 표현하기 위해서 3비트가 필요하며, 따라서 파일의 길이는 삽십만비트가 된다. 십만x3=삼십만
- 위 테이블의 가변길이 코드를 사용하면 224,000비트가 된다.
- Prefix code
- 어떤 codeword 다른 codeword의 prefix가 되지 않는 코드
(codeword: 하나의 문자에 부여된 이진코드를 말함)
- 모호함이 없어 디코드가 가능함
- Prefix code는 하나의 이진트리로 표현 가능함
- 허프만 코딩 알고리즘
Two huffman trees created for five letters a,b,c,d, and e with probabilities .39 ,.21 ,.19 ,.12, and .09 => a가 39% b가 21% c가 19% 등
Two Huffman tress generated for letters P, Q, R, S, and T with probabilities .1 .1, .1, .2, and .5
인코딩을 했을 때 파일의 길이는 동일해 진다.
- Run-length encoding
- 런은 동일한 문자가 하나 혹은 그 이상 연속해서 나오는 것을 의미
- Run-length encoding에서는 각각의 run 그 “run을 구성하는 문자”와 “run의 길이”의 순서쌍 (n, ch)로 encoding한다. 여기서 ch가 문자이고 n은 길이이다. 가려 위의 문자열 s는 다음과 같잉 코딩된다.3ab1a. => aaabbaba
- Run-length encoding은 길이가 긴 run들이 많은 경우에 효과적이다.
댓글