만물을 유일한 숫자로 대응시키는 방법에 관한 생각

 

시작은 파일 압축 이야기로부터..

SSD라 그런가.. 파일 복사를 여러개로 쪼개서 실행하는게 왜 더 빠른거같지?

 

IT 업계 종사자인 지인이 낮에 뜬금없이 위와 같이 화두를 던졌다. 저장장치 간 파일 이동작업을 많이 해본 사람은 알겠지만, 파일 갯수가 몇십만 개 급으로 많을 경우 전체를 압축해서 옮긴 다음 압축을 푸는 것이 빠른 경우가 많다. 이 사람도 이걸 모르진 않을 텐데, 질문을 던진 것이 의아했다. 하여간 관련해서 파일 이동시 병목이 CPU인지 램인지 저장장치인지에 관해서 약간의 이야기가 오갔다. 결국 직접 해 보니 압축해서 옮기는 것이 더 빨랐고, CPU를 100%로 갈구기 위해 폴더별로 압축을 해서 압축과 이동을 동시에 하니 더 빨라졌다. 그런데 압축 얘기를 하다 보니, 그 동안 압축 알고리즘도 제대로 모르고 압축 프로그램들을 쓰고 있었다는 생각이 들었다. 안그래도 최근에 VS code랑 디코의 리사이징시 렉걸리는 문제때문에 퍼포먼스와 효율성에 관한 관심이 높아지고 있던 차에, 압축 알고리즘도 모르면서 효율성같은걸 생각하고 있는 데에 갑자기 자존심이 상했다. 그래서 생각난 김에 압축 알고리즘을 알아보기로 했다.

 

zip 파일 구조 파악과 PK0102

역시 압축 하면 대중적으로 가장 많이 쓰이는 것이 zip 포맷일 것이다. 잠깐 검색해보니 생각보다 구조는 단순했다.

http://www.softlab365.com/wordpress/?p=478 

zip 파일 포맷 간단히 알아보기

대충 파일 맨 뒤쪽에 파일 목록들과 각 파일 헤더 오프셋 주소값들을 모아놓은 central directory 영역이 있고, 앞쪽의 각 파일의 헤더에 파일명, 파일 길이, 압축 방식 등을 적어놓는 방식이었다. 그리고 각 영역은 PK로 시작하는 시그니처 바이트들로 구별하게 되어 있었다. PK는 zip 포맷을 처음 개발한 Phil Katz의 이름을 딴 것으로 추정되는데, 자기 이름을 마패로 파일에 박아버리는 포맷을 만들었더니 그게 사실상의 표준이 되어 수많은 zip 파일들에 들어있는 거였다. 자세한 포맷 스펙은 다음의 문서에서 살펴볼 수 있다.

https://support.pkware.com/home/pkzip/developer-tools/appnote/application-note-archives

 

이게 진짜인가 싶어서 얼마 전에 반디집으로 압축했던 파일을 hex로 열어보니 다음과 같이 정말로 PK로 시작하는 바이트 시퀀스를 다수 찾을 수 있었다. 아마 디지털 시대에 전 지구로 자기 이름을 가장 많이 뿌린 사례가 아닐까 싶다..

바이너리 코드는 보기가 힘들었지만 zip 포맷 스펙과 대조해가면서 hex를 읽다 보니 하나의 zip 안에서도 파일별로 다른 알고리즘을 사용해서 압축할 수 있다는 것을 알게 되었다 (위에 워드프레스 글에서도 해당 언급이 나온다). 그리고 영문 위키를 보니 가장 많이 쓰이는 압축 알고리즘이 deflate라는 방식인 것으로 확인했다. 그래서 그거만 정복하면 나도 직접 zip 파일로 압축할 수 있는 프로그램을 짤 수 있겠다고 생각했다.

 

Deflate 알고리즘과 Huffman coding

deflate 방식도 잠깐 검색해 보니 RFC 1951 문서에 깔끔하게 정리되어 있었다. 

https://datatracker.ietf.org/doc/html/rfc1951

RFC 1951 - DEFLATE Compressed Data Format Specification version 1.3

정독하면서 보니 Huffman coding과 LZ77 알고리즘을 적절히 섞어서 만든게 deflate 알고리즘인 것이었다. 그런데 허프만 코딩의 예시로 다음 그림을 보니 떠오르는 생각이 있었다.

                          /\              Symbol    Code
                         0  1             ------    ----
                        /    \                A      00
                       /\     B               B       1
                      0  1                    C     011
                     /    \                   D     010
                    A     /\
                         0  1
                        /    \
                       D      C

각 문자를 기호로 취급하고 이걸 이진 숫자로 변환한다니, 어디서 많이 보던 그림인데?

 

괴델의 불완전성 정리와 일반 문장을 숫자로 바꾸는 법에 관한 의문

허프만 코딩의 예시를 보자마자 예전에 흥미롭게 봤던 다음의 영상이 떠올랐다. (영어 자막 있음)

https://youtu.be/HeQX2HjkcNo?t=917 

 

이 영상을 보면 괴델이 각종 수학기호를 숫자로 변환하는 규약을 만들고, 그걸로 명제를 숫자로 바꾸는 규칙을 세운 다음, '참이지만 증명 불가능한 명제가 있다'는 것을 수학적으로 증명한 사례가 나온다. 예전에도 그랬지만 다시 봐도 괴델의 천재적인 발상은 놀라웠다.

 

