(컴퓨터공학입문) 008. 텍스트 압축

텍스트 압축

“AAAAA” 라는 문자열이 있다고 하자.

얼마 안되는 길이기때문에 이를 그대로 저장해도 되겠지만, 만약 길이가 수십만이라도 그냥 저장하는 것이 좋을까?

당연하겠지만 데이터를 저장하거나 전송할 때는 데이터의 크기를 줄이는 것이 효율적이다.

본 포스팅에서는 데이터의 크기를 줄이기 위한 방법 중 하나인 텍스트 압축 기술에 대해서 알아보자.

1. RLE 방식 (Run-length encoding)

압축의 원리를 이해하기 위한 가장 간단한 방법으로 RLE가 있다.

아래와 같은 문자열이 있다고 가정하자.

AAAAAAABBCCCDEEEEFFFFFFG

하나의 문자를 표현하는 데 1바이트가 필요하므로 위의 문자열은 24바이트를 차지하게 된다.

따라서 데이터를 압축했다고 판정하려면 24바이트 보다 사이즈가 줄어들면 된다.

이때 문자열을 문자와 반복횟수로 표현하는 방법을 사용할 수 있는데, 이를 RLE라고 한다.

RLE를 적용하면 아래와 같이 표현된다.

A7B2C3D1E4F6G1

24바이트를 14바이트로 인코딩하였으므로 데이터 압축을 성공했다고 할 수 있다.

다만 이 방식은 반복되는 문자열이 거의 없다면 오히려 원문보다 크기가 커질 수가 있으므로 주의해야한다.

2. 허프만 코딩 (Huffman coding)

허프만 코딩은 대부분의 압축프로그램에서 사용하는 방법이다.

사용 빈도를 기준으로 빈도가 높은 문자는 적은 비트로 된 코드로 변환하고, 빈도가 낮은 문자는 많은 비트된 코드로 변환하는 방식이다.

이 방식을 사용하면 전체 데이터를 표현하는 데 필요한 비트가 줄어들게 된다.

위의 설명에 나오듯이 허프만 코딩을 사용하려면 압축 대상이 되는 데이터마다 효율적인 압축을 할 수 있게끔 특정 체계에 따라서 압축해야한다.

이때 특정 체계란 데이터마다 각 문자에 대한 특정 코드가 정해져야하는데 이를 관리하는 것을 허프만 트리(Huffman tree) 라고 한다.

위의 RLE 방식에서 썼던 예제를 허프만 코딩 방식으로 처리해보자.

AAAAAAABBCCCDEEEEFFFFFFG

(1) 데이터 내 문자들에 대한 빈도수를 구한다.

문자	빈도
A	7
B	2
C	3
D	1
E	4
F	6
G	1

(2) 빈도를 기준으로 내림차순으로 정렬한다.

문자	빈도
A	7
F	6
E	4
C	3
B	2
D	1
G	1

(3) 낮은 빈도를 가진 문자를 기준으로 이진 트리를 구성한다.

graph TD
  A(14)
  B(A:7)
  C(7)
  D(4)
  E(C:3)
  F(B:2)
  G(2)
  H(D:1)
  I(G:1)
  J(10)
  K(F:6)
  L(E:4)
  M(24)
  M --- A
  M --- J
  A --- B
  A --- C
  C --- D
  C --- E
  D --- F
  D --- G
  G --- H
  G --- I
  J --- K
  J --- L

(4) 각 가지에 코드를 부여한다.

왼쪽 가지엔 0, 오른쪽 가지엔 1을 부여하여 코드를 부여한다.

graph TD
  A(14)
  B(A:7)
  C(7)
  D(4)
  E(C:3)
  F(B:2)
  G(2)
  H(D:1)
  I(G:1)
  J(10)
  K(F:6)
  L(E:4)
  M(24)
  M-- 0 ---A
  M-- 1 ---J
  A-- 0 ---B
  A-- 1 ---C
  C-- 0 ---D
  C-- 1 ---E
  D-- 0 ---F
  D-- 1 ---G
  G-- 0 ---H
  G-- 1 ---I
  J-- 0 ---K
  J-- 1 ---L

(5) 각 코드를 붙여가면서 각 문자별로 허프만 코드를 정의한다

문자	빈도	허프만 코드	비트 수
A	7	00	2
F	6	01	2
E	4	11	2
C	3	011	3
B	2	0100	4
D	1	01010	5
G	1	01011	5

(6) 원문을 허프만 코드로 변환한다.

// Before
AAAAAAABBCCCDEEEEFFFFFFG // 24bytes = 192bits
// After
0000000000000001000100011011011010101111111101010101010101011 // 61bits

192비트의 데이터가 61비트만큼 줄어든 것을 확인할 수 있다.