number unary code length offset r code
--------------------------------------------------------------------------------------
0000 0
0001 10 0 0
0002 110 10 0 10,0
0003 1110 10 1 10,1
0004 11110 110 00 110,00
0009 1111111110 1110 001 1110,001
0013 1110 101 1110,101
0024 11110 1000 11110,1000
0511 111111110 11111111 111111110,11111111
1025 11111111110 0000000001 11111111110,0000000001
0009 1111111110 1110 001 1110,001
9는 1110 001로 인코딩 된다.
이걸 역으로 따라가면
우선 1110 마지막 영은 구분을 위해서 필요한것이기 때문에 제거
그러면 111 = 7
다음 001 = 1
7 + 1 = 8
처음 0을 저장하는 공간을 절약하기 위해서 인코딩하는 숫자에서 1을 뺀값을 인코딩한다.
다시 말하면 9 = 7 + 1 + 1
0013 1110 101 1110,101
그럼 13의 경우는
13에서 우선 1을 빼면 12가 된다.
1110,101 에서 처번째 111은 =7이되고
101 = 5
13 = 7 + 5 + 1
1025 11111111110 0000000001 11111111110,0000000001
1025는
1025에서 1을 빼고 1024
0000000001 = 1
1111111111 = 1024
1025 = 1024 + 1 + 1
length를 결정하는건 log함수를 이용한다.
1025의 경우
log1025 = 10
구분자 1
length = 11자리
마지막 1자리를 0으로 하고 앞부분은 모두 1로
나머지는
1025 - 2^(log1025) = 1025 - 2^10 = 1025 - 20 = 1005
log1025 = 10자리..
열라 복잡하다...
--- 작업중 ---
'알고리즘' 카테고리의 다른 글
| Expectation Maximization (0) | 2008.09.15 |
|---|---|
| index-compression( relative-10 ) (0) | 2007.12.14 |
| ternary search tree (0) | 2007.10.31 |
| Bayes' theorem (0) | 2007.06.03 |
| 비터비(viterbi) 알고리즘 (0) | 2007.05.24 |