[Algorithm] LZW (Lempel-Ziv-Welch) 구현

Algorithm

[Algorithm] LZW (Lempel-Ziv-Welch) 구현

비번변경 2023. 12. 22. 19:47

LZW

LZW (Lempel-Ziv-Welch)는 Abraham Lempel, Jacob Ziv와 Terry Welch 만든 공통 무손실 데이터 압축 알고리즘이다. 1978년에 Lempel과 Ziv가 공개한 LZ78 알고리즘을 1984년에 Welch가 개선하여 공개했다. 구현이 간단하고 높은 처리량을 제공할 수 있다. 유닉스 파일 압축 유틸리티인 compress의 알고리즘이며 GIP 이미지 포맷에도 사용된다.

핵심 아이디어는 데이터 공간을 절약하기 위해 패턴을 만들어서 재사용하는 것이다. 일반적으로 ASCII Code는 문자를 8bit로 나타내므로 최대로 표현할 수 있는 문자의 개수는 256개이다. 여기서 LZW는 문자를 9~12bit까지 확장하여, 총 4096개 공간 중 기본 문자 256개 공간을 제외한 3840개의 공간을 추가로 사용해 문자를 표현한다. 추가 문자 표현 공간에는 한 번 이상 나온 문자의 결합이 저장된다.

즉, 문자를 순서대로 읽으면서 문자열로 그룹화하여, 그룹화한 문자열을 코드로 변환하여 사용하는 것이다.

이 글에서는 간단히 대문자를 압축할 수 있는 정도로 구현해본다.

압축

압축은 아래와 같은 순서로 동작한다.

길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다.
w에 해당하는 사전 색인 번호를 출력하고, 입력에서 w를 제거한다.
입력에서 처리되지 않는 다음 글자 c가 남아있으면, w+c를 사전에 등록한다.
단계 2로 돌아간다.

위 알고리즘을 Python으로 구현하면 다음과 같다.

의사코드

    w = NIL;
    add all possible charcodes to the dictionary
    for (every character c in the uncompressed data) do
        if ((w + c) exists in the dictionary) then
            w = w + c;
        else
            add (w + c) to the dictionary;
            add the dictionary code for w to output;
            w = c;
        endif
    done
    add the dictionary code for w to output;
    display output;

def encode(msg):
    w = ''
    zip_dict = {i: ord(i) for i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'}
    answer = []
    for c in msg:
        list_keys = zip_dict.keys()
        if w + c in list_keys:
            w = w + c
        else:
            zip_dict[w + c] = max(zip_dict.values()) + 1
            answer.append(zip_dict[w])
            w = c
    answer.append(zip_dict[w])
    return answer

실행 결과 )

메시지 BABAABAAA를 압축했을 때, 사전과 그 결괏값은 아래와 같다.

# 사전
{'A': 65, 'B': 66, 'C': 67, 'D': 68, 'E': 69, 'F': 70, 'G': 71, 'H': 72, 'I': 73, 'J': 74, 'K': 75, 'L': 76, 'M': 77, 'N': 78, 'O': 79, 'P': 80, 'Q': 81, 'R': 82, 'S': 83, 'T': 84, 'U': 85, 'V': 86, 'W': 87, 'X': 88, 'Y': 89, 'Z': 90, 'BA': 91, 'AB': 92, 'BAA': 93, 'ABA': 94, 'AA': 95}

# 결괏값
[66, 65, 91, 92, 65, 95]

압축 해제

반대로 압축 해제는 다음과 같은 순서로 동작한다.

길이가 1인 모든 단어를 포함하도록 사전을 초기화한다.
다음 인코딩 기호를 읽고, 사전에 인코딩 되어 있는지 확인한다.
- 참:
  1. 해당 문자열 W를 출력한다.
  2. 이전 문자열과 W의 첫 번째 기호와 연결한 값을 사전에 추가한다.
- 거짓:
  1. 이전 문자열과 이전 문자열의 첫번째 기호를 연결한 값을 변수 V에 저장한다.
  2. V를 사전에 추가하고 출력한다.
입력이 끝날 때까지 단계 2로 돌아간다.

위 알고리즘을 Python으로 구현하면 다음과 같다.

def decode(li):
    zip_dict = {i: ord(i) for i in 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'}
    entry = {v: k for k, v in zip_dict.items()}[li.pop(0)]  # 현재 문자열
    result = entry  # 결괏값
    w = entry  # 이전 문자열

    for i in li:
        index = max(zip_dict.values()) + 1
        if i in zip_dict.values():
            entry = {v: k for k, v in zip_dict.items()}[i]
            zip_dict[w + entry[0]] = index
        else:
            entry = w + w[0]
            zip_dict[entry] = index
        result += entry
        w = entry
    return result

실행 결과 )

메시지 BABAABAAA를 압축한 값을 다시 압축해제해 본다.