렘펠–지브 압축(Lempel–Ziv compression)

글에는 되풀이가 많습니다. 같은 낱말, 같은 어미, 같은 구절이 거듭 나옵니다. 1977년 이스라엘 테크니온 공과대학의 아브라함 렘펠과 야코브 지브는 글을 앞에서부터 읽으며, 지금 자리에서 시작하는 문자열이 앞에 이미 나온 적이 있으면 그것을 '$d$칸 앞에서 시작하는 $\ell$글자'라는 참조 $\langle d, \ell \rangle$로 바꾸고, 없으면 글자를 그대로 적는 방법을 내놓았습니다(LZ77). 풀 때는 참조를 만날 때마다 이미 풀어 놓은 부분에서 그대로 베껴 오면 됩니다. 글자마다의 확률표가 전혀 필요 없다는 점이 허프만 부호⁠(Huffman coding)⁠와 다릅니다.

글: . 세 글자 이상 겹칠 때만 참조로 바꿉니다.

지금까지의 출력:

'hahaha…'를 보세요. 참조는 자기 자신과 겹쳐도 됩니다. ha 두 글자를 적은 뒤의 $\langle 2, \ell \rangle$은 두 칸 앞에서 한 글자씩 베끼는데, 베끼는 동안 새로 쓴 글자를 다시 베끼니 ha가 계속 이어집니다. 그래서 'ha'를 번 되풀이한 글자 개가 토큰 개로 줄어듭니다. 늘어나는 것은 길이 ℓ을 적는 자릿수뿐이고, 그것은 로그만큼만 자랍니다.

실제 압축기는 가장 긴 겹침을 빨리 찾으려고 세 글자짜리 조각마다 그것이 나왔던 자리들을 해시 테이블⁠(hash table)⁠에 적어 둡니다. 세 글자짜리 조각은 n = 3인 n-그램⁠(n-gram)⁠입니다. zip, gzip, PNG가 쓰는 DEFLATE는 거리를 32KB 안쪽으로 제한한 LZ77로 되풀이를 없앤 뒤, 남은 글자와 참조를 허프만 부호로 한 번 더 줄입니다. 1978년의 LZ78과 이것을 미국의 테리 웰치가 고친 LZW(1984)는 참조 대신 지금까지 본 문자열의 사전을 키워 가며 번호로 가리키며, GIF 그림 형식이 LZW를 씁니다. 사전을 키우는 또 다른 압축법으로, 가장 자주 이웃해 나오는 두 기호를 새 기호 하나로 바꾸기를 되풀이하는 바이트 쌍 부호화(BPE, 1994)가 있습니다. 오늘날 언어 모델⁠(language model)⁠이 글을 자를 어휘를 만드는 토큰화가 이 방법을 씁니다.

왜 이것이 좋은 압축일까요? 렘펠과 지브, 그리고 뒤이은 연구들은 원천이 정상적이고 에르고딕⁠(ergodic)⁠하기만 하면, 글이 길어질수록 이런 방법의 기호당 비트 수가 원천의 엔트로피율⁠(entropy rate)⁠로 수렴⁠(convergence)⁠한다는 것을 보였습니다. 정상적이라는 것은 기호를 내는 확률 규칙이 시간에 따라 바뀌지 않는다는 뜻입니다. 에르고딕하다는 것은 긴 글 하나에서 센 빈도가 글이 길어질수록 원천 전체의 확률에 다가간다는 뜻입니다. 상태가 유한 개이고 전이 확률⁠(transition probability)⁠이 고정되어 있으며 어느 상태에서든 모든 상태로 갈 수 있는 마르코프 연쇄(정상 분포⁠(stationary distribution)⁠에서 출발한 것)가 그런 예입니다. 분포를 모르고도 원천 부호화 정리⁠(source coding theorem)⁠의 한계에 닿으니 '범용' 압축이라 부릅니다. 반면 '무작위 글'처럼 되풀이가 없는 글은 거의 줄지 않습니다. 이것은 방법의 결함이 아닙니다. 비둘기집 원리⁠(pigeonhole principle)⁠에 따르면 어떤 압축도 모든 글을 줄일 수는 없고, 줄어드는 글이 있으면 줄지 않는 글도 있어야 합니다.

이어지는 곳. 압축된 길이는 그 글이 얼마나 규칙적인지를 재는 실용적인 잣대입니다. 압축된 길이에 풀기 프로그램의 길이(글과 상관없는 상수)를 더한 값은 콜모고로프 복잡도⁠(Kolmogorov complexity)⁠보다 작을 수 없습니다. 거꾸로 말하면 콜모고로프 복잡도는, 그 상수를 빼면, 어떤 압축기도 밑돌 수 없는 이론적 하한입니다. 두 글을 이어 붙여 압축했을 때 따로 압축한 것보다 얼마나 줄어드는지로 글 사이의 거리를 잴 수도 있습니다. 여러 언어로 된 같은 글을 이런 거리로 묶어 비교 언어학⁠(comparative linguistics)⁠의 계통수⁠(phylogenetic tree)⁠와 비슷한 나무를 얻은 연구도 있습니다. 흔한 낱말이 압도적으로 자주 나오는 지프의 법칙⁠(Zipf's law)⁠이 글이 잘 줄어드는 한 가지 이유입니다. LZMA(xz, 7-Zip)처럼 참조를 찾은 뒤 그 결과를 다시 산술 부호화⁠(arithmetic coding)⁠의 한 갈래인 범위 부호로 적는 압축기도 많습니다.