아브라함 렘펠(Abraham Lempel)

아브라함 렘펠은 1936년 폴란드의 르부프(오늘날 우크라이나의 르비우)에서 태어났습니다. 그가 태어날 무렵 르부프는 스테판 바나흐를 중심으로 한 수학자들이 카페에 모여 문제를 주고받던 폴란드 수학의 중심지였지만, 몇 해 뒤 전쟁과 점령이 이 도시의 유대인 공동체를 거의 지워 버렸습니다. 뒤에 이스라엘로 건너간 렘펠은 하이파의 테크니온에서 공학자가 되었습니다. 그 무렵 컴퓨터 과학은 전기 공학과 수학 사이에서 막 독립⁠(independence)⁠한 분야였고, 렘펠의 일은 스위치 회로, 그래프 알고리즘⁠(algorithm)⁠, 수열의 조합론⁠(combinatorics)⁠처럼 기계가 다루는 이산적인 대상의 구조를 밝히는 것이었습니다. 그 조합론의 감각이 동료 야코브 지브의 정보 이론과 만나 렘펠–지브 압축이 태어났습니다.

나이 세 ·

그는 테크니온에서 1963년 학사, 1965년 석사, 1967년 박사 학위를 모두 전기 공학으로 받았습니다. 박사 학위를 받던 해 그는 시몬 에번, 이스라엘 체데르바움과 함께 그래프가 평면 그래프인지, 곧 변이 서로 엇갈리지 않게 평면에 그릴 수 있는지를 판정하는 방법을 발표했습니다. 전자 회로의 배선을 한 층의 기판 위에 교차 없이 깔 수 있는지가 바로 이 물음입니다. 그들의 방법은 꼭짓점⁠(vertex)⁠에 번호를 매겨 하나씩 더해 가면서, 지금까지 그린 부분을 어떻게 배치할 수 있는지의 가능성들을 계속 추려 나갑니다. 가능성이 하나도 남지 않으면 평면 그래프가 아닙니다. 이 방법은 1976년 부스와 루커가 알맞은 자료 구조를 더해 그래프의 크기에 비례하는 시간 안에 끝나도록 만든 평면성 판정⁠(planarity testing)⁠ 알고리즘의 바탕이 되었습니다(4색 정리⁠(four color theorem)⁠).

1970년 그는 시프트 레지스터가 만드는 수열에 관한 논문을 냈습니다. 시프트 레지스터는 $n$칸에 비트가 하나씩 들어 있는 장치로, 한 걸음마다 비트들을 한 칸씩 밀고 빈칸에 지금 칸들의 값으로 정한 새 비트를 넣습니다. 이렇게 나오는 수열 가운데 특별한 것이 드브라윈 수열입니다. 길이가 $2^n$인 고리 모양의 비트열로, 길이 $n$인 창을 한 칸씩 옮기면 가능한 $n$비트 조각이 모두 꼭 한 번씩 나타납니다. $n = 3$이면 00010111이 그렇습니다. 창을 옮기면 000, 001, 010, 101, 011, 111, 110, 100으로 여덟 가지가 모두 한 번씩 나옵니다(끝에서 처음으로 이어집니다). 이런 수열은 통신의 동기 신호, 회로 검사, 암호에 쓰입니다. 렘펠은 $n$비트 조각 $(x_1, \ldots, x_n)$을 이웃한 두 비트의 합을 2로 나눈 나머지⁠(remainder)⁠들의 조각 $(x_1 \oplus x_2, \ldots, x_{n-1} \oplus x_n)$으로 보내는 사상을 생각했습니다(모듈러 연산⁠, modular arithmetic⁠). 이 사상에서 $n-1$비트 조각 하나로 오는 조각은 서로 모든 비트가 뒤집힌 꼭 두 개이고, 이 성질을 거꾸로 따라가면 작은 드브라윈 수열⁠(de Bruijn sequence)⁠에서 한 단계 큰 드브라윈 수열을 만들 수 있습니다. $n$비트 조각들을 꼭짓점으로, 한 칸 밀기를 변으로 그린 그림을 드브라윈 그래프라 합니다. 드브라윈 수열은 이 그래프의 꼭짓점을 모두 한 번씩 지나는 고리이고, 한 단계 작은 그래프에서 보면 모든 변을 한 번씩 지나는 오일러 회로⁠(Euler circuit)⁠입니다. 렘펠의 사상은 $n$비트 그래프를 $n-1$비트 그래프로 보내면서 변으로 이어진 두 꼭짓점을 변으로 이어진 두 꼭짓점으로 보내므로 그래프 사이의 준동형⁠(homomorphism)⁠이고, 오늘날 '렘펠의 준동형'이라 불립니다.

1970년대 들어 그는 지브와 함께 문자열이 얼마나 복잡한지를 재는 문제를 붙들었습니다. 러시아의 콜모고로프는 1960년대에 문자열의 복잡도를 그것을 출력하는 가장 짧은 프로그램의 길이로 정의했지만(콜모고로프 복잡도⁠, Kolmogorov complexity⁠), 이 값은 정지 문제⁠(halting problem)⁠ 때문에 일반적으로 계산할 수 없습니다. 1976년 렘펠과 지브는 허락하는 연산을 '앞에 나온 부분을 베끼기' 하나로 줄였습니다. 문자열을 왼쪽에서부터 읽으며, 다음 조각은 앞에서 베낄 수 있는 데까지 길게 늘인 뒤 새 글자 하나를 붙여 끝냅니다. 이렇게 잘린 조각의 수가 그 문자열의 복잡도입니다. 예컨대 0001101001000101은 0 · 001 · 10 · 100 · 1000 · 101의 여섯 조각으로 잘립니다. 둘째 조각 001에서 앞의 두 0은 첫 자리에서 시작해 베낀 것인데, 베끼는 도중에 방금 베낀 글자를 다시 베끼는 겹침도 허락됩니다.

