반복을 가리킨다 - 같은 말을 두 번 적지 않는 법

노트에서 〃를 적는 순간이 압축의 시작이다. 그 요령을 어디까지 밀 수 있는지를 본다.

붙어 있는 반복은 개수로 접는다

가장 단순한 반복은 같은 것이 줄줄이 이어지는 경우다.

AAAAAAAAAAAABBBBCCCCCCCC

24글자다. 그런데 이걸 사람이 노트에 옮긴다면 A 열둘, B 넷, C 여덟이라고 적을 것이다. 컴퓨터도 똑같이 한다.

12A 4B 8C

“무엇이 몇 번”만 적는 이 방식을 런렝스 부호화(RLE)라고 부른다. 압축이라는 말이 붙은 것 중 가장 이해하기 쉽고, 실제로 가장 먼저 나온 부류이기도 하다.

이게 잘 먹히는 데이터가 있다. 팩스로 보내는 흑백 문서가 대표적이다. 한 줄 대부분이 흰색이라 흰색 1200개처럼 접힌다. 단색 배경의 아이콘, 스캔한 서류도 마찬가지다.

반복이 없으면 오히려 커진다

RLE에는 정직한 대가가 있다. 반복이 없는 데이터에 걸면 크기가 늘어난다.

ABCDEFG   ->   1A 1B 1C 1D 1E 1F 1G

7글자가 14글자가 됐다. “몇 번”을 적는 자리가 매번 붙는데 정작 접을 게 없어서다.

이건 RLE만의 흠이 아니라 모든 압축이 지고 가는 성질이다. 어떤 압축 방식도 특정 데이터에서는 크기를 늘린다. 왜 그럴 수밖에 없는지는 시리즈 뒤쪽의 한계 편에서 정면으로 다룬다.

그래서 실제 형식들은 요령을 하나 얹는다. 접는 게 손해다 싶은 구간은 “여기는 그냥 원본”이라고 표시하고 손대지 않는다. 늘어나는 폭을 아주 작게 묶어 두는 장치다.

붙어 있지 않아도 반복은 반복이다

RLE의 진짜 한계는 다른 데 있다. 바로 옆에 붙어 있어야만 반복으로 쳐 준다.

실제 데이터의 반복은 그렇게 안 생겼다.

사과는 맛있다. 바나나는 길다. 사과는 맛있다.

사과는 맛있다.가 두 번 나왔지만 붙어 있지 않다. RLE로는 하나도 못 줄인다. 그런데 노트를 적는 학생은 이런 반복도 잡아낸다. 두 번째 사과는 맛있다.를 적을 때 **“18자 앞의 것, 8자”**라고만 적으면 그만이다.

이 발상이 압축의 판을 바꿨다. 접는 게 아니라 가리키는 것이다.

뒤를 돌아 위치와 길이를 적는다

가리키려면 두 가지를 적어야 한다. 얼마나 뒤로 가서, 몇 글자를 가져올지.

(거리 18, 길이 8)이라고 적으면 “여기서 18자 앞으로 되돌아가 거기서부터 8자를 그대로 가져오라”는 뜻이다. 원본 여덟 글자를 대신하는 자리에 두 개의 수가 들어간다.

이 방식을 LZ77이라고 부른다. 이름은 낯설어도 하는 일은 노트의 “위 두 줄, 4자”와 정확히 같다. 그리고 zip, gzip, PNG가 안에서 쓰는 것이 전부 이 계열이다.

여기서 왜 이게 강력한지가 보인다. 반복이 얼마나 멀리 떨어져 있든, 얼마나 길든 상관없이 두 개의 수로 대체된다. 200자짜리 반복도 (거리 5000, 길이 200) 하나면 끝난다. 붙어 있어야 한다는 조건이 사라진 값이 이만큼 크다.

얼마나 뒤까지 돌아볼 수 있나

다만 무한정 뒤를 돌아볼 수는 없다. 거리를 적는 자리도 유한하기 때문이다.

거리를 두 바이트로 적기로 정했다면 최대 65,535자 앞까지만 가리킬 수 있다. 그보다 멀리 있는 반복은 눈앞에 있어도 못 쓴다. 이 “돌아볼 수 있는 범위”를 **창(window)**이라고 부른다.

