[06] Data Compression

Coding은 데이터 압축, 암호화, 오류감지 및 수정, 데이터 전송 및 저장에 사용되는 이론이다. 주된 목적은 데이터의 패턴을 분석해서 압축하여 통신을 가능하게 하는 것이다.

 

1. Source coding: Data compression

데이터 압축의 목적으로 사용되는 coding의 경우, 가장 빈번하게 나오는 결과에는 짧은 표현을, 가장 덜 발생하는 결과에는 상대적으로 긴 표현을 주어 압축한다.

(ex. 모스 부호가 한국인에게는 가장 유명하다)

 

Definitions

• Source code란 부호화된 데이터라고 보면된다.
• $c(x)$ : codeword of x
• $l(x)$ : $c(x)$의 길이
• $D*$ : D-ary alphabet으로 만들 수 있는 source code의 집합 (유한한 길이)

 

Code를 평가하는 방법 중 하나는 expected length $L(C)$를 측정하는 방법이다. $L(C)$는 code의 optimality를 확인하는 데 사용된다.

$$ L(C) = \sum p(x)l(x) $$

 

Example.

현재, 4개의 sample을 보여주고 있다. 그러므로 unifom-length codeword라면 $log4$이므로 2 bits임을 알 수 있다. 문제에서 제시하는 code의 경우 $L(C)$를 구해보면 1.75 bits이다. 따라서 그냥 바꾼 것 보다 좋다는 것을 알 수 있다.

 

$X$의 entropy를 구해보면, $H(X)$는 1.75 bits임을 알 수 있다. Entropy는 RV $X$를 최대한 압축한 정보량이므로 codeword compression의 lower bound이다. $H(X)=L(C)$이므로 제시하는 code는 optimal임을 알 수 있다.

 

Example.

풀이는 다 적었다.

 

Example. Morse code

모스부호는 영어에서 가장 많이 사용되는 E나 T에 제일 짧은 부호를 할당하였고 Q나 Z와 같이 덜 사용되는 알파벳에는 긴 부호를 할당하였다.

모스부호의 경우, 태생적으로 모든 부호 사이에 space가 있어 optimal은 아니다.

 

Code에 있어 주요한 개념은 다음과 같다.

• Nonsingularity : x가 다르면 c(x)도 다르다.
• Code extension : c(x)=00, c(y)=11이면 c(xy)=0011이다.
• Uniquely decodable codes : Individual codeword가 unique하면 된다.
• Prefix/instantaneous code : Codeword의 prefix가 다른 codeword가 아니다. (모든 codeword가 구별되기 때문에, 미래의 bit를 확인안해도 된다.)

 

2. Kraft Inequality

D의 알파벳 크기를 가지는 Prefix code라면, 다음의 부등식을 만족한다.

$$ \sum D^{-l_i} \leq 1 $$

 

Converse는 Kraft inequality를 만족하면 해당 $l(x)$로 prefix code를 만들 수 있음을 의미하게 된다.

*증명은 교과서를 보자

 

Kraft inequality는 $\infty$에도 성립한다.

$$ \sum_{i=1}^{\infty} D^{-l_i} \leq 1 $$

 

간단하게 증명하자면 다음 그림처럼 할당할 수 있기 때문이다.

 

그래서 정리하자면 다음과 같다.

• Kraft inequality 만족하면, prefix code가 존재한다.
• Prefix code라면 Kraft inequality를 만족한다.
• Uniquely decodable code는 prefix code보다 codeward length가 길거나 같다.

 

3. Optimal Code

Optimal이 되려면, 길이가 짧으면 장땡이다.

 

그래서 optimal code를 찾기 위한 식은 다음과 같다.

$$ minimize\, L(C) = \sum p_i l_i $$

$$ subject\,to\, \sum D^{-l_i} \leq 1 $$

 

그러나 위 문제는 $l_i$이가 integer이기 때문에 convex optimization을 사용할 수 없다. 그래서 라그랑주 곱셈이랑 KKT로 잘 해결한다. 그래서 다음의 결과를 얻는다. (Shannon code가 된다)

$$ p_i = D^{-l_i} $$

$$ l_i^{*} = -log_Dp_i $$
$$ L^{*} = \sum p_i l_i^{*} = H_D(X) $$

 

이래서 아까 앞에서 entropy가 lower bound라고 언급했었다. 정리하면 다음과 같다.

$$ L \geq H_D(X) $$

with equality iff $p_i = D^{-l_i} $

 

Length의 bound를 구해보자. $ l_i^{*} = -log_Dp_i $였다. $l_i$는 integer임으로 ceiling을 통해 구하게 되고 Kraft inequality를 만족하는지 확인해보면 만족한다.

ceiling을 이용하기 때문에, 모든 $l_i$가 optimal일 때 범위는 다음처럼 제한된다.

$$ H_D(X) \leq L^{*} \leq H_D(X) +1 $$

*shannon code는 optimal이군

4. Compression with Wrong Codes

• source distribution : $p(x)$
• assigned codeword length : $l(x) = ceiling(-log\, q(x))$

