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