야코브 지브(Jacob Ziv)

야코브 지브는 1931년 영국 위임 통치 아래의 팔레스타인, 갈릴리 호숫가의 티베리아스에서 태어났습니다. 1948년 이스라엘이 세워진 뒤 새 나라의 공학자들은 하이파의 테크니온(이스라엘 공과대학)에서 길러졌고, 전쟁이 끊이지 않던 나라에서 통신과 전자 기술은 곧 생존의 기술이었습니다. 그 무렵 통신의 수학은 1948년 섀넌의 논문으로 막 새로 태어나 있었습니다. 섀넌의 원천 부호화 정리⁠(source coding theorem)⁠는 메시지를 기호당 엔트로피보다 짧게 줄일 수는 없고 그 한계에는 얼마든지 다가갈 수 있다고 알려 주었지만, 그러려면 원천이 기호를 내놓는 확률을 알아야 했습니다. 실제 파일과 글은 확률표를 달고 오지 않습니다. 지브는 동료 렘펠과 함께, 확률을 모른 채로 그 한계에 다가가는 방법을 찾아냈습니다.

나이 세 ·

그는 1954년 테크니온 전기 공학과를 졸업하고 이스라엘 국방부의 연구 부서에서 통신 장비를 연구하며 1957년 석사 학위를 받았습니다. 그 뒤 MIT로 건너가 1962년 박사 학위를 받았습니다. 그 무렵의 MIT는 정보 이론의 중심이었습니다. 1950년대 후반부터 섀넌이 교수로 있었고, 로버트 파노, 피터 일라이어스, 로버트 갤러거 같은 사람들이 잡음 속에서 믿을 만하게 보내는 부호를 연구하고 있었습니다. 이스라엘로 돌아와 국방 연구를 이끌던 그는 1968년부터 2년 동안 미국 벨 연구소에서 일한 뒤, 1970년 테크니온 교수가 되어 평생 그곳에 있었습니다.

그의 초기 업적 가운데 하나는 1969년 모셰 자카이와 함께 낸 추정 오차의 하한입니다. 레이더 메아리가 돌아오는 데 걸린 시간처럼 잡음 섞인 신호 속에 숨은 값을 추정할 때, 어떤 방법을 써도 오차의 제곱 평균⁠(mean)⁠이 얼마보다 작아질 수 없는지를 묻는 문제입니다. 흔히 쓰는 크라메르–라오 하한⁠(Cramér–Rao bound)⁠은 잡음이 작을 때는 정확하지만 잡음이 크면 실제 오차를 크게 얕잡아 봅니다. 지브와 자카이는 값을 추정하는 문제를 '둘 가운데 어느 쪽인가'를 가리는 수많은 판정 문제로 쪼개고, 판정이 틀릴 확률로 추정 오차를 아래에서 묶어, 잡음이 클 때도 쓸 수 있는 하한⁠(lower bound)⁠을 얻었습니다(분산⁠(variance)⁠, 최대가능도법⁠(maximum likelihood)⁠). 1976년에는 아론 와이너와 함께, 받는 쪽이 보내는 쪽의 자료와 비슷한 자료(곁정보)를 이미 가지고 있을 때 얼마나 줄여 보낼 수 있는지를 밝혔습니다. 가까이 놓인 두 온도계처럼 서로 비슷한 값을 재는 두 장치가 있다면, 둘째 장치는 첫째의 값을 보지 못하면서도 받는 쪽이 첫째 값을 안다는 사실만으로 훨씬 적은 비트를 보낼 수 있습니다. 이 와이너–지브 부호화⁠(Wyner–Ziv coding)⁠는 조금 틀려도 되는 손실 압축⁠(lossy compression)⁠의 율–왜곡 이론⁠(rate–distortion theory)⁠을 곁정보가 있는 경우로 넓힌 것으로, 오늘날 센서망과 영상 부호화 연구에 쓰입니다.

