LZ78 압축 계산기
문자열을 LZ78로 압축해 (사전 인덱스, 다음 글자) 토큰을 하나씩 보여 주고, 사전이 만들어지는 순서와 다시 풀었을 때 원문이 그대로 돌아오는지 확인합니다.
UTF-8 바이트로 바꿔 LZ78 규칙대로 사전을 만들어 갑니다
토큰 6개
67.5%
80비트가 54비트가 되었습니다
토큰과 사전 생성 순서
| # | 토큰 (인덱스, 글자) | 나타내는 값 | 새 사전 항목 |
|---|---|---|---|
| 0 | (0, a) | a | #1 = a |
| 1 | (0, b) | b | #2 = b |
| 2 | (1, b) | ab | #3 = ab |
| 3 | (3, a) | aba | #4 = aba |
| 4 | (2, a) | ba | #5 = ba |
| 5 | (2, 없음) | b | 없음(꼬리 토큰) |
사용 방법
- 1압축할 글을 입력합니다.
- 2토큰(사전 인덱스, 다음 글자)이 하나씩 나오는 순서와, 그때마다 사전에 새로 들어가는 항목을 확인합니다.
- 3되돌린 결과가 원문과 같은지, 압축률이 몇 %인지 봅니다.
자주 묻는 질문
dev/lz77은 이미 나온 글자들(슬라이딩 윈도) 안에서 (거리, 길이, 다음 글자)를 찾고, dev/lzw-compress는 사전에 알파벳 256개를 미리 채워 넣어 인덱스만 내보냅니다. LZ78은 그 중간 단계로, 사전이 빈 채로 시작하고 (기존 사전 인덱스, 다음 글자) 쌍을 매번 명시적으로 출력하며 그 쌍 자체가 새 사전 항목이 됩니다.
LZW는 LZ78의 "다음 글자" 필드를 없앴습니다. 사전에 알파벳(바이트 256개)을 미리 채워 둬서 항상 매치가 있으므로, 매번 새 글자를 따로 실어 보낼 필요가 없어져 인덱스만으로 충분해졌기 때문입니다. 그만큼 토큰이 가벼워져 압축률이 좋아집니다.
현재까지 매칭된 부분(w)에 새 글자(c)를 더한 w+c가 사전에 없으면, (w의 인덱스, c)를 출력하고 w+c를 새 항목으로 사전에 추가한 뒤 처음부터 다시 매칭을 시작합니다. "ababab"를 넣으면 (0,a) (0,b) (1,b) 순서로 토큰이 나오며 사전에는 "a", "b", "ab"가 차례로 생깁니다.
새 글자를 못 만나고 입력이 끝나는 예외적인 경우로, 새 사전 항목 없이 인덱스만 담은 "꼬리 토큰"이 마지막에 하나 더 붙습니다. "aa"를 넣으면 (0,a)로 "a"가 사전에 생긴 뒤, 두 번째 a는 "a"와 매칭되지만 뒤에 글자가 없어 (1, 없음)이라는 꼬리 토큰이 나옵니다.
오히려 커집니다. 반복이 전혀 없으면 글자마다 매번 새 사전 항목을 만들어야 해서, 토큰 하나(인덱스+글자)가 원래 글자 하나보다 더 많은 비트를 씁니다. 반복이 많을수록 사전을 재사용하는 비율이 높아져 압축 효과가 커집니다.
알아두면 좋은 점
- 바이트(UTF-8) 단위로 다룹니다. 한글은 한 글자가 3바이트라 사전 항목이 글자 경계에 맞지 않을 수 있습니다.
- 토큰 하나의 비트 수는 인덱스 비트(그 시점 사전 크기 기준)와 글자 8비트(꼬리 토큰은 글자 없음)를 더해 어림잡습니다. 실제 구현(GIF의 LZW 등)은 고정 폭이나 다른 부호화를 쓰기도 해 비트 수가 다를 수 있습니다.
- 결정적 절차라 압축→해제 왕복이 항상 원문과 같은지로 검산했습니다.
함께 보면 좋은 도구
마지막 검증: 2026년 9월 3일 · 결과는 참고용 추정치입니다.