파일 압축

1. 파일은 바이트 단위로 기록된다.

 

⒜파일에 저장되는 데이터의 단위는 바이트다. 파일 크기를 KB 등의 단위로 나타내는 것도 

이 때문이다. 

 

바꿔 말하면 파일은 바이트의 집합체라고 할 수 있다. 

1바이트로 표현할 수 있는 데이터는 256가지이며, 2진수로 00000000 ~ 11111111의 범위를 

갖는다. 이 데이터가 문자를 나타낸다면 문서 파일이 되고, 그림을 나타낸다면 그림 파일이 되는 것이다. 하지만 파일은 바이트 단위의 데이터가 연속적으로 저장되어 있는 것임은 같다.

 

 

⒜파일(file): 디스크 등의 기록 매체에 데이터를 저장한 것

 

 

 

 

2. 런 렝스 코딩

 

'AAAAAAAABBBBCCCCCCDDDDD'를 저장한 텍스트 파일이 있다고 하자.

알파벳 하나의 크기는 1바이트이므로 이 파일의 크기는 22바이트다.

이 파일을 압축하기 위해서 다음과 같은 방식을 생각해볼 수 있다.

 

A7B3C6D5

 

문자의 뒤에 그 문자의 반복횟수를 씀으로써 22바이트에서 8바이트로 줄였다.

이런 압축 기법을 런 렝스 코딩(Run Length Coding)이라 한다.

참고로 그림 파일 역시 바이트의 집합이므로 이 기법으로 압축할 수 있고, 실제로 FAX 등에서 쓰이고 있다. G3라는 규격을 사용하는 FAX에서는 문자와 그림을 모두 흑백으로 보낸다. 이 경우 검정색 아니면 흰색의 데이터가 반복되므로 반복 횟수만을 써서 압축할 수도 있다.

 

하지만 런 렝스 코딩은 반복되는 데이터가 적은 경우 효율이 떨어진다는 한계가 있다.

그림 파일과 같이 반복되는 데이터가 많은 경우 효과를 발휘하지만, 문서 파일의 경우 오히려 파일의 크기가 더 커질 수 있다.

 

예를 들어 'I am Groot.'를 런 렝스 코딩으로 압축한다면 다음과 같이 파일의 크기가 더 커진다.

 

I am Groot. (11 byte)

I1 1a1m1 1G1r2t1.1 (18 byte)

 

이 경우 ⒝압축률은 164%가 된다.

 

런 렝스 코딩을 문자 단위가 아닌 문자열 단위로 압축하는 방법도 있다.

예를 들어 'This is tree.'에서는 'is'가 두 번 반복되고 있다.

 

 

⒝압축률: (압축 전 파일 크기 ÷ 압축 후 파일 크기) × 100

 

 

 

 

3. 허프만 코딩

 

허프만 코딩(Huffman Coding)은 1952년 허프만(D. A. Huffman)이 고안한 압축 기법으로, 실제로 ⒞LHA라는 압축 소프트웨어에서 사용되고 있는 기법이다.

 

문서 파일은 여러 종류의 문자로 구성되며, 각 문자의 사용 횟수는 다르다.

그렇다면 사용 횟수가 많은 문자는 8보다 적은 비트 수, 예를 들어 3비트로 나타내고, 

사용횟수가 많은 문자는 8보다 많은 비트 수, 예를 들어 11비트로 나타내면 어떨까?

 

문서 파일에 60개의 A와 2개의 Z가 있다고 하자. 이 경우 파일의 크기는 62 × 8 = 496비트다.

하지만 A를 3비트로, Z를 11비트로 나타낸다면 3 × 60 ＋ 11 × 2 = 202비트가 된다.  

 

단, 디스크는 1바이트 단위로 데이터를 기록하므로 파일로 저장될 때는 모두 

1바이트 단위로 묶여 저장된다.

 

 

⒞LHA: 일본의 요시자키 하루야스가 개발한 압축 소프트웨어로, 무료로 공개되어 있다. 압축 파일의 확장명은 lha.

 

 

 

 

 

