LZ77
LZ77은 이전에 나타난 데이터를 미끄러지는 창에서 찾아 거리·길이 참조로 치환한다 무손실 사전 압축 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다.
| 분류 | 알고리즘 · 무손실 사전 압축 |
|---|---|
| 주요 목적 | 이전에 나타난 데이터를 미끄러지는 창에서 찾아 거리·길이 참조로 치환한다 |
| 핵심 방법 | 현재 입력 위치에서 이전 윈도우의 가장 긴 일치 부분을 검색하고 (distance,length)와 다음 문자 등의 토큰으로 표현한다 |
| 복잡도 | 압축 속도는 일치 검색 자료구조와 창 크기에 따라 달라지며 복호화는 출력 길이에 비례 |
| 적용 조건 | 창의 크기, 일치 길이·오프셋과 참조 중첩의 의미를 정확히 정의해야 한다 |
| 참고 자료 | 기술 자료 |
| 관련 분야 | 자료구조, 계산 복잡도 |
LZ77은 이전에 나타난 데이터를 미끄러지는 창에서 찾아 거리·길이 참조로 치환한다 무손실 사전 압축 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다.[1]
핵심 작동은 다음과 같다. 현재 입력 위치에서 이전 윈도우의 가장 긴 일치 부분을 검색하고 (distance,length)와 다음 문자 등의 토큰으로 표현한다. 복호기는 이미 복원한 출력에서 참조해 바이트를 재생성한다. 이 절차에서 각 단계에 유지되는 값의 의미를 정의하고 자료구조 또는 수치 표현에 따라 처리 순서를 구현한다.
계산 특성은 압축 속도는 일치 검색 자료구조와 창 크기에 따라 달라지며 복호화는 출력 길이에 비례 실제 구현에는 창의 크기, 일치 길이·오프셋과 참조 중첩의 의미를 정확히 정의해야 한다 단계마다 유지되어야 하는 불변식, 종료 조건과 입력 경계를 검사하면 수학적 모델을 프로그램의 동작과 연결할 수 있다.
활용과 다른 기법과의 관계에서는 1977년 Abraham Lempel과 Jacob Ziv가 발표한 사전 압축의 기초이며 DEFLATE, zlib 등의 계보에 활용된다. 실제 시스템에서는 시간·메모리 사용, 입출력 비용, 정밀도와 저장 형식이 성능에 영향을 줄 수 있다. 필요한 경우 가장 작은 입력과 중복·퇴화 상태도 시험해야 한다.[2]