Dictionary Code   사전 코드

(2019-02-06)

Lempel-Ziv-Welch, LZW 부호화, LZ 부호화, 렘펠 지브 부호화

1. 사전 코드 (Dictionary Code)호프만 부호화 또는 산술 부호화는 사전에 심볼의 발생 확률를 정확히 알아야 하나,
     - 대부분의 응용에서는 심볼의 발생 확률을 미리 알지 못함
     - 따라서, 미리 심볼확률분포를 알 필요없는 부호화 방법이 필요함

  ㅇ 결국, 정보 소스로부터 실시간으로 심볼의 발생 패턴을 표(사전)로 만들고,
     - 표의 인덱스부호화하는 방식
     - 여기서, 사전이란, 이전/직전에 부호화시퀸스의 일부를 말함


2. 사전 코드 분류

  ㅇ 고정적 사전 (Static Dictionary)
     - 부호화 이전에 소스에 대한 정보를 가지고 일람표 구성
        . 例) Digram 부호화 등

  ㅇ 적응적 사전 (Adaptive Dictionary)
     - 입력되는 그 자체를 가지고 그것에 적응적으로 일람표를 구성하여 부호화/복호화
        . 例) LZ 부호화 등
     * 대부분의 적응적 사전 기술은 Abraham Lampel, Jacob Ziv에 의해 1977,1978년에 개발됨


3. LZ 부호화 (Lempel-Ziv)

  ㅇ 이전에 받았던 일련의 입력을 마치 사전 처럼 사용 (dictionary-based 구조)
     - 부호화 과정에서 새로 나오는 문자열을 사전식(dictionary)으로 부호화한 표로
       설계한 후에 다음 문자의 부호화에 활용
     - 여러 문자들을 묶은 가변길이 문자열을 가변길이 부호로 표현

  ㅇ LZ77 (LZ1) 부호화
     - 일치하는 문자열의 상대적인 위치와 일치하는 길이 만을 저장
        . < o, l, c > 
           .. o : 오프셋
           .. l : 일치하는 심볼의 길이 
           .. c : 현재 탐색버퍼에 일치하는 심볼 바로 다음에 있는 심볼부호어
     - 탐색버퍼(search buffer),사전탐색버퍼(look-ahead buffer),이동창(sliding window)
       등을 갖음
        . 탐색버퍼 : 최근에 부호화심볼 일부를 포함 (사전 역할). 
                     이미 부호화된 시퀸스. 수천 바이트 정도의 길이를 갖음.
        . 사전탐색버퍼 : 앞으로 부호화될 시퀸스 일부를 포함.
                         수십 바이트 정도의 길이를 갖음 
        . 이동창 : 이동창을 이동시키며 탐색. 이동창을 통해 입력 시퀸스를 조사.
                   보통 30 바이트 정도.
        . 일치하는 길이 : 일치하는 가장 긴 문자열의 길이 (가장 긴 일치)
     - PKZip, Zip, LHarc, PNG, ARJ 등 일반적으로 사용되는 압축 방법들이 모두
       가변길이코드에 기반을 둔 LZ77 방법을 사용하고 있음

     - ... (작성중) ...

  ㅇ LZ78 (LZ2) 부호화
     - 탐색버퍼를 사용치 않고 사전을 만들어 사용

     - ... (작성중) ...

  ㅇ LZW 부호화
     - Terry Welch가 LZ77,LZ78 알고리즘을 응용한 방법으로, 단지 인덱스 만을 부호화

     - ... (작성중) ...

  * Abraham Lampel, Jacob Ziv, Terry Welch


[소스부호화 (기초)] 1. 소스 부호화 2. 고정 길이 부호 3. 가변 길이 부호(엔트로피 부호화) 4. 호프만 부호 5. 산술 부호화 6. LZW 부호화 7. 연속 길이 부호화

 
        최근수정     요약목록     참고문헌