비주기적 구조는 결코 붕괴하지 않는다: 무손실 압축을 위한 피보나치 계층 구조

기존의 계층적 데이터 압축 방식은 일정 깊이 이상에서 구조가 무너지는 한계가 있었으나, 이 논문은 피보나치 준결정 구조를 활용해 무한히 확장 가능한 비주기적 계층을 제안한다. 이를 통해 대규모 데이터셋에서 장거리 의존성을 효과적으로 포착하며, 실제 1GB 실험에서 bzip2를 능가하고 xz에 근접하는 성능을 증명했다.

기존의 LZ77 같은 압축 알고리즘은 고정된 윈도우 내에서 반복되는 패턴을 찾는다. 하지만 데이터 규모가 커질수록 더 먼 곳에 있는 긴 문맥을 참조해야 하는데, 일반적인 주기적 계층 구조는 특정 깊이 이상으로 가면 유효한 매칭 위치가 사라지는 '구조적 붕괴' 현상이 발생한다. 이는 마치 격자무늬 위에 다른 격자를 겹칠 때 특정 지점에서 무늬가 어긋나 더 이상 겹치지 않는 것과 유사하다.

이 논문은 황금비(φ)를 기반으로 한 피보나치 준결정 타일링을 도입하여 이 문제를 해결한다. 피보나치 수열은 비주기적이면서도 수학적으로 매우 정밀하게 제어된 구조를 가진다. 이 구조를 압축의 가이드라인으로 삼으면, 모든 계층 깊이에서 두 가지 타일 유형(L, S)이 항상 일정한 비율로 공존하게 된다. 이는 수학적으로 황금비가 PV 수라는 특수한 성질을 가지기 때문에 가능하며, 덕분에 계층이 무한히 깊어져도 룩업 위치가 고갈되지 않는다.

결과적으로 144개 이상의 단어로 이루어진 매우 긴 구절도 모든 위치에서 기하학적으로 결정된 참조 지점을 가질 수 있다. 이는 대규모 언어 모델이 처리하는 긴 문맥 데이터의 중복성을 제거하는 데 최적의 구조를 제공하며, 데이터가 커질수록 압축 효율이 선형적으로 증가하는 결과를 낳는다.

입력 텍스트를 단어 단위로 토큰화한 후, 36개의 비주기적 타일링 후보(12개의 황금비 위상, 6개의 무리수 타일링, 18개의 최적화된 타일링)를 각 블록에 적용하여 가장 높은 점수를 얻는 구조를 선택한다. 점수는 각 타일 위치 k에서 적용 가능한 가장 깊은 계층 ℓ(k)에 대해 지수적으로 증가하는 보너스 b_ℓ을 합산하여 계산한다.

선택된 타일링을 바탕으로 11단계의 피보나치 수 {1, 2, 3, 5, ..., 144} 길이에 대응하는 다단계 코드북을 구축한다. [단어 시퀀스 입력 → 피보나치 타일링 규칙 적용 → 각 위치별 최적 n-gram 매칭 → 인덱스 번호 출력] 과정을 거치며, 각 단계의 코드북은 빈도순으로 정렬되어 관리된다.

계층 구조의 각 단계에서 발생하는 선택 정보(Hit/Miss flag)는 Order-2 문맥 모델을 사용하는 산술 부호화(Arithmetic Coding)를 통해 압축된다. [이전 두 단계의 레벨 정보 입력 → 144개의 특화된 확률 모델 적용 → 현재 레벨 부호화 → 압축 비트스트림 출력] 순으로 연산이 수행된다. 어휘 외 단어(OOV)는 별도의 LZMA 스트림으로 분리하여 구조적 무결성을 유지하며 최종 파일을 조립한다.

1GB 규모의 Wikipedia 데이터(enwik9) 실험에서 Quasicryth v5.6은 22.59%의 압축률을 달성했다. 이는 bzip2의 25.40%를 명확히 앞지르는 수치이며, 고성능 압축기인 xz의 21.57%에 근접한 성능이다. 특히 데이터 크기가 커질수록 비주기적 계층의 이점이 극대화되어, 100MB에서 1GB로 데이터가 늘어날 때 압축 이득이 33배 급증하는 현상을 보였다.

A/B 테스트 결과, 동일한 조건에서 주기적 구조(Period-5)는 계층 깊이 4단계에서 붕괴하여 더 이상의 압축 이득을 얻지 못한 반면, 피보나치 계층은 89-gram과 144-gram 수준의 깊은 매칭을 성공적으로 수행했다. enwik9에서 89-gram 매칭은 5,369회, 144-gram 매칭은 2,026회 발생하여 대규모 데이터에서의 장거리 중복 제거 능력을 입증했다.

피보나치 치환 규칙 σ: L → LS, S → L의 역변환인 Deflation을 반복 적용하여 다단계 계층을 구축한다. 각 계층 k에서의 슈퍼 타일은 F_{k+2} 단어 길이를 커버하며, Perron-Frobenius 고유벡터 v1 = [φ, 1]^T / (φ+1) 분석을 통해 모든 계층에서 L과 S 타일의 비율이 정확히 황금비(φ)로 유지됨을 보장한다. 이는 주기적 타일링이 ⌈log_φ(p)⌉ 수준에서 붕괴하는 것과 대조적이다.

Sturmian 시퀀스의 특성인 최소 인자 복잡도 p(n) = n+1을 활용하여 코드북 효율 η_m = C_m / (F_m + 1)을 극대화한다. 이는 임의의 비주기적 이진 타일링 중 피보나치 타일링만이 계층 비붕괴와 최대 코드북 효율을 동시에 만족하는 유일한 구조임을 의미한다. 또한 Weyl의 균등분포 정리에 의해 타일 밀도가 전 계층에서 균일하게 유지되어 코드북 항목의 활용도가 극대화된다.

구현 측면에서는 24비트 정밀도의 산술 부호화기와 Fenwick-tree 가속 구조를 사용하며, 64개 항목의 Recency Cache를 통해 빈번한 인덱스를 빠르게 처리한다. 압축 과정은 36개의 타일링 후보를 모두 평가하는 비대칭적 구조를 가지지만, 복원 시에는 헤더의 2바이트 위상 정보만으로 전체 타일링을 결정론적으로 재구성할 수 있어 매우 빠른 복원 속도를 제공한다.

현재 구현은 단어 단위(Word-level) 압축에 특화되어 있어 바이트 단위의 미세한 중복 제거에는 한계가 있을 수 있다. 또한 압축 시 36개의 타일링 후보를 모두 스캔하고 대규모 코드북을 구축해야 하므로, 압축 속도가 bzip2 등 기존 방식에 비해 상대적으로 느리다.