압축의 물음으로 돌아가 봅시다. 허프만 부호⁠(Huffman coding)⁠는 글자마다의 확률표가 있어야 짤 수 있습니다. 글을 한 번 읽어 표를 만들고 다시 읽어 부호화할 수는 있지만, 표도 함께 보내야 하고, 무엇보다 글자들은 서로 기대어 있습니다. 한국어에서 '습' 다음에는 '니'가 올 가능성이 높듯이, 앞 글자가 다음 글자를 바꾸니 글자 하나하나의 빈도만으로는 한계에 닿지 못합니다. 지브는 물음을 더 과감하게 세웠습니다. 확률이라는 가정을 아예 버리고, 주어진 문자열 하나만 놓고 보았을 때, 어떤 압축기가 그 문자열에 맞춰 설계된 어떤 유한한 기계 못지않게 잘 줄일 수 있을까?

1977년 지브와 렘펠의 답(LZ77)은 이미 보낸 글을 사전으로 쓰는 것이었습니다. 글을 앞에서부터 읽으며, 지금 자리에서 시작하는 조각이 앞에 나온 적이 있으면 그 조각을 다시 보내는 대신 '$d$칸 앞에서 시작하는 $\ell$글자를 베껴라'라는 참조 $\langle d, \ell \rangle$를 보냅니다. 받는 쪽도 이미 받은 글을 가지고 있으니 똑같이 베낄 수 있습니다. 'abcabcabcabc'라면 처음 세 글자 a, b, c를 그대로 보낸 뒤 참조 $\langle 3, 9 \rangle$ 하나로 끝납니다. 3칸 앞에서 9글자를 베끼면 베끼는 동안 방금 쓴 글자를 다시 베끼게 되는데, 한 글자씩 차례로 베끼면 이것도 아무 문제가 없습니다. 참조가 왜 엔트로피만큼의 비트로 충분한지는 뒤에 와이너와 지브가 1989년에 밝혔습니다. 기호당 엔트로피가 $H$인 원천에서 길이 $\ell$인 조각은 대략 $2^{\ell H}$칸 앞에서 다시 나타나므로, 거리 $d$를 적는 데 드는 $\log_2 d$비트는 대략 $\ell H$, 곧 글자당 $H$비트가 됩니다.

1978년의 두 번째 방법(LZ78)은 지나온 조각들을 번호 붙은 사전에 쌓아 갑니다. 글을 읽으며 사전에 있는 가장 긴 조각에 새 글자 하나를 붙인 것을 다음 조각으로 삼고, '사전의 몇 번 조각 + 새 글자'로 보낸 뒤 그 조각을 사전에 새로 넣습니다. 'aababcabcd'는 a, ab, abc, abcd로 잘려 (0, a), (1, b), (2, c), (3, d)로 보내집니다. 되풀이가 많을수록 조각이 빨리 길어집니다. 이 논문의 정리는 확률을 전혀 가정하지 않습니다. 어떤 무한 문자열이든, LZ78은 그 문자열 하나에 맞춰 설계된 가장 좋은 유한 상태 압축기, 곧 기억이 유한한 유한 오토마톤⁠(finite automaton)⁠으로 된 어떤 압축기에도 길게 보아 뒤지지 않습니다. 원천이 확률적이고 정상적이며 에르고딕⁠(ergodic)⁠하다면(예컨대 마르코프 연쇄⁠(Markov chain)⁠), 길이 $n$의 글이 잘리는 조각의 수를 $c(n)$이라 할 때 위의 식처럼 글자당 비트 수가 원천의 엔트로피율⁠(entropy rate)⁠ $H$에 다가갑니다. 한 방법이 모든 원천에 대해 동시에 최적이라는 뜻에서 이런 방법을 보편 압축이라 부릅니다(렘펠–지브 압축⁠, Lempel–Ziv compression⁠).

이 논문들은 처음에는 정보 이론 학술지의 수학이었지만 곧 모든 컴퓨터에 들어갔습니다. 1984년 스페리 연구소의 테리 웰치가 LZ78을 하드웨어로 빠르게 돌리도록 다듬은 LZW는 유닉스의 compress와 1987년의 그림 형식 GIF에 쓰였습니다. LZW에 걸린 특허가 1994년 말 사용료 분쟁을 일으키자 특허를 피한 새 형식 PNG가 만들어졌는데, PNG가 쓰는 디플레이트⁠(Deflate)⁠는 LZ77로 반복을 참조로 바꾼 뒤 그 결과를 다시 허프만 부호로 적습니다. zip, gzip, 웹 페이지를 보낼 때의 압축, 그리고 오늘날의 xz, Zstandard, Brotli까지 대부분의 무손실 압축기는 렘펠–지브 계열의 참조 위에 허프만의 부호나 산술 부호화⁠(arithmetic coding)⁠를 얹은 구조입니다. 긴 글에서 같은 조각을 빨리 찾는 일에는 해시 테이블⁠(hash table)⁠이 쓰입니다.

