결론부터: LZ77은 슬라이딩 윈도우 기반의 딕셔너리 압축 알고리즘입니다. 핵심 사상은 "이미 처리한 데이터를 사전으로 사용하고, 반복되는 내용을 만나면 역참조한다"입니다. 인코딩 시 삼중쌍 (distance, length, next_char)을 출력합니다. distance만큼 뒤로 역추적하여 일치하는 length 길이의 문자열을 찾고, 그 뒤에 일치하지 않는 문자 next_char를 붙입니다. 11자 문자열 "abracadabra"를 예로 들면, LZ77 인코딩은 단 5개의 삼중쌍만 필요하므로 압축 효과가 매우 큽니다. LZ77은 DEFLATE(ZIP/GZIP/PNG)의 핵심 구성 요소이며, LZSS/LZMA/LZ4 등 현대 압축 알고리즘의 공통 조상입니다. 아래에서는 슬라이딩 윈도우 원리부터 시작해 인코딩 과정을 단계별로 시연합니다.
Huffman 인코딩 원리에 아직 익숙하지 않다면, 먼저 Huffman 인코딩 원리: 압축 알고리즘의 초석을 읽어 보길 권장합니다.
1. 딕셔너리 압축이란 무엇인가
압축 알고리즘은 크게 두 학파로 나뉩니다. 통계 코딩(예: Huffman 인코딩)은 문자 빈도에 따라 가변 길이 코드워드를 할당하고, 딕셔너리 압축은 "포인터 참조"로 반복 내용을 대체합니다. LZ77은 딕셔너리 압축 학파에 속하며, 사전 테이블을 미리 구축하지 않고 이미 처리한 데이터를 암묵적 사전으로 사용합니다. 반복 내용을 만나면 "역참조 포인터"로 이전에 나타난 위치를 가리킵니다.
| 학파 | 핵심 원리 | 대표 알고리즘 | 장점 | 단점 |
|---|---|---|---|---|
| 통계 코딩 | 빈도별 가변 길이 코드 | Huffman, 산술 코딩 | 엔트로피 하한에 근접 | 장거리 반복에 약함 |
| 딕셔너리 압축 | 참조로 반복 내용 대체 | LZ77, LZW, LZMA | 반복 패턴에 능통 | 무작위 데이터에 무력 |
| 하이브리드 코딩 | 딕셔너리+통계 2단계 | DEFLATE, ZSTD | 종합적으로 최적 | 구현이 복잡 |
| 변환 코딩 | 주파수 영역으로 변환 후 양자화 | DCT(JPEG), DWT | 손실 압축 효율 높음 | 정보 손실 발생 |
실제로 가장 널리 쓰이는 압축 알고리즘은 거의 모두 "하이브리드 코딩"입니다. 먼저 LZ77로 반복 패턴을 제거하고, 그 잔차에 Huffman으로 빈도 기반 압축을 수행합니다. DEFLATE는 LZ77 + Huffman의 고전적 조합으로, ZIP, GZIP, PNG에서 폭넓게 사용됩니다.
2. LZ77 알고리즘 원리 상세
LZ77의 핵심은 슬라이딩 윈도우 메커니즘입니다. 윈도우는 두 부분으로 나뉩니다. 검색 버퍼(이미 처리한 과거 데이터)와 룩어헤드 버퍼(아직 처리하지 않은 미래 데이터). 인코딩 시 룩어헤드 버퍼에서 일정 구간을 가져와 검색 버퍼에서 최장 일치를 찾습니다. 찾으면 삼중쌍을 출력하고, 못 찾으면 원본 문자를 그대로 출력합니다.
2.1 슬라이딩 윈도우 구조
슬라이딩 윈도우 크기가 압축 효과를 직접 결정합니다. 윈도우가 클수록 역추적 가능한 과거 데이터가 많아져 일치 확률이 높아집니다. 알고리즘별로 윈도우 크기 차이가 매우 큽니다.
| 알고리즘 | 검색 버퍼 | 룩어헤드 버퍼 | 최대 일치 길이 | 전형적 시나리오 |
|---|---|---|---|---|
| LZ77 원본 | 수 KB | 10여 바이트 | 16바이트 | 교육 예제 |
| DEFLATE | 32KB | 258바이트 | 258바이트 | ZIP/GZIP/PNG |
| LZMA | 8MB(설정 가능) | 273바이트 | 273바이트 | 7z/xz 아카이브 |
| LZ4 | 64KB | 제한 없음 | 제한 없음 | 실시간 압축 |
| ZSTD | 8MB(최대 1GB) | 제한 없음 | 제한 없음 | 현대 범용 |
2.2 삼중쌍 인코딩 형식
LZ77의 출력 단위는 삼중쌍 (distance, length, next_char)이며, 각 필드의 의미는 아래 표와 같습니다.
| 필드 | 의미 | 값 범위(DEFLATE) | 인코딩 비트수 | 예시 |
|---|---|---|---|---|
| distance | 역추적 거리(몇 문자 뒤로 가서 일치 찾기) | 1–32768 | 15 bit | distance=10 → 10자 전으로 이동 |
| length | 일치 길이(연속 일치 문자 수) | 3–258 | 8 bit | length=5 → 5자 일치 |
| next_char | 일치 후의 다음 문자 | 0–255 | 8 bit | next_char='d' → ASCII 100 |
삼중쌍의 교묘함은 일치 종료 후 next_char를 하나 더 출력해 인코더가 항상 최소 1문자 이상 전진하도록 보장한다는 점입니다. 그래서 절대 무한 루프에 빠지지 않습니다. 어떤 일치도 찾지 못했을 때(length=0)는 distance와 length가 모두 0이며 next_char만 출력합니다. 이는 원본 문자 그대로 저장하는 것으로 퇴화합니다.
2.3 일치 검색 전략
일치 검색은 LZ77의 성능 병목입니다. 룩어헤드 버퍼에서 일정 구간을 가져와 검색 버퍼에서 최장 일치를 찾아야 하므로, 무차별 대입은 O(n×m) 복잡도이며, 실제 구현은 해시 테이블이나 접미사 트리로 가속합니다.
| 검색 전략 | 자료구조 | 검색 복잡도 | 공간 오버헤드 | 전형적 응용 |
|---|---|---|---|---|
| 무차별 대입 | 없음 | O(n×m) | 없음 | 교육 예제 |
| 해시 체인 | 해시 테이블+연결 리스트 | 평균 O(n) | 낮음 | zlib(DEFLATE) |
| 해시 버킷 | 해시 테이블+배열 | 평균 O(1) | 중간 | LZ4 |
| 접미사 트리 | 접미사 트리/접미사 배열 | 최악 O(n) | 높음 | LZMA |
3. 실전 예제: "abracadabra" 인코딩 시연
LZ77으로 "abracadabra"(11자)를 완전히 인코딩해 봅니다. 초기 상태에서 검색 버퍼는 비어 있고, 룩어헤드 버퍼는 전체 문자열입니다. 위치를 하나씩 스캔하면서 과거 데이터에서 최장 일치를 찾습니다.
원문: a b r a c a d a b r a
인코딩 과정:
| 단계 | 현재 위치 | 룩어헤드 내용 | 검색 버퍼 조회 | 출력 삼중쌍 | 설명 |
|---|---|---|---|---|---|
| 1 | 위치 1 | abracadabra | 비어 있음, 일치 없음 | (0, 0, 'a') | 첫 문자, 그대로 출력 |
| 2 | 위치 2 | bracadabra | 'a' 검색, 위치 1에 일치 | (1, 0, 'b') | distance=1, 1자 일치, 'b' 추가 |
| 3 | 위치 3 | racadabra | 검색 버퍼: "ab" | (0, 0, 'r') | 일치 없음, 그대로 출력 |
| 4 | 위치 4 | acadabra | 검색 버퍼: "abr" | (3, 1, 'a') | "a" 일치, 'c' 추가 |
| 5 | 위치 5 | cadabra | 검색 버퍼: "abra" | (4, 0, 'c') | 'c' 일치 없음, 그대로 |
| 6 | 위치 6 | adabra | 검색 버퍼: "abrac" | (4, 0, 'a') | 'a'는 4자 전 일치, 그대로 'd' 추가 |
| 7 | 위치 7 | dabra | 검색 버퍼: "abraca" | (0, 0, 'd') | 일치 없음, 그대로 출력 |
| 8 | 위치 8 | abra | 검색 버퍼: "abracad" | (7, 3, 'r') | "abr" 3자 일치, distance=7, 'r' 추가 |
| 9 | 위치 9 | bra | 검색 버퍼: "abracadab" | (8, 2, 'a') | "br" 일치, distance=8, 'a' 추가 |
인코딩 결과: (0,0,'a') (1,0,'b') (0,0,'r') (3,1,'a') (4,0,'c') (4,0,'a') (0,0,'d') (7,3,'r') (8,2,'a')
원본 11자가 9개 삼중쌍으로 줄었습니다. 더 흥미로운 것은 후반 단계 8과 9로, "abra" 3자 일치와 "br" 2자 일치를 distance 포인터로 대체하여 큰 폭의 압축 효과를 보여줍니다. 실제 텍스트(반복 패턴 포함)에서는 이런 일치가 빈번히 발생해 압축률이 크게 향상됩니다.
4. LZ77의 후손 알고리즘: LZSS/LZMA/LZ4
1977년 LZ77이 제안된 이후, 이를 기반으로 다양한 변형 알고리즘이 등장했습니다. 각 알고리즘은 LZ77의 핵심 아이디어를 계승하면서도 특정 측면을 개선합니다.
| 알고리즘 | 제안 연도 | 핵심 개선 | 압축 속도 | 압축 해제 속도 | 압축률 | 대표 응용 |
|---|---|---|---|---|---|---|
| LZ77 | 1977 | 원본 알고리즘 | 중간 | 중간 | 중간 | 교육용 |
| LZSS | 1982 | 일치 없을 때 플래그 비트로 구분, 1문자/삼중쌍 선택 | 빠름 | 빠름 | 중간 | LHA, RAR(초기) |
| DEFLATE | 1991 | LZ77 + Huffman, 표준화 | 중간 | 빠름 | 중상 | ZIP, GZIP, PNG, HTTP |
| LZMA | 1998 | 큰 윈도우(8MB), 최적 파싱, 범위 코더 | 느림 | 중간 | 최고 | 7z, xz |
| LZ4 | 2011 | 해시 버킷, 단순한 인코딩 | 극히 빠름 | 극히 빠름 | 낮음 | 실시간, 게임, DB |
| ZSTD | 2016 | 해시 체인+엔트로피, 속도/압축률 균형 | 빠름 | 빠름 | 중상 | 범용, Linux 커널 |
| LZMA2 | 2009 | LZMA 멀티스레드, 병렬 처리 | 느림 | 중간 | 최고 | 7z(병렬) |
선택 가이드:
- 아카이브(고 압축률, 속도 무관): LZMA/LZMA2가 최고 압축률을 제공하며, 7z/xz 포맷으로 사용.
- 범용(속도/압축률 균형): ZSTD가 이상적이며, DEFLATE도 여전히 널리 쓰임.
- 실시간(속도 우선): LZ4가 압축 해제 속도 GB/s 급으로, 게임·DB·라이브 스트리밍에 적합.
- 웹/HTTP: DEFLATE가 표준이며, gzip, PNG, HTTP Content-Encoding으로 사용.
5. LZ77의 한계와 대응
LZ77은 강력하지만 한계도 있습니다. 알고리즘 사용 시 이러한 한계를 이해하고 적절히 대응해야 합니다.
| 한계 | 원인 | 영향 | 대응 방안 |
|---|---|---|---|
| 이미 압축된 데이터에 무력 | JPEG, MP4 등은 이미 엔트로피 코딩 완료, 반복 패턴 없음 | 압축 불가, 오히려 용량 증가 가능 | 재압축 회피, 이미 압축된 형식 그대로 저장 |
| 메모리 사용량 큼 | 큰 슬라이딩 윈도우 | 임베디드·IoT 기기에 불리 | LZ4(64KB) 같은 경량 알고리즘 선택 |
| 병렬화 어려움 | 현재 위치가 과거에 의존 | 멀티코어 활용 낮음 | 데이터 블록 분할, LZMA2 병렬 |
| 최악의 경우 매우 느림 | 해시 충돌, 최장 일치 검색 | 대용량 파일에서 지연 | 조기 종료, greedy 일치 |
| 캡슐화 매체 무력 | 이미 ZIP 내부에 있는 파일을 다시 ZIP으로 포장 | 용량 증가 5%-20% | 캡슐화 형식 식별 후 zip 스킵 |
6. 자주 묻는 질문(FAQ)
Q1: LZ77 알고리즘이란 무엇인가요?
LZ77은 1977년 Lempel과 Ziv가 제안한 슬라이딩 윈도우 기반 딕셔너리 압축 알고리즘입니다. 핵심 사상은 이미 처리한 데이터를 사전으로 사용하고, 반복 내용을 만났을 때 (distance, length, next_char) 삼중쌍으로 원본 데이터를 대체하는 것입니다. distance는 역추적 거리, length는 일치 길이, next_char는 일치 후의 다음 문자입니다. LZ77은 DEFLATE(ZIP/GZIP/PNG)의 핵심 구성 요소이며, LZSS/LZMA/LZ4 등 현대 알고리즘의 조상입니다.
Q2: LZ77의 슬라이딩 윈도우란 무엇인가요?
슬라이딩 윈도우는 LZ77의 핵심 자료구조로, 검색 버퍼(이미 처리한 과거 데이터)와 룩어헤드 버퍼(아직 처리하지 않은 미래 데이터)로 나뉩니다. 인코딩 시 룩어헤드 버퍼에서 일정 구간을 가져와 검색 버퍼에서 최장 일치를 찾습니다. 전형적인 윈도우 크기는 32KB(DEFLATE 표준)이며, 윈도우가 클수록 일치 확률은 높아지지만 메모리 오버헤드도 커집니다. 윈도우 크기가 최대 역추적 거리 distance의 상한을 결정합니다.
Q3: LZ77과 LZ78의 차이는 무엇인가요?
LZ77은 슬라이딩 윈도우로 암묵적 사전을 사용합니다. 일치 내용을 역사 데이터에 직접 참조하며 별도 사전을 저장하지 않습니다. 반면 LZ78은 명시적 사전 테이블을 사용합니다. 이미 본 문자열을 사전 항목으로 번호 부여해 저장하고, 인코딩 시 사전 인덱스를 출력합니다. LZ77은 텍스트처럼 국부 반복이 있는 데이터에 적합하고, LZ78은 전역 반복이 있는 데이터에 적합합니다. 실제 응용에서 LZ77의 후손(DEFLATE/LZMA/LZ4)이 LZ78의 후손(LZW)보다 훨씬 더 널리 쓰입니다.
Q4: LZ77, LZMA, LZ4 중 어느 것이 압축률이 가장 높은가요?
압축률 순서: LZMA > LZ77(DEFLATE) > LZ4. LZMA는 더 큰 윈도우(기본 8MB), 더 정교한 일치 알고리즘, 범위 코딩을 사용해 압축률이 가장 높지만 속도가 가장 느립니다. DEFLATE는 32KB 윈도우 + Huffman으로 압축률 중간, 속도 중간입니다. LZ4는 압축률을 trade-off하고 속도를 극대화한 알고리즘으로, 압축률이 가장 낮지만 압축 해제 속도는 4GB/s에 달합니다. 선택은 시나리오에 따라 달라집니다. 아카이브는 LZMA, 범용은 DEFLATE/ZSTD, 실시간은 LZ4.
7. 결론
LZ77은 1977년 제안된 지 반세기가 넘었지만 여전히 현대 압축 알고리즘의 초석입니다. DEFLATE(ZIP/GZIP/PNG), LZMA(7z), ZSTD 등 사실상 모든 범용 압축 도구의 핵심에 LZ77 또는 그 변형이 자리 잡고 있습니다. 핵심 사상 — "이미 처리한 데이터를 사전으로 삼아 반복을 역참조로 대체한다" — 은 단순하면서도 강력합니다. 인코딩 시 삼중쌍 (distance, length, next_char)을 출력하고, 슬라이딩 윈도우로 검색 버퍼와 룩어헤드 버퍼를 관리합니다. 약점은 이미 압축된 데이터에 대한 무력함과 메모리 사용량이며, 이후 LZSS/LZMA/LZ4/ZSTD가 이를 차례로 개선했습니다.
실무에서 LZ77을 직접 구현할 일은 드물지만, 그 원리를 이해하면 압축 도구 선택에 큰 도움이 됩니다. 아카이브는 LZMA, 범용은 DEFLATE/ZSTD, 실시간은 LZ4 — 이 선택 기준은 모두 LZ77 원리에서 출발합니다. SmartSlim의 백엔드 압축 엔진은 LZMA2 + ZSTD 하이브리드 전략을 사용하며, 파일 유형과 크기에 따라 자동으로 최적 알고리즘을 선택해 압축률과 속도의 균형을 맞춥니다.
LZ77과 결합되는 Huffman 인코딩의 원리가 궁금하다면, Huffman 인코딩 원리 상세 설명을 참고하시기 바랍니다.