LZW
LZW은 입력에서 등장하는 문자열을 사전에 동적으로 등록하여 문자열을 코드로 표현한다 무손실 사전 압축 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다.
| 분류 | 알고리즘 · 무손실 사전 압축 |
|---|---|
| 주요 목적 | 입력에서 등장하는 문자열을 사전에 동적으로 등록하여 문자열을 코드로 표현한다 |
| 핵심 방법 | 초기 기호 사전에서 출발해 가장 긴 현재 문자열의 코드를 출력하고 그 문자열과 다음 기호의 결합을 사전에 추가한다 |
| 복잡도 | 일반적으로 입력 길이에 비례한 인코딩·복호화 가능하지만 사전 탐색 구현에 따라 달라짐 |
| 적용 조건 | 초기 사전·코드 폭 확장·사전 초기화 또는 리셋 규칙을 송수신 측에서 공유해야 한다 |
| 참고 자료 | 기술 자료 |
| 관련 분야 | 자료구조, 계산 복잡도 |
LZW은 입력에서 등장하는 문자열을 사전에 동적으로 등록하여 문자열을 코드로 표현한다 무손실 사전 압축 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다.[1]
핵심 작동은 다음과 같다. 초기 기호 사전에서 출발해 가장 긴 현재 문자열의 코드를 출력하고 그 문자열과 다음 기호의 결합을 사전에 추가한다. 복호기도 출력 과정에서 같은 사전을 재구성한다. 이 절차에서 각 단계에 유지되는 값의 의미를 정의하고 자료구조 또는 수치 표현에 따라 처리 순서를 구현한다.
계산 특성은 일반적으로 입력 길이에 비례한 인코딩·복호화 가능하지만 사전 탐색 구현에 따라 달라짐 실제 구현에는 초기 사전·코드 폭 확장·사전 초기화 또는 리셋 규칙을 송수신 측에서 공유해야 한다 단계마다 유지되어야 하는 불변식, 종료 조건과 입력 경계를 검사하면 수학적 모델을 프로그램의 동작과 연결할 수 있다.
활용과 다른 기법과의 관계에서는 Terry Welch가 1984년 발표했으며 GIF와 초기 압축 형식 등에 채택되었다. LZ77의 거리 참조와는 다른 사전 코드 방식이다. 실제 시스템에서는 시간·메모리 사용, 입출력 비용, 정밀도와 저장 형식이 성능에 영향을 줄 수 있다. 필요한 경우 가장 작은 입력과 중복·퇴화 상태도 시험해야 한다.[2]