되풀이가 많은 문자열은 조각이 빨리 길어져 조각 수가 적고, 무작위 문자열은 조각 수가 많습니다. 길이가 $n$인 무작위 비트열에서는 조각 수가 대략 $n / \log_2 n$이 됩니다. 이유는 셈에 있습니다. 서로 다른 조각이 $c$개 있으면 길이 $k$짜리 비트열은 $2^k$가지뿐이니 대부분의 조각은 길이가 $\log_2 c$쯤은 되어야 하고, 그래서 조각들의 길이를 모두 더한 $n$은 적어도 $c \log_2 c$쯤입니다. 문자열이 서로 다른 짧은 조각으로 너무 많이 쪼개질 수는 없다는 이 비둘기집 같은 셈이 1976년 복잡도와 1977–78년 압축의 증명을 함께 떠받칩니다. 렘펠–지브 복잡도⁠(Lempel–Ziv complexity)⁠는 계산이 쉬워서 지금도 뇌파나 심장 박동의 규칙성, DNA 서열의 반복을 재는 데 널리 쓰입니다.

이 셈은 곧바로 압축이 되었습니다. 조각 하나를 '어디서 얼마나 베꼈는지와 새 글자'로 적으면 조각 수가 적을수록 짧아지고, 조각 수가 원천의 엔트로피⁠(entropy)⁠만큼 줄어들면 압축도 엔트로피에 다가갑니다. 1977년 논문(LZ77)은 앞의 글을 가리키는 참조로, 1978년 논문(LZ78)은 조각들을 번호 붙은 사전에 쌓는 방식으로 이것을 실현했고, 원천의 확률⁠(probability)⁠을 몰라도 한계에 다가가는 보편 압축⁠(universal compression)⁠이 되었습니다(자세한 이야기는 지브의 페이지와 렘펠–지브 압축에 있습니다). 1976년 논문에는 렘펠의 이름이, 1977년과 1978년 논문에는 지브의 이름이 먼저 적혀 있지만, 방법은 흔히 렘펠–지브, 줄여서 LZ라 불립니다.

이 방법은 1984년 테리 웰치의 LZW를 거쳐 유닉스의 compress와 GIF에, LZ77은 허프만 부호⁠(Huffman coding)⁠와 짝을 지은 디플레이트⁠(Deflate)⁠로 zip과 PNG에 들어가, 오늘날 거의 모든 컴퓨터와 전화기 안에서 날마다 돌고 있습니다. 렘펠은 대학 밖의 연구도 이끌었습니다. 1990년대에 하이파에 휼렛패커드 연구소의 이스라엘 지부를 세워 오랫동안 이끌었고, 2007년 압축에 대한 공로로 IEEE 리처드 해밍 메달을 받았습니다. 해밍 메달은 12년 전인 1995년 지브가 먼저 받은 상이기도 합니다. 렘펠은 2023년 2월 세상을 떠났고, 일곱 주 뒤 지브도 그 뒤를 따랐습니다.

이어지는 곳. 문자열 하나의 정보량이라는 생각은 콜모고로프 복잡도에서, 확률 원천의 정보량은 엔트로피와 원천 부호화 정리⁠(source coding theorem)⁠에서 이어집니다. 무작위란 더 줄일 수 없다는 뜻이라는 생각은 무작위성과 비둘기집 원리⁠(pigeonhole principle)⁠로, 드브라윈 수열과 한 붓 그리기는 오일러 경로⁠(Euler path)⁠와 오일러로, 평면에 그리는 그래프의 이야기는 4색 정리와 그래프로 이어집니다. 렘펠–지브의 참조 위에 부호를 얹는 방법은 허프만과 산술 부호화⁠(arithmetic coding)⁠에 있습니다.

관계.

• 영향을 받음 안드레이 콜모고로프 — 콜모고로프의 복잡도, 곧 문자열을 만들어 내는 가장 짧은 프로그램의 길이는 계산할 수 없으므로, 렘펠과 지브는 1976년 '앞에서 베끼기'만 허락하는 계산 가능한 복잡도를 대신 내놓았습니다.

연표.

• 1963년 테크니온 전기 공학과를 졸업하다
• 1967년 테크니온에서 박사 학위를 받고, 에번·체데르바움과 평면 그래프 판정 방법을 발표하다
• 1970년 드브라윈 그래프⁠(de Bruijn graph)⁠의 준동형으로 시프트 레지스터를 설계하는 논문을 내다
• 1976년 지브와 「유한 수열의 복잡도에 관하여」를 발표하다
• 1977년 지브와 앞의 글을 가리키는 압축(LZ77)을 발표하다
• 1978년 지브와 사전을 쌓는 압축(LZ78)을 발표하다
• 1982년 IEEE 펠로가 되다
• 2007년 IEEE 리처드 해밍 메달을 받다