--------------------------------------------------------------------------
| 압축키 | encoding할수 있는 데이터 수 | 각 코드의 길이 | 쓰지 않는 코드 길이 |
|-------------------------------------------------------------------------
| a | 28 | 1 | 0 |
| b | 14 | 2 | 0 |
| c | 09 | 3 | 1 |
| d | 07 | 4 | 0 |
| e | 05 | 5 | 3 |
| f | 04 | 6 | 0 |
| g | 03 | 7 | 1 |
| h | 02 | 8 | 0 |
| i | 01 | 9 | 0 |
--------------------------------------------------------------------------
<표 1>
입력 : 4, 6, 11, 12, 3, 5, 21, 7, 9, 13,
실제 : 3, 5, 10, 11, 2, 4, 20, 6, 8, 12
이진 : 11, 101, 1010, 1011, 10, 100,10100, 110, 1000, 1100
32 bit = 4byte
4bit(키)+28bit(데이터) 로 구성
이제 위에 나열한 이진 코드를 가지고 데이터 압축하는 방법을 설명하겠다.
첫번째 11은 2bit 이다. <표1> 에서 보면 압축키 b부터 표현 가능하다.
두번째 101은 3bit이다. <표1> 에서 보면 압축키 c부터 표현 가능하다.
세번째 1010은 4bit이다. <표1> 에서 보면 압축키 d부터 표현 가능하다.
네번째 1011은 4bit이다. <표1> 에서 보면 압축키 d부터 표현 가능하다.
다섯번째 10은 2bit이다. <표1> 에서 보면 압축키 d로 표현 가능하다.
여섯번째 100은 3bit이다. <표1> 에서 보면 압축키 d로 표현 가능하다.
일곱번째 10100은 5bit이다. <표1>에서 보면 압축키 e부터 표현 가능하다.
일곱번째 데이터에서 압축키 e로 표현가능한데 압축키 e는 5개의 데이터만을 표현할수 있기 때문에
이진수 10까지만 압축하여 표현할수 있다.
000e 00100 10100 00110 01000 01100 xxx ->마지막 3bit 버림
위와 같은 방법으로 하면
10개의 숫자를 8byte로 표현할수 있다.
e 00011 00101 01010 01011 00010 xxx -> 4byte
e 00100 10100 00110 01000 01100 xxx -> 4byte
다음에는 relative-10
'알고리즘' 카테고리의 다른 글
| gamma code (0) | 2007.11.23 |
|---|---|
| ternary search tree (0) | 2007.10.31 |
| Bayes' theorem (0) | 2007.06.03 |
| 비터비(viterbi) 알고리즘 (0) | 2007.05.24 |
| 내가 이해한 색인 압축(index compression) (0) | 2007.03.31 |