$$ H(p) + D(p||q) \leq E_pl(X) < H(p) + D(p||q) + 1 $$

 

q와 p가 다를수록 D(p||q)가 커진다. 이는 곧 code length가 길어짐을 의미하게 된다.

• $p_x = \{0.5, 0.25, 0.125, 0.125\}$
• $H(X) = 1.75$
• $q_x = \{0.25,0.25,0.25,0.25\}$

D(p||q)는 0.25가 되어 codeword length = H(x) + D(p||q) = 2 bits가 된다.

 

5. Huffman Code : Optimal code construction

1. Decreasing order로 확률 줄세우기
2. D-ary면 D개만큼 알파벳 할당하기
3. D개 합치기
4. 반복

Bi-nary case

Average length를 구해보면, 2.3 bits가 나온다.

 

Ter-nary case에 대해서는 다음과 같다. 3개의 least prob.을 합치는 식으로 진행한다.

Ter-nary case

마찬가지로 average length를 구해보면, 1.5 ternary digits이다.

 

두 케이스를 구분하는 방법은 $D^{E[l(x)]}$로 진행한다.

• Bi-nary = $2^{2.3}$ = 4.92
• Ter-nary = $3^{1.5}$ = 5.20

 

근데 하다보면 끝에서 D개가 안남을 수 있다. 이 경우에는 Dummy를 추가해서 구한다.

$1+(D-1)k$로 시작 size를 맞추면 된다. 위 예제는 D=3이므로 k=3을 가정해 7로 시작 size를 맞추었다.

 

Suboptimal way; Fano's construction

이외에도 suboptimal인 Fano의 코드 생성방법이 있다. Prob.을 줄세워서 이등분 할건데, 최대한 양쪽이 비슷한 확률을 가지도록 나누는 것이다. 그래서 하나씩 0과 1을 할당하며 이 방법을 계속 반복한다.

이 방법은 $L(C) \leq H(X) + 2 $가 된다.

 

Optimality of Huffman code

1. Shannon code(sub-optimal)와의 비교

• let $p_x$ = {1/3, 1/3, 1/4, 1/12}
• Then Huffman code length = (2,2,2,2) or (1,2,3,3)
• Then Shannon code = (2,2,2,4)

3번째 친구는 Shannon이 더 좋지만, average length 측면에서는 Huffman(2)이 Shannon(2.17) 보다 좋음

 

Binary Huffman code는 optimal이다. 하지만 많은 다른 optimal code가 있다.

 

2. Optimality 조건

• $p_i > p_j$면 $l_i \leq l_j$이다.
• Two longest codeword는 같은 길이임
• Two longest codeword는 마지막 bit만 다름

잘 생각해보면 저래야 optimal을 달성하며 2번 조건은 사실 의미가 없고 3번의 경우 무조건 만족해야지만 optimal인건 아니다. 

 

어쨋든 Huffman code의 경우 해당 조건을 모두 만족해서 optimal이다.

 

6. Shannon-Fano-Elias codes

누적 확률을 이용해 codeword를 만드는 방법이다.

$$ F(x) = \sum_{a \leq x} p(a) $$

 

간단한 계산을 위해, 수정된 누적합을 사용한다.

$$ F(X) = \sum p(a) + {1 \over 2}p(x) $$

 

$F(X)$는 real number이기 때문에, code로 사용하기 어려움이 있다. 그래서 largest less than F(X) 값으로 사용한다. Prefix free property도 가능하다.

Prefix 문제 해결방법

 

Example.

Binary로 구하는 과정은 다음과 같다고 한다. (챗지피티쓰)

• 0.125를 2진수로 변환합니다. 0.125는 2진수로 0.001입니다.
• 0.125 *2 = 0.25 (0, 소수점 이하가 0.25 남음)
• 0.25 × 2 = 0.5 (0, 소수점 이하가 0.5 남음)
• 0.5 × 2 = 1.0 (1, 소수점 이하가 0 남음)
• 결과: 0.125 (10진수) = 0.001 (2진수)

 

SFE로 만든 code의 경우, average $L(C)$는 2.75 bits이다. Huffman이 1.75 bits였으니 Suboptimal임을 알 수 있다. SFE는 sequence에 적용할 수 있어 Arithmetic coding에 자주 사용된다. 특히 Binary 데이터에 자주 사용된다.

 

7. Competitiveness of Shannon codes

가장 쉬운 방법은 codeword의 길이를 비교하는 것이다. a에 대해서 codeword의 길이가 짧으면 +1, 길면 -1 점수를 부과하는 방식으로 비교할 수 있다.

 

Shannon code가 질 확률은 다음과 같다.

지기 매우 어렵다는 것을 의미한다.

 

Specific case에 대해서는 Shannon code가 optimal임을 보일 수도 있다. 가령 Prob.이 지수승으로 나타나는 dyadic prob. mass function을 distribution으로 가지는 경우이다. ($p(x)=2^{-k}$) 이 경우에 대해서 Shannon code는 $l(x) = l'(x)$ for all x가 아닌 이상 항상 더 좋다.