압축기는 뜻밖에 글과 글이 얼마나 닮았는지를 재는 도구도 되었습니다. 1993년 지브와 네리 메르하브는 한 글을 다른 글의 조각들로 얼마나 짧게 잘라 낼 수 있는지로 두 원천 사이의 쿨백–라이블러 발산⁠(Kullback–Leibler divergence)⁠을 어림하는 방법을 내놓았습니다. 2002년 이탈리아의 물리학자들은 여러 언어로 된 글을 zip으로 압축해 서로 얼마나 잘 줄여 주는지로 언어의 계통수⁠(phylogenetic tree)⁠를 그리고 글쓴이를 가려내 보였습니다. 문자열 하나의 정보량을 묻는 콜모고로프 복잡도⁠(Kolmogorov complexity)⁠는 계산할 수 없지만, 압축기가 만든 파일의 길이는 그 위쪽 어림이 됩니다.

지브는 테크니온에서 전기공학부 학장과 부총장을 지내며 이스라엘 공학 교육의 틀을 만드는 데에도 힘을 쏟았습니다. 1993년 이스라엘상, 1995년 IEEE 리처드 해밍 메달, 1997년 정보 이론 학회의 섀넌상을 받았고, 2021년에는 전기전자공학자협회(IEEE)가 주는 가장 큰 상인 명예 메달을 받았습니다. 2023년 3월, 평생의 동료 렘펠이 세상을 떠난 지 일곱 주 뒤에 그도 세상을 떠났습니다.

이어지는 곳. 압축이 넘을 수 없는 한계는 엔트로피와 원천 부호화 정리가, 앞 기호에 기대는 원천의 한계는 조건부 엔트로피⁠(conditional entropy)⁠가 정합니다. 확률표가 있을 때의 최선은 허프만 부호와 산술 부호화이고, 조금 틀려도 되는 압축은 율–왜곡 이론과 이산 코사인 변환⁠(discrete cosine transform)⁠으로 이어집니다. 모든 글을 줄이는 압축이 불가능한 까닭은 비둘기집 원리⁠(pigeonhole principle)⁠에 있고, 정보 이론이 자란 곳의 이야기는 벨 연구소에 있습니다.

관계.

• 영향을 받음 클로드 섀넌 — 섀넌의 원천 부호화 정리가 알려 준 한계, 곧 기호당 평균 비트 수는 엔트로피보다 작을 수 없다는 한계에 원천의 확률을 모르고도 다가가는 방법을 찾는 것이 지브의 평생 물음이었습니다.
• 함께 연구 아브라함 렘펠 — 테크니온의 동료로서 1976년 복잡도 논문, 1977년과 1978년의 두 압축 논문을 함께 써 렘펠–지브 압축을 만들었습니다.

연표.

• 1954년 테크니온 전기 공학과를 졸업하다
• 1955년 이스라엘 국방부의 연구 부서에서 통신 장비를 연구하기 시작하다
• 1962년 MIT에서 박사 학위를 받다
• 1968년 미국 벨 연구소의 연구원이 되다
• 1969년 모셰 자카이와 추정 오차의 하한을 발표하다
• 1970년 테크니온 전기공학부 교수가 되다
• 1976년 렘펠과 유한 수열의 복잡도를 재는 방법을, 와이너와 곁정보가 있는 부호화를 발표하다
• 1977년 렘펠과 앞의 글을 가리키는 압축(LZ77)을 발표하다
• 1978년 렘펠과 사전을 쌓는 압축(LZ78)을 발표하다
• 1993년 이스라엘상을 받다
• 1997년 정보 이론 학회의 섀넌상을 받다
• 2021년 IEEE 명예 메달을 받다