4. 허프만 트리

 

모스 부호는 각 문자가 일반적인 문서에서 나타나는 빈도를 기준으로 데이터 길이를 정한다.

그러나 이것이 모든 경우에 최적화되는 체계는 아닐 것이다.

 

허프만 코딩에서는 압축할 파일마다 최적의 부호 체계를 구축하고, 이를 기준으로 압축한다.

따라서 허프만 코딩으로 압축되는 파일에는 허프만 코드 정보와 압축된 데이터가 함께 저장된다.

 

문자열 AAAAAABBCDDEEEEEF를 허프만 코딩으로 압축해보자.

 

빈도수가 큰 것부터 오름차순으로 나타내면 A, E, D, B, F, C다.

자주 사용되는 방법은 A부터 C까지 0, 1, 10, 11, 100, 101을 부여하는 것이다.

하지만 이 경우 101이 C인지, DE인지 EAE인지 구분할 수 없다.

 

때문에 허프만 코딩에서는 허프만 트리(Huffman tree)를 이용해 부호 체계를 구축해야 한다.

실제로 나무(tree)는 뿌리에서 줄기가 나고, 줄기에서 가지가 나고, 가지에서 잎이 나지만

허프만 트리는 반대로 뿌리가 가장 나중에 생긴다.

허프만 트리는 다음의 절차를 거쳐 만들어진다.

 

① 데이터의 반복 횟수를 기록한다.

 

 

 

② 나타난 횟수가 적은 문자 두 개를 가지처럼 연결한 후 그 위에 횟수의 합을 적는다.

 

 

 

③ 과정 ②를 반복한다.

 

 

 

④ 왼쪽 가지에는 0, 오른쪽 가지에는 1을 쓴다. 그리고 뿌리부터 각 데이터까지의 경로 상의 

    숫자를 차례로 적는다. 이 숫자가 허프만 코드가 된다.

 

 

 

이 과정을 거치면 AAAAAABBCDDEEEEEF는 0000000000001001001101011010101010101111이 된다. 이는 40비트 = 5바이트다. 따라서 압축률은 (5 ÷ 17) × 100 = 29%가 된다.

 

 

 

 

 

5. 손실 압축과 무손실 압축

 

그림 파일에 쓰이는 포맷으로는 ⒟BMP, ⒠JPEG, ⒡TIFF, ⒢GIF 등이 있다. 이 중 BMP는 데이터가 압축되지 않는 방식이다. BMP 외의 대부분의 그림 파일은 압축되어 있다.  

 

그림 파일의 경우 런 렝스 코딩과 허프만 코딩이 아닌 다른 방법을 생각해볼 수 있다. EXE 파일이나 문서 파일과 달리 대부분의 그림 파일은 압축 후의 그림 파일을 압축 전의 상태로 완벽하게 되돌릴 필요가 없기 때문이다. 따라서 ZIP이나 LHA와 같은 ⒣무손실 압축을 할 필요가 없다.

그러니까 압축된 파일이 ZIP이나 LHA 파일일 경우 복원했을 때 압축 전의 상태와 동일하지만,

JPEG나 GIF 파일일 경우 복원해도 일부 정보가 누락되어 있기 때문에 압축 전의 상태와 다르다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

⒟BMP(BitMaP): 모니터나 프린터가 출력하는 비트에 데이터를 그대로 매핑할 수 있는 그림 파일 포맷.

⒠JPEG(Joint Photographic Experts Group): 디지털 카메라에 이용되는 그림 파일 포맷.

⒡TIFF(Tag Image File Format):  태그(tag)라는 식별 기호를 가진 파일 포맷.

⒢GIF(Graphic Interchange Format): 미국의 Compuserve가 개발한 그림 파일 포맷. 컬러 수가 256가지로 제한되어 있다.

⒣무손실 압축: 압축 전의 상태로 되돌릴 수 있는 압축 방식. 압축 전의 상태로 되돌릴 수 없는 방식은 손실 압축이라 한다.