노트로 치면 앞 장을 몇 페이지까지 넘겨 볼 수 있느냐다. 두 페이지 전은 찾아보지만 서른 페이지 전은 찾기가 귀찮아 그냥 다시 적는 것과 같다.

창을 키우면 더 많은 반복을 잡지만 대가가 둘 붙는다.

• 찾는 시간이 늘어난다. 매 자리마다 “이 조각이 앞에 나온 적 있나”를 뒤져야 한다
• 거리를 적는 자리가 커진다. 멀리까지 가리키려면 수가 커지고, 수가 커지면 적는 데 비트가 더 든다

압축 프로그램의 레벨 옵션이 주로 이 창과 탐색 노력을 조절한다. 높은 레벨이 느리면서 더 잘 줄어드는 이유가 여기 있다.

자기 자신을 겹쳐 가리킬 수 있다

가리키기에는 처음 보면 이상해 보이는 재주가 하나 있다. 아직 다 만들어지지도 않은 자리를 가리킬 수 있다.

AAAAAAAAAA(A 열 개)를 이렇게 적는다고 해 보자.

A (거리 1, 길이 9)

거리 1이면 바로 한 칸 앞이다. 그런데 한 칸 앞에는 지금 막 적은 A 하나뿐이고, 가져오라는 길이는 9다. 가져올 게 아직 없는데 9자를 가져오라니 모순처럼 보인다.

푸는 쪽을 한 글자씩 따라가 보면 모순이 아니다. 한 칸 앞의 A를 가져와 쓰면 그 순간 결과가 AA가 되고, 다시 한 칸 앞을 보면 방금 쓴 A가 있다. 이렇게 한 글자씩 밀면서 아홉 번을 채운다.

그래서 가리키기는 붙어 있는 반복까지 흡수한다. 앞에서 본 RLE가 하던 일을 따로 둘 필요가 없어진 것이다. 같은 아이디어를 규모만 키웠더니 앞의 것을 삼켜 버렸다.

실무에서: 무엇이 잘 줄고 무엇이 안 주나

가리키기가 원리라는 걸 알면 어떤 데이터가 잘 줄지 미리 짐작할 수 있다.

JSON 응답이 압축을 걸었을 때 유난히 잘 주는 이유가 여기서 설명된다. 목록의 항목마다 같은 키 문자열이 그대로 다시 나오기 때문이다. 항목이 천 개면 같은 키가 천 번 나오고, 두 번째부터는 전부 짧은 가리킴으로 바뀐다.

다만 그게 곧 “그러니 JSON을 그대로 써도 된다”는 뜻은 아니다. gRPC 편에서 짚은 대로 압축은 전송 크기만 줄이고 파싱 비용은 그대로다. 이 시리즈의 마지막 편에서 그 거래를 다시 본다.

한 가지 요령이 더 있다. 비슷한 것끼리 모아 두면 더 잘 준다. 창 안에 반복이 들어와야 가리킬 수 있으므로, 여러 파일을 압축할 때 같은 종류를 붙여 두면 이득이 커진다. 로그를 날짜별로 잘라 각각 압축하는 것보다 한 덩어리로 묶어 압축하는 쪽이 대체로 더 작아지는 이유다.

정리

• 압축의 첫째 무기는 반복을 두 번 적지 않는 것이다.
• 붙어 있는 반복은 개수로 접는다(RLE). 팩스나 단색 이미지에는 잘 맞지만 반복이 없으면 오히려 커진다.
• 떨어져 있는 반복은 뒤를 돌아 가리킨다(LZ77). (거리, 길이) 두 수로 아무리 긴 반복도 대체된다.
• 돌아볼 수 있는 범위가 창이고, 창을 키우면 더 줄지만 느려진다. 압축 레벨이 조절하는 것이 대체로 이것이다.
• 가리키기는 자기 자신을 겹쳐 가리킬 수 있어 붙어 있는 반복까지 흡수한다.
• 그래서 로그·JSON·코드는 잘 줄고, 이미 압축된 것과 암호문은 안 준다.

다음 글은 줄어드는 둘째 이유로 넘어간다. 반복이 하나도 없어도 어떤 것이 유난히 자주 나온다면 아직 줄일 여지가 남아 있다.