한양과기고 에듀테크 수업도구 대시보드

LZ77 압축 — 방금 지나간 글자를 다시 가리키기

글에는 같은 조각이 반복된다. "ABABAB", "보고보고보고"처럼. LZ77은 이미 읽은 부분(검색 창)에서 앞으로 나올 글자와 가장 길게 겹치는 곳을 찾아, 그 글자들을 그대로 저장하는 대신 (얼마나 뒤로, 몇 글자) 라는 짧은 좌표로 바꿔 적는다. gzip · PNG · ZIP의 DEFLATE가 바로 이 방식(LZ77 + 허프만)이다.

1. 압축할 문자열

검색 창 크기 12

미리보기 창 크기 6

2. 창을 오른쪽으로 밀며 가장 긴 일치 찾기

처리 완료 검색 창 찾은 일치 미리보기 창 다음 글자

‘시작’을 누른 뒤 다음 토큰으로 진행하세요.

3. 만들어진 토큰 (거리, 길이, 다음글자)

아직 없음

4. 얼마나 줄었을까?

–

원본 (bits, 8b/글자)

–

토큰 (bits)

–

절약률

원본 (글자당 8비트)–

LZ77 토큰–

여기서는 리터럴 토큰 9bit(플래그 1 + 글자 8), 참조 토큰 17bit(플래그 1 + 거리 8 + 길이 4 + 다음글자 4… 실제 gzip은 허프만으로 더 줄인다)로 어림한 값이다.

5. 토큰만으로 원본 복원하기

디코더는 사전(dictionary)이 필요 없다. 지금까지 복원한 글자 자체가 사전이다. 참조 토큰을 만나면 거리만큼 뒤로 가서 길이만큼 한 글자씩 베껴 붙인다.

–

6. 인코더 (의사코드)

# pos: 아직 압축 안 한 위치, W: 검색 창, L: 미리보기 창 pos = 0 while pos < len(data): best_len, best_dist = 0, 0 start = max(0, pos - W) # 검색 창의 모든 시작점에서 얼마나 길게 이어지나 확인 for j in range(start, pos): k = 0 while k < L and pos+k < len(data) and data[j+k] == data[pos+k]: k += 1 # 일치 구간이 창 밖으로 겹쳐도 OK if k > best_len: best_len, best_dist = k, pos - j if best_len >= 2: emit(Ref(dist=best_dist, len=best_len, next=data[pos+best_len])) pos += best_len + 1 else: emit(Literal(data[pos])) # 겹치는 게 없으면 글자 그대로 pos += 1

7. 핵심 아이디어

사전이 곧 데이터다

따로 코드표를 저장하는 허프만과 달리, LZ77은 이미 지나간 원문을 사전으로 쓴다. 그래서 인코더·디코더가 같은 규칙만 알면 추가 정보 없이 서로 맞춰진다.

겹치는 복사도 허용

(거리 1, 길이 5)는 "바로 앞 글자를 5번 반복"이라는 뜻. 복사를 한 글자씩 진행하므로 아직 안 만들어진 글자도 즉석에서 채워진다. 런-렝스 압축이 공짜로 포함된다.

창이 클수록 유리, 대신 느림

검색 창이 넓으면 멀리 있는 반복도 잡지만, 매 위치에서 창 전체를 훑어야 해 느려진다. 실제 gzip은 32KB 창 + 해시 체인으로 후보를 빠르게 좁힌다.

뒤에 허프만을 한 번 더

LZ77이 뱉은 거리·길이 숫자에도 편향이 있다(짧은 거리가 흔함). DEFLATE는 그 위에 허프만 코딩을 씌워 마무리한다. LZ77 → 허프만이 gzip의 2단 구조.

1977년 Abraham Lempel과 Jacob Ziv가 발표 — 이름의 77이 그 해다. 이듬해 나온 LZ78과 함께 거의 모든 무손실 압축의 뿌리가 됐다.