Dictionary Code   사전 코드

(2021-06-25)

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


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. 연속 길이 부호화  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"