사전 코딩

오프셋과 길이 참조를 사용해 반복되는 패턴을 재사용합니다.

슬라이딩 윈도우

최장 일치를 찾기 위해 이동하는 윈도우를 유지합니다.

기반 알고리즘

ZIP, GZIP, DEFLATE, PNG 등 현대 압축 포맷의 기반입니다.

LZ77 동작 방식

LZ77은 최근에 본 데이터로 구성된 슬라이딩 윈도우를 유지합니다. 각 위치에서 윈도우 안에서 가장 긴 일치 문자열을 찾습니다. 일치가 있으면 (오프셋, 길이, 다음 문자) 참조를 출력하고, 없으면 (0,0,문자)와 같은 리터럴을 출력합니다. 이렇게 반복되는 패턴을 짧은 참조로 대체하여 무손실 압축을 제공합니다.

LZ77 예제

Text: "ABCABCABC"
Window=4, Lookahead=4

Position 0: 'A' - no match
  → (0,0,A)

Position 1: 'B' - no match
  → (0,0,B)

Position 2: 'C' - no match
  → (0,0,C)

Position 3: 'ABC' - matches at offset 3
  → (3,3,A)

Position 7: 'BC' - matches at offset 3
  → (3,2,)

Output: (0,0,A)(0,0,B)(0,0,C)(3,3,A)(3,2,)