소인수분해는 유일하다는 것을 역이용해서 괴델 넘버로 변환한 문장들을 2 3 5 7로 시작하는 소수의 지수로 배치한 후 다 곱해버리면, 해당 문장이 갖는 유일하고 1:1로 대응되는 숫자를 얻는다는 생각이었다. 모든 명제가 각각 유일한 하나의 숫자로 변환될 수 있다니... 과거의 나는 이거야말로 궁극의 인코딩이 아닐까 라는 생각을 했었다.

 

그런데 계속 궁금했던 부분이 특정 언어와 논리 기호들로 표현된 문장을 어떻게 숫자로 바꾸냐는 것이었다. 해당 영상에서는 논리 기호에 대한 괴델 넘버로의 변환만 예시로 들 뿐 일반 문장, 예를 들면 사람의 수명은 유한하다 같은 것들은 어떤 규칙으로 변환하는지에 대해 언급하지 않았다. 괴델의 논문을 찾아서 읽지는 않았지만 아마도 그러한 변환이 존재한다고 가정하고 모순을 보이는 것이 주 목적이었기 때문에 변환 규칙에 관해서는 깊이 다루지는 않았을 것으로 추정했다. 그런데 위의 허프만 코딩을 보고 갑자기 뒤통수를 딱 맞은 것 같은 기분이 들었다.

 

UTF-8 인코딩은 문자 및 기호를 숫자로 변환하는 규칙이었다

사실 맨 앞의 압축파일을 떠올려 보면, 어떤 언어로 구성되어 있는 문서나 프로그램을 전부 숫자로 변환한 것이 아닌가? 그리고 그것의 근간이 되는 규칙이 유니코드, 대표적으로 UTF-8이었던 것이다. 물론 온 세상의 언어가 UTF-8로 구현된 것은 아니지만 다수의 언어들에 대해 전 인류가 대체로 동의하는 방식으로 이미 숫자와 1:1 대응을 시키는 규칙을 과거의 사람들이 만들어놨던 것이다. 당연히 우리 한글도 고대 한글을 포함해서 가능한 거의 모든 조합에 대해 유니코드 주소를 부여받았다. 자세한 언어 목록은 다음의 문서에 정리되어 있다.

http://www.unicode.org/charts/index.html

Unicode 14.0 Character Code Charts

그리고 UTF-8같은 경우 가변 바이트이기 때문에 차후에 계속 뭔가가 추가되더라도 확장 가능한 규칙이다. 모든 UTF-8 규칙에 대한 테이블은 다음 사이트에서 확인할 수 있다. 일반 언어뿐만 아니라 음표 기호라든지 수학 기호라든지 하는 것들이 모두 유니코드에 대응되는 주소를 갖고 있다.

https://www.charset.org/utf-8

UTF-8 code page

이것을 이용하면 언어로 표현 가능한 모든 문서, 명제, 그리고 생각 등등을 앞의 괴델의 방법을 통해 유일하게 대응되는 괴델 숫자로 변환할 수 있는 거였다..

 

문자로 표현되지 않는 것들에 대한 변환으로 확장 및 한계점

위의 생각을 좀 더 확장하면, 각종 사물이나 사람도 원자 배열 등을 숫자로 변환하는 규칙을 정하면 유일하게 대응되는 괴델 숫자로 변환할 수가 있다고 볼 수 있다. 즉, 맨 앞의 그림에서 표현하였듯이 대한민국 헌법같이 문자로 표현 가능한 경우뿐만 아니라 안드로메다 은하같은 거대 천체나 유재석 씨 같은 사람도 단 하나의 숫자로 변환해버릴 수가 있는 것이다.

 

그리고 이것이 NFT에서 쓰이는 원리와 유사한 것이 아닐까 라고 생각했다. NFT는 아직까지는 사물에만 적용되지만 내가 생각한 방법으로 확장을 시키면 우리가 상상 가능한 모든 것을 유일하게 대응되는 숫자로 변환할 수 있는 것이다. 만약 이 값을 우주 시뮬레이션의 입력값으로 사용한다면? 역시 괴델이 제창한 방법의 엄청난 파급력을 다시금 느낄 수 있는 지점이다.

 

그리고 압축파일에서 알아본 deflate 알고리즘 등으로 원래 정보를 압축한 다음 괴델 숫자로 변환하면 괴델 숫자를 얻는 데에 걸리는 시간이 많이 줄어들 것으로 생각할 수 있다.

 

물론 나만 이런 생각을 했을리는 없고, 이미 많은 사람들이 이런 생각을 했을 것이다. 그리고 나도 물론 괴델의 방법으로 변환한 숫자가 소수의 지수에 정보를 저장하는 방법이기 때문에 엄청나게 비효율적이고 큰 숫자를 만들어 낸다는 사실을 안다. 나중에 해당 숫자를 입력으로 받았을 때 원래대로 디코딩하기 위해 소인수분해가 들어간다는 점도 이것을 실질적으로 이용하고자 할 때 걸림돌이 되는 부분이다.

 

결론

언급했던 단점들을 감안하더라도, 모든 정보를 단 하나의 숫자로 변환해서 저장할 수 있음을, 그리고 그 숫자가 변환 전 정보와 유일한 대응이 되는 규칙을 만들 수 있다는 것은 매우 흥미로웠다. 원래는 압축 파일을 알아보자고 시작한 건데 생각이 여기에까지 다다르게 된 점에 대해 나 자신도 놀랐다. 오늘의 생각이 한낱 망상일 수도 있겠지만, 먼 미래에 엄청난 연산능력을 가진 컴퓨터가 나온다면 정말로 이런 방식으로 정보를 저장할 수도 있지 않을까? 생각은 이쯤에서 마치기로 한다.