LZ77 슬라이딩 윈도 압축 계산기

앞서 나온 글자열을 다시 적는 대신 「몇 칸 뒤에서 몇 글자」로 가리켜 줄이는 압축 방식입니다. 1977년 렘펠과 지브가 발표했으며, gzip·zip·PNG가 모두 이 방식에 허프만 부호를 얹은 구조(deflate)입니다.

됩니다. 그리고 그것이 이 알고리즘의 묘미입니다. aaaaa를 만들 때 (거리 1, 길이 4)로 적으면 푸는 쪽은 한 칸 뒤 글자를 네 번 가져오는데, 한 글자씩 옮기다 보면 방금 쓴 글자를 다시 읽어 저절로 늘어납니다. 다만 복원할 때 구간을 통째로 복사하면 이 경우에 결과가 깨지므로 반드시 한 글자씩 옮겨야 합니다.

크면 멀리 있는 반복도 잡지만 거리를 적는 데 비트가 더 듭니다. deflate는 창을 32KB, 길이를 258까지로 두고 있습니다. 이 도구에서 창 크기를 바꿔 보면 같은 글이라도 잡히는 반복의 개수와 압축률이 달라지는 것이 보입니다.

LZW는 사전을 따로 만들어 번호로 가리키고, LZ77은 사전 없이 원문 자체를 사전처럼 씁니다. 그래서 LZ77은 사전을 주고받을 필요가 없고 앞부분만 있으면 이어서 풀 수 있습니다. GIF가 LZW, gzip이 LZ77 계열입니다.

되풀이가 없으면 토큰이 글자보다 비싸기 때문입니다. 매치가 없는 자리도 (0, 0, 글자) 토큰으로 적어야 하는데 거리와 길이 자리가 그대로 낭비됩니다. 실제 gzip은 리터럴과 매치를 구분해 적고(LZSS) 허프만으로 다시 줄이므로 이만큼 나빠지지는 않습니다.

다릅니다. 이 도구는 거리·길이·글자를 고정 폭 비트로 적었을 때를 어림한 값입니다. gzip은 그 위에 허프만 부호를 얹어 자주 나오는 값을 더 짧게 적으므로 실제로는 더 줄어듭니다. 원리를 보이기 위한 값으로 보시는 것이 맞습니다.

전송되지 않습니다. 압축과 복원은 모두 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.