25 압축
MSI 의 파일은 캐비닛에, MSIX 의 파일은 ZIP 압축 파일에 담겨 옮겨지고, 둘 다 보통 압축되어 있다: 더 적은 바이트로 쓰이고, 거기서 원래 것이 정확히 되살아난다. 이 장은 둘이 함께 쓰는 방법인 deflate 가 그것을 어떻게 하는지를 실제 예의 비트까지 내려가 보인다.
25.1 데이터를 줄일 수 있는 까닭#
손실 없는 압축이 되는 것은 실제 데이터가 무작위가 아니기 때문이다. 두 가지가 되풀이된다:
- 나열. 프로그램의 기계어는 명령 무늬를 되풀이하고, 글은 낱말을 되풀이하고, 파란 하늘 그림은 같은 색을 되풀이한다.
- 기호, 고르지 않게. 영어 글에서
e는z보다 훨씬 흔하고, 프로그램에서는 바이트00이 아주 흔하다.
deflate 는 둘을 차례로 쓴다: LZ77 이 되풀이된 나열을 짧은 참조로 바꾸고, 이어서 허프만 부호가 흔한 기호를 더 적은 비트로 쓴다.
어느 쪽도 없는 데이터 - 무작위 수, 또는 이미 압축된 데이터(PNG, JPEG 그림, ZIP 파일, 동영상) - 는 줄일 수 없다. 해 보면 시간이 들고 몇 바이트가 늘어난다.
25.2 LZ77: "앞에서 베껴 와라"#
LZ77(Lempel 과 Ziv, 1977년)은 데이터를 처음부터 읽다가, 다음 바이트들이 조금 전에 나온 적이 있으면 대신 뒤 참조를 쓴다: "거리만큼 뒤로 가서 길이만큼 베껴라". 나머지는 글자 그대로(literal) 한 바이트씩 쓴다.
12 바이트 abcabcabcabc 를 보자. deflate 는 이것을 글자 넷과 참조 하나로 쓴다:
literal a
literal b
literal c
literal a
copy: distance 3, length 8베끼는 것은 자기가 만드는 것과 겹쳐도 된다: 3 바이트 뒤로 가면 bca 에 닿고, 한 바이트씩 베끼면 방금 쓴 바이트를 계속 읽게 된다:
written so far: a b c a
^ start 3 back
copy 8: a b c a b c a b c a b c
\_______________/ 8 copied bytes그래서 아무리 긴 반복도 짧은 참조 하나다. deflate 는 거리 32,768 바이트(창)까지, 길이 3 에서 258 까지를 쓴다.
25.3 허프만 부호: 흔한 기호에 짧은 부호#
LZ77 을 지나면 데이터는 기호의 줄이 된다: 글자 바이트, 길이, 거리. 보통의 바이트는 무엇이든 8비트를 쓴다. 허프만 부호는 기호마다 비트 수를 따로 준다 - 잦은 것에는 적게 - 그리고 어떤 부호도 다른 부호의 앞부분이 되지 않게 해서, 읽는 쪽이 언제나 한 부호가 어디서 끝나는지 안다.
기호 넷으로 된 작은 예:
| 기호 | 빈도 | 고정 2비트 부호 | 허프만 부호 |
|---|---|---|---|
| A | 50% | 00 | 0 |
| B | 25% | 01 | 10 |
| C | 12.5% | 10 | 110 |
| D | 12.5% | 11 | 111 |
평균하면 기호 하나에 2비트 대신 0.5 x 1 + 0.25 x 2 + 0.125 x 3 + 0.125 x 3 = 1.75 비트다. ABAD 는 0 10 0 111 이 되고, 0100111 을 왼쪽부터 읽으면 A, B, A, D 로만 읽힌다.
deflate 에는 부호 표가 두 가지다: 표준에 한 번 정해 둔 고정 표(작은 데이터에 좋다)와, 블록마다 그 블록의 기호 수를 세어 만들어 블록 앞에 저장하는 동적 표(큰 데이터에 좋다).
25.4 deflate, 비트 하나하나#
deflate(RFC 1951)는 블록을 쓴다. 블록은 저마다 세 비트짜리 머리로 시작한다:
| 비트 | 뜻 |
|---|---|
| 1비트: BFINAL | 1 = 마지막 블록 |
| 2비트: BTYPE | 0 = 저장(바이트 그대로), 1 = 고정 허프만 부호, 2 = 동적 허프만 부호 |
고정 표의 기호:
| 기호 | 뜻 | 부호 길이 | 부호 |
|---|---|---|---|
| 0-143 | 글자 바이트 0-143 | 8비트 | 00110000 + 기호 |
| 144-255 | 글자 바이트 144-255 | 9비트 | 110010000 + (기호 - 144) |
| 256 | 블록 끝 | 7비트 | 0000000 |
| 257-279 | 길이(와 추가 비트) | 7비트 | 0000001 ... |
| 280-287 | 길이(와 추가 비트) | 8비트 | 11000000 ... |
길이 뒤에는 5비트 거리 부호가 오고, 어떤 부호는 범위 안의 정확한 값을 고르려고 추가 비트를 몇 개 더 붙인다.
abcabcabcabc 를 deflate 로 압축하면 이렇다 - 열두 바이트 대신 일곱 바이트:
4b 4c 4a 4e 84 21 00deflate 는 바이트마다 가장 낮은 비트(비트 0, 2장)부터 채운다. 그 순서로 풀어 쓰면 비트의 줄은:
byte 4b = 01001011 -> bits in order: 1 1 0 1 0 0 1 0
byte 4c = 01001100 -> bits in order: 0 0 1 1 0 0 1 0
...이고, 이렇게 읽힌다:
| 비트(순서대로) | 뜻 |
|---|---|
1 | BFINAL = 1: 마지막 블록 |
1 0 | BTYPE = 1(두 비트를 낮은 비트부터 수로 읽는다): 고정 부호 |
10010001 | 글자 a (0x61 = 97. 00110000 + 97 = 10010001) |
10010010 | 글자 b |
10010011 | 글자 c |
10010001 | 글자 a |
0000110 | 기호 262: 길이 8 |
00010 | 거리 부호 2: 거리 3 |
0000000 | 기호 256: 블록 끝 |
3 + 4 x 8 + 7 + 5 + 7 = 54 비트이고, 일곱째 바이트의 마지막 두 비트는 쓰지 않는다. (허프만 부호만은 deflate 가 부호의 가장 높은 비트부터 쓴다. BTYPE 이나 추가 비트 같은 수는 가장 낮은 비트부터다. 제4부가 모든 표를 적어 두었다.)
25.5 MSZIP: 캐비닛 속의 deflate#
캐비닛(.cab)은 파일 데이터를 32 KiB 이하의 블록으로 나눈다. MSZIP 에서는 블록마다 두 글자 CK(43 4b) 뒤에 deflate 스트림 하나가 오고, 블록은 앞 블록 안을 참조할 수 있다. 원본의 compress = "mszip:6" 은 9 단계 중 6 의 노력으로 하는 deflate 다: 수가 클수록 일치를 더 오래 찾는다 - 결과는 작아지고 시간은 더 든다 - 풀리는 방식은 같다.
25.6 MSIX 속의 deflate#
MSIX 는 ZIP 압축 파일이고, ZIP 은 파일마다 그대로("저장", 방법 0) 또는 deflate 로 압축해(방법 8) 담는다. 튜토리얼의 hello.msix(17장):
| 파일 | 크기 | 패키지 안 | |
|---|---|---|---|
hello.exe | 17,920 | 6,706 | deflate: 37% |
Registry.dat | 8,192 | 430 | deflate: 대부분 0 바이트라 5% |
AppxManifest.xml | 2,960 | 1,010 | deflate: 글이라 34% |
Assets\Square150x150.png | 301 | 301 | 저장: PNG 는 이미 압축되어 있다 |
guide.txt | 6 | 14 | deflate: 너무 작아 얻는 것이 없다 |
마지막 줄이 아주 작은 데이터를 압축하는 비용을 보인다: deflate 블록에는 머리 몇 비트와 끝 부호가 있고, 여섯 바이트에는 되풀이할 것이 없다.
25.7 쓰이는 곳#
- 튜토리얼 15장:
compress,cab,cab-max-size. - 튜토리얼 17장:
--msix-compress. - 제4부: 캐비닛, MSZIP, deflate, MSIX.