Lempel-Ziv Coding
렘펠-지브 압축
렘펠-지브 압축은 데이터 압축 기법중 하나입니다.
간단히 어떠한 방식으로 압축이 되는지 알아보겠습니다.
예를들어 taccagtaccagtaccacta# 라는 메세지를 압축하려 합니다.
여기서 마지막 # 문자는 임의로 정하여 문장의 마침을 알리는 표식으로 사용하겠습니다.
렘펠-지브의 압축방식의 핵심은
사전을 사용한다는 것입니다.
문자를 압축시킬때
사전에 한번도 등록되지 않은 문자를 번호표와 함께 사전에 넣는것입니다.
단, 압축의 시작에 앞서 사전에는 0번째 단어가 존재합니다.
즉, 사전은 언제나 0번째 번호표와 null을 뜻하는 <> 문자가 포함됩니다
이는 이론적일뿐, 실전 코드에선 그냥 빈 문자나 문장이 되겠습니다.
제가 방금 예제로 taccagtaccagtaccacta# 라는 문장을 압축한다 하였는데요,
첫글자부터 살펴봅시다.
첫글자는 t 이고 사전에 한번도 등록되지 않았습니다.
자, 0번이 이미 존재하니 t는 1번이 되겠습니다.
그럼 사전은
번호 단어 압축
-------------------------
0 <> none
1 t (0, t)
위의 사전표를 보시면 압축란에 (0, t)이라고 되있는데요,
t는 분명 1번인데 왜 압축엔 0을 쓰는것일까요?
그건 바로 압축에서의 이 번호는 선행 문자를 뜻합니다.
여기서 렘펠-지브의 압축이 빛을 보는 것이지요.
한번이라도 사전에 등록된 단어는 전부다 쓰지않고
단순히 번호를 붙임으로써 사전에서 뽑아 쓰면됩니다.
그럼 다르게 생각해보면 반복적인 문자가 많으면 많을수록,
압축하려는 문자가 길면 길수록 빛을 보겠죠?
제가 실험했을때는 단순히 텍스트 파일이 1메가만 넘어도 압축의 효율이 보였습니다.
자 그럼 다음 문자는 a입니다. 역시 사전에 없죠. 등록해줍시다.
그 다음 c도 없습니다. 이것 역시 등록해 줍시다.
번호 단어 압축
-------------------------
0 <> none
1 t (0, t)
2 a (0, a)
3 c (0, c)
그 다음문자는 c인데..c는 이미 등록이 됬습니다. 번호는 3번이네요,
만약 사전에 등록이 되있다면 다음 문자도 같이 봐줍니다. a군요.
그러면 이번 문자는 ca가 되겠습니다. 사전에 없으니 등록해야겟죠?
번호 단어 압축
-------------------------
0 <> none
1 t (0, t)
2 a (0, a)
3 c (0, c)
4 ca (3, a)
보셨나요? ca에서 마지막 문자를 뺀 앞문자 (이경우 c)는 이미 사전에 등록되있기 때문에 번호표를 대신 붙여줍니다.
그럼 마저 사전을 채워봅시다.
번호 단어 압축
-------------------------
0 <> none
1 t (0, t)
2 a (0, a)
3 c (0, c)
4 ca (3, a)
5 g (0, g)
6 ta (1, a)
7 cc (3, c)
8 ag (2, g)
9 tac (6, c)
10 cac (4, c)
11 ta# (6, #)
자, 그럼 압축된 문자는 이렇습니다.
(0, t) (0, a) (0, c) (3, a) (0, g) (1, a) (3, c) (2, g) (6, c) (4, c) (6, #)
본래의 문장은
taccagtaccagtaccacta#
이구요.
뭔가 더 길어졌죠?
네, 렘펠-지브 압축 방식은 반복적인 문자가 적을수록, 압축할 양이 적을수록 비효율적입니다.
방금 압축한 예제 처럼요.
'공학 > 기타 컴퓨터 정보' 카테고리의 다른 글
| 컴퓨터 프로그램이 실행되기 까지의 과정 (3) | 2013.02.23 |
|---|