LZW(엘더-제프리-웰치) 알고리즘은 데이터 압축에 사용되는 사전 기반(dictionary-based) 무손실(lossless) 압축 방법이다. 1984년 아서 레임펨(Arthur Lempel)과 야코프 지브(Jacob Ziv)이 제시한 LZ78 알고리즘을 기반으로, 제프리 웰치(Jeffrey Welch)가 1984년 IBM에서 이를 개선한 형태가 LZW이다. 이름은 Lempel, Ziv, Welch의 이니셜을 따서 명명되었다.
원리
LZW는 입력 데이터 흐름을 순차적으로 읽으며, 현재까지 발견된 문자열 패턴을 사전에 저장한다. 초기 사전은 모든 가능한 단일 기호(예: 8비트 바이트 0 ~ 255)로 구성된다. 이후 새로운 문자열이 기존 사전에 없는 경우, 그 문자열을 사전에 추가하고, 기존에 존재하는 가장 긴 문자열에 대한 사전 인덱스를 출력한다. 이렇게 함으로써 반복되는 패턴을 짧은 코드워드(codeword)로 대체하여 압축 효과를 얻는다.
주요 특성
- 무손실 압축: 원본 데이터를 완전히 복원할 수 있다.
- 고정된 코드폭: 초기에는 가변 길이 코드를 사용하지만, 일반적인 구현에서는 9~12비트의 고정 코드폭을 적용한다.
- 사전 초기화: 사전은 압축과 복원 양쪽에서 동일하게 초기화되므로, 별도의 사전 전송이 필요 없다.
역사와 특허
LZW는 1984년 제프리 웰치가 IBM 연구소에서 발표했으며, IBM은 1985년부터 2003년까지 미국 및 일부 국가에서 특허(US 4558302)를 보유하였다. 특허 기간 동안, LZW를 이용한 포맷(예: GIF)에서는 특허료 문제로 인해 라이선스가 요구되었다. 특허가 만료된 이후에는 자유롭게 사용되고 있다.
응용 분야
- 이미지 포맷: GIF(Graphics Interchange Format), TIFF(Tagged Image File Format) 등에서 색상 표 데이터를 압축하는 데 사용된다.
- 파일 압축 프로그램: UNIX 계열의
compress명령어 등 초기 압축 유틸리티에서 채택되었다. - 통신: 일부 데이터 전송 프로토콜에서 실시간 압축을 위해 활용되었다.
구현 및 성능
LZW는 구현이 비교적 단순하고, 사전 관리에 메모리를 적게 사용한다는 장점이 있다. 압축률은 입력 데이터의 중복도에 크게 좌우되며, 일반 텍스트나 반복적인 그래픽 데이터에서 1.5배~2배 정도의 압축 효율을 보인다. 시간 복잡도는 압축·복원 모두 O(n)이며, 사전 탐색은 해시 테이블이나 트라이(Trie) 구조를 이용해 효율적으로 수행된다.
제한점
- 사전 크기 제한: 코드폭이 제한적이므로 사전 크기가 일정 수준을 초과하면 더 이상 새로운 패턴을 추가하지 못한다. 이는 압축 효율의 한계가 될 수 있다.
- 특정 데이터에 비효율: 이미 압축된 데이터나 무작위성이 높은 데이터에는 압축률이 낮다.
관련 기술
- LZ77, LZ78: LZW와 동일한 Lempel‑Ziv 계열에 속하지만, 압축 방식과 사전 관리 방법이 다르다.
- Deflate: LZ77 기반에 허프만 코딩을 결합한 압축 방식으로, ZIP 및 PNG 등에 사용된다.
LZW는 데이터 압축 분야에서 오랫동안 활용되어 온 표준 알고리즘으로, 특허 만료 이후에는 다양한 소프트웨어와 포맷에서 자유롭게 적용되고 있다.
