정보이론과 압축 - 1

20 Oct 2008

다음 중 어떤 문자열이 더 많은 정보를 담고 있을까? 어떤 문자열이 더 복잡할까?

01010101010101010101010101010

11000101010001001000100100010

‘정보’나 ‘복잡도’의 정의를 명확히 내리지 않은 상태에서도 누구나 두번째 문자열을 가리킬 것이다. 그러면 왜 첫번째 문자열은 덜 복잡하고, 적은 양의 ‘정보’를 가지고 있다고 느껴질까? 간단한 접근 방법 한가지는 우리의 일상어를 가지고 문자열을 기술해 보는 것이다. 첫번째 문자열은 매우 쉽다. “‘01’이 xx 번 반복되는 문자열”이라고 하면 된다. 이 기술을 들은 사람은 첫번째 문자열을 다시 만들어 낼 수 있다. 반면에 두번째 문자열은 간단한 기술이 어렵다. “11000, 다음에 10이 세 번 반복되고, 001이 두 번 나오고, …”와 같이 말이 길어진다.

자연어를 이용한 위의 접근은 너무 단순해 보이지만, 사실 정보이론의 핵심 개념 중 하나인 Kolmogorov complexity (혹은 algorithmic entropy, 이하 KC) 를 잘 묘사하고 있다. 대강 말하자면, 주어진 문자열의 KC는 그 문자열을 만들어낼 수 있는 가장 짧은 프로그램의 길이로 정의한다. 어떤 문자열이 복잡하다거나 많은 정보를 담고 있다는 것의 의미는 곧, 그 문자열을 만들어내는데 긴 프로그램이 필요하다는 것이다. 하나마나한 소리 같을지도 모르겠다. 사실, KC는 추상적인 개념이며 Halting problem과 엮여 있어서 계산 가능하지도 않다. 하지만, 개념 자체는 매우 유용하게 쓰일 수 있다. 일례로, 우리는 매일 매일 컴퓨터에게 주어진 문자열의 KC 값 추정을 지시하고 있다. 무슨 소리냐고? 압축프로그램이 하는 일이 주어진 파일을 가능한 한 작은 크기를 가지도록 변환 – KC의 추정치를 계산 – 하는 것이기 때문이다.

Zip bomb라는 것이 있다. 시스템을 감시하고 있는 백신 소프트웨어들을 무력화 시키는 용도로 주로 쓰이는 압축 파일로, 맨 처음 예로 들었던 첫 문자열 ‘01010101…’ 과 같은 것이다. 이런 문자열은 아무리 길어도 매우 짧은 프로그램으로 기술할 수 있다 (압축이 잘 된다). Zip bomb는 이걸 극단적으로 응용한 것으로, 압축 프로그램을 일종의 프로그램 실행기로 보고 이 프로그램 실행기를 통해서 어마어마한 양의 출력을 내보내도록 설계된 프로그램이다. 위키백과에 의하면 ‘42.zip’ 이라는 유명한 zip bomb의 경우 파일 크기가 42 킬로바이트 정도에 불과하지만 압축을 모두 풀면 4.5 페타바이트 (~4500 테라바이트) 에 달하는 파일을 만들어 낸다.

더 재미난 예는 다음 글에서…