Week2. 2–5. Integer Compression Method
수알못(수학을 알지 못하는) 개발자의 UIUC MCS-DS CS410 좌충우돌 해딩기.
2주차 강의 2.5의 내용 중 integer compresion method에 대해
Binary :
equal-length coding
Unary :
x ≥ 1 은 (x — 1)만큼의 1로 + 마지막에 0를 붙임.
예) 2의 경우 (2–1)=1, 즉 1개의 1에다가 0을 뒤에 붙여서(더하는 게 아님) 10.
5의 경우 (5–1)=4, 즉 4개의 1에다가 0을 뒤에 붙여서 11110
그러면 100을 표시하려면? (100–1)=99. 즉 99개의 1에다가 뒤에 0을 붙여야 함. 표시를 위해서는 100비트가 필요. 표시해야 하는 숫자가 1,000 이라면? 10,000이라면?
=> 정확히 그 숫자의 크기만큼의 비트를 사용해야 하므로 큰 숫자의 경우에는 너무나도 비효율적.
unary인코딩된 숫자들의 디코딩은 어떻게 하나? 모든 인코딩 된 숫자의 끝에는 0이 붙이므로 unary인코딩을 읽다가 0을 만나면 그 다음부터 새로운 숫자가 시작된다고 보면 된다. 예를 들어 1101111010 이라고 하면 (110)(11110)(10) 으로 나눌 수 있고, unary가 어떻게 숫자를 인코딩했는지를 생각해보면 각 묶음에서 1의 갯수+1 을 한 것이 원래의 숫자임을 알 수 있다. 즉 110은 1이 2개이므로 2+1 = 3, 11110은 1이 4개이므로 4+1 = 5, 10은 1이 1개이므로 1+1 = 2.
영문 위키피디아 항목을 살펴보면 Unary compressin은 이렇게 표시하는 방법 외에 1 과 0을 바꿔서 표시하는 alternative도 있는 것 같다. 즉 5가 11110 대신에 00001로 표시됨.
감마-코드(γ-code) :
앞에서 살펴본 unary코딩이 큰 숫자의 경우 가운데 1이 너무 많아진다는 걸 보완할 수 있는 코드. 여전히 unary코드를 사용하긴 하지만, 주어진 10진수 n에 대해서 2^k ≤ n < 2^(k+1) 인 k를 찾아서 거기다가 1을 더한 값을 unary 로 표시한다는 게 차이점이다. 알다시피 구해낸 k에다가 1을 더하면 2진수 표시에서 몇번째 digit에 1이 있는지를 알 수 있다( right -> left 스캔 )
10진수의 2진수 변환을 위해 사용하는 2거듭제곱 표현과 실제로 변환된 2진수들을 생각해보면,
1 = 2⁰ => 1
2 = 2¹ => 10
3 = 2¹ + 2⁰ => 11
4 = 2² => 100
5 = 2² + 2⁰ => 101
…
쉽게 패턴을 볼 수 있으리라 생각한다.
3의 예를 들어보면 3 = 2¹ + 2⁰, 제일 높은 지수가 1이므로, 거기다가 1을 더해서 구한 값 2가 이 이진수의 길이이자 leftmost bit 이 1인 값이다. 그래서 2를 unary로 하면 ( 2–1 ) = “1”, 여기다가 “0”을 붙여서 “10”을 구한다.
자 그런데 이렇게만 표시하면 원래의 값인 3과 코딩된 값 2 (우리는 막 2진수 10 을 unary “10”으로 바꿨다 ) 사이에 값 차이, 즉 offset 1이 존재한다. 이걸 바로 직전 구한 unary “10” 에다가 붙여줌. 가장 큰 수를 코딩한 게 두자리였기 때문에 나머지 값 1은 한자리로 표시가능하다. 즉 “10” + “1” = “101”. (2진수의 덧셈이 아니라 string의 concat으로 볼 것)
5의 경우는 어떨까? 2^k ≤ 5 < 2^(k+1)이 되는 k는 2이므로 ( 2 + 1 ) = 3 이고 이 3을 unary로 바꾸면 ( 3–1 ) = 2니까 1을 두번 넣고 0을 붙여서 “110”을 만들면 된다. 처음의 수는 5였고 지금 코딩된 값은 4 (2² ) 니까 1만큼의 offset이 생긴다. 마찬가지로 5의 2진수 표현 중 가장 왼쪽이 3번째 자리였기 때문에 나머지들은 모두 2진수 두자리로 표시가 가능하다. 오프셋이 1이였으므로 “01”. 따라서 앞의 “110” + “01” 을 해서 “11001”을 만든다.
근데 막 눈치챘는가? 감마코드 변환할 때 보면 제일 높은 지수를 구한 다음에 또 1을 더하고 그걸 unary로 변환할때는 다시 1을 빼서 그 갯수만큼 1을 붙이고 마지막에 0을 붙인다.
그러니까 그냥 +1 뒤에 곧바로 -1 하지 말고, 10진수 -> 2거듭제곱 표현시 가장 높은 지수를 구한 다음에 바로 그 갯수만큼 1을 붙이고 0을 붙이면 된다.10을 가지고 연습해 보면10 = 2^3 + 2^1이니까 가장 높은 지수인 3만큼 "111"을 붙이고 그 뒤에 "0"을 만들어서 unary prefix인 "1110" 을 구하고 10 - 2^3 = 2만큼을 뒤쪽에 2진수 세자리를 이용해서 "010"으로 표현해서 붙여주면 된다. 결과는 "111010".5의 경우
5 = 2^2 + 2^0
이므로 가장 큰 지수 2만큼 "11" 하고 뒤에 "0" 붙여서 "110"을 만든다. 그리고 5 - 2^2 = 1이므로 2 digit 2진수를 이용해서 1을 표현한 "01"을 붙임. "11001"
정리하자면 감마코드 변환은
- 주어진 10진수 n에 대해서 2^k ≤ n < 2^(k+1) 이 되는 k를 찾아서
- k갯수만큼 1을 쭉 붙이고 그 뒤에 0을 붙여서 unary prefix 를 만든 다음
- 처음 주어진 10진수 값 n과 2^k 값 의 차이( n — 2^k ) 를 k의 길이를 가지는 2진수를 이용해서 표현, 2단계에서 구한 unary prefix와 붙인다.
5를 가지고 다시 한번 이 변환방법을 따르면
- 2^k ≤ 5 < 2^(k+1) 인 k는 2,
- “11” + “0” = “110” ( unary prefix )
- 5–2² = 1, 이 1을 2자리 이진수로 표시하면 “01”, 이걸 unary prefix와 붙여서 “11001”.
그럼 역변환은 어떻게 하나? 감마코드를 어떻게 만들었는지를 생각해보면 쉽다.
- 주어진 감마코드를 왼쪽에서 오른쪽으로 훑으면서 첫번째 0이 나오는 부분을 찾아 분리한다.(0은 왼쪽 부분에 포함되도록, 왜냐면 이게 unary prefix니깐) 위 5의 예를 들면 “11001” 이니까 “110” 과 “01”로 분리됨.
- 왼쪽부분 110 은 “11” 에 “0”을 붙인 것이고, “11”은 1이 2개 있으니까 이것의 unary변환 전 값은 3이고, 해당 10진수의 2거듭제곱의 가장 큰 값이 2라는 소리다. 2진수로 표시하자면 1?? 인 숫자이다. 아무튼 그래서 2² = 4
- 1단계에서 분리된 값 중 두번째 “01”은 그냥 그 자체로 2진수니까 10진수로 변환하면 1. (또 여기서 한가지, 길이가 2라는 것으로 부터 unary prefix변환된 수는 3자리 2진수라는 걸 알 수 있다)
- 2 단계와 3단계의 결과를 합쳐준다. 4+1 = 5. w00t!
위키피디아 설명 : https://en.wikipedia.org/wiki/Elias_gamma_coding
델타 코드(δ-Code)
다시 한번 이 앞의 5의 예를 들어보자(5야 미안해 ㅠㅠ). 5를 감마코드로 변환했을 때 값이 11001이었다. 이 중에 뒤쪽 uniform code 인 01을 제외한 앞쪽의 unary prefix를 잘 생각해보면 이 값은 2^k ≤ ? < 2^(k+1) 을 만족하는 k값을 unary로 표시한 것이다. 그런데 우리가 처음에 unary를 설명하고 그 다음에 설명한 감마코드가 뭐하는 거였더라? 그렇다, unary 를 좀 더 압축시키기 위한 것이었다. 그러면 이 unary prefix로 표시된 값도 그냥 감마 코드로 표시하면 더 압축이 되지 않을까? 요게 바로 델타 코드의 기본 개념이다.
5의 unary prefix인 110은 1이 2개니까 원래의 변환전 값은 3이라는 소리다. ( unary 변환할 때는 주어진 숫자 — 1 만큼 1을 붙이고 끝에 0을 붙이므로). 자 이제 모든 걸 잊고 단순히 3을 감마코드로 변환해 보자. 어? 우리 아까 저~ 위에 했었다. 값은 “101” 이다. ( 더이상 자세한 설명은 생략한다 ) 그리고 마지막으로 5의 감마코드 변환시 뒤쪽 uniform code가 “01” 이었으므로 이걸 “101” 뒤에다 붙임. 그러면 “10101”.
오늘은 여기까지.
