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"

정리하자면 감마코드 변환은

1. 주어진 10진수 n에 대해서 2^k ≤ n < 2^(k+1) 이 되는 k를 찾아서
2. k갯수만큼 1을 쭉 붙이고 그 뒤에 0을 붙여서 unary prefix 를 만든 다음
3. 처음 주어진 10진수 값 n과 2^k 값 의 차이( n — 2^k ) 를 k의 길이를 가지는 2진수를 이용해서 표현, 2단계에서 구한 unary prefix와 붙인다.

5를 가지고 다시 한번 이 변환방법을 따르면

1. 2^k ≤ 5 < 2^(k+1) 인 k는 2,
2. “11” + “0” = “110” ( unary prefix )
3. 5–2² = 1, 이 1을 2자리 이진수로 표시하면 “01”, 이걸 unary prefix와 붙여서 “11001”.

그럼 역변환은 어떻게 하나? 감마코드를 어떻게 만들었는지를 생각해보면 쉽다.

1. 주어진 감마코드를 왼쪽에서 오른쪽으로 훑으면서 첫번째 0이 나오는 부분을 찾아 분리한다.(0은 왼쪽 부분에 포함되도록, 왜냐면 이게 unary prefix니깐) 위 5의 예를 들면 “11001” 이니까 “110” 과 “01”로 분리됨.
2. 왼쪽부분 110 은 “11” 에 “0”을 붙인 것이고, “11”은 1이 2개 있으니까 이것의 unary변환 전 값은 3이고, 해당 10진수의 2거듭제곱의 가장 큰 값이 2라는 소리다. 2진수로 표시하자면 1?? 인 숫자이다. 아무튼 그래서 2² = 4
3. 1단계에서 분리된 값 중 두번째 “01”은 그냥 그 자체로 2진수니까 10진수로 변환하면 1. (또 여기서 한가지, 길이가 2라는 것으로 부터 unary prefix변환된 수는 3자리 2진수라는 걸 알 수 있다)
4. 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”.

오늘은 여기까지.