산술 부호화·BWT·델타 인코딩으로 구성하는 무손실 압축

압축 대상에 따라 달라지는 역할

저장 공간과 전송 비용을 줄이는 무손실 압축에서는 데이터의 분포와 처리 방식이 코덱 선택을 결정한다. 텍스트·로그·시계열·이미지를 다룰 때 산술 부호화, Burrows–Wheeler Transform(BWT), 델타 인코딩은 각각 엔트로피 부호화, 전처리, 차분 표현의 역할을 맡는다.

산술 부호화는 기호열을 [0,1) 구간 안의 하위 인터벌로 계속 좁힌 뒤 비트열로 내보내는 엔트로피 부호화 방식이다. 정적 테이블, 적응형 빈도, 컨텍스트 같은 확률 모델로 기호별 구간을 나누며, 정규화(renormalization) 과정에서 비트를 방출한다. 허프만 부호화보다 평균 엔트로피에 더 가까운 압축률을 낼 수 있고 비트 단위 정밀도로 확률을 반영한다. 반면 비트 오류가 뒤쪽까지 전파되기 쉬워 블록화와 체크섬이 필요하다.

BWT는 입력 문자열을 가역적으로 변환해 비슷한 문자가 모이도록 만드는 전처리다. 변환 자체가 압축을 수행하지는 않으며, 일반적으로 MTF(Rank/Move-To-Front), RLE, 산술 부호화·Range·ANS 같은 엔트로피 부호화와 이어 붙인다. 블록 기반으로 동작하므로 블록을 키우면 압축률은 좋아질 수 있지만 메모리 사용량과 지연도 늘어난다.

델타 인코딩은 연속한 값의 차이를 저장해 엔트로피를 낮춘다. 단조롭거나 점진적으로 변하는 시계열, 센서 값, 키 정렬 데이터에서 특히 효과적이다. 정수 데이터에는 ZigZag를 통한 부호 처리와 Golomb/Rice, Varint를 함께 쓸 수 있으며, 저엔트로피 차분에는 Golomb/Rice가 잘 맞는다.

압축 파이프라인에서 관리할 상태

산술 부호화는 입력을 받은 뒤 모델을 추정하고, 인터벌을 갱신하며, 정규화와 비트 방출을 거쳐 EOF 기호를 처리한다. 이 흐름에서는 언더플로와 오버플로를 피하기 위한 스케일링, 캐리 전파 제어가 필요하다. 확률 합이 0이 되거나 빈도가 포화되면 모델 리셋, 스케일 다운, 블록 재동기화로 복구 가능성을 확보한다.

BWT 기반 파이프라인은 보통 입력 → BWT → MTF(또는 RANK) → RLE → 엔트로피 부호화 순서로 구성한다. 반복 패턴이 많은 텍스트와 소스 코드에 강점이 있다. 블록 크기는 예를 들어 256KB~1MB 범위에서 선택할 수 있고, SA/ISA(접미 배열) 구현 방식도 성능과 메모리의 균형에 영향을 준다.

델타 스키마에는 1차·2차 차분 여부, ZigZag 같은 부호 처리, 클리핑·랩어라운드 같은 범위 제약을 명시해야 한다. 정수 폭과 오버플로 조건도 함께 고정한다. 차분 뒤에는 Rice, Golomb, 산술 부호화 중 데이터 분포에 맞는 엔트로피 부호화를 선택하며, 분산이 낮은 차분 분포에는 Rice가 경량·고속이다.

스트리밍 환경에서는 산술 부호화가 적합하고, BWT는 블록 단위 병렬 처리에 맞는다. 델타 인코딩은 두 방식 모두에 사용할 수 있지만 초기 상태(seed)를 관리해야 한다. 블록 헤더에 동기화 마커, CRC32/XXH3, 모델 스냅샷을 넣으면 손상 후 복구 범위를 제한할 수 있다.

부호화기 상태는 부동소수점보다 정수 고정소수점으로 다루는 편이 플랫폼 간 비일관성을 줄인다. 입력 검증으로 블록 크기와 빈도 테이블 오염을 막고, 오류 전파에 민감한 산술 부호화에는 짧은 블록과 주기적 체크포인트를 둔다. 메모리가 제한된 환경이라면 Rice와 Varint를 우선 검토할 수 있다.

텍스트와 시계열에서의 조합

텍스트나 소스 코드 저장에는 BWT, MTF, RLE, Arithmetic Coding을 연결할 수 있다. 블록 크기는 512KB~1MB 범위에서 두고 MTF 히스토리 길이를 조정하며 EOF 심볼을 명시한다. 버전 관리 압축을 패치와 결합할 때는 가변 블록과 콘텐츠 정의 청킹(CDC)을 사용해 변경 전파를 줄일 수 있다.

시계열·센서·로그 데이터는 Delta(1차/2차) + ZigZag → Rice/AC 구조로 처리할 수 있다. 타임스탬프에는 Delta-of-Delta를, 값에는 스케일 정규화 후 델타를 적용한다. 4KB~64KB 같은 블록 프레이밍과 리샘플링·결측 처리 규칙을 명시해야 복원 과정이 흔들리지 않는다.

컬럼 지향 저장소와 데이터 웨어하우스에서는 정렬 키에 Delta+RLE를 적용하고, 카디널리티가 낮은 컬럼에는 사전+RLE를, 잔차에는 AC/ANS를 적용할 수 있다. 파티션과 세그먼트를 블록화하면 병렬 질의에 유리하며, 메타데이터에는 최솟값·최댓값·스케치를 포함한다.

엣지와 임베디드 환경에서는 산술 부호화 대신 Rice나 Varint로 연산량을 낮출 수 있다. 정수 고정소수점과 제한된 버퍼를 이용한 순방향 스트리밍 처리가 적합하며, 온디바이스 경량 압축과 게이트웨이 고압축을 결합한 주기적 원시 덤프 전략도 사용할 수 있다.

압축률과 복구성 사이의 선택

텍스트에서는 BWT+AC가 DEFLATE 대비 515%p 개선된 사례가 관측됐으며, 데이터 특성에 의존하므로 최신 정보 확인이 필요하다. 시계열에서는 Delta+Rice가 원시 데이터 대비 310배, Varint 대비 20~40% 향상을 기대할 수 있다.

블록 병렬화로 다중 코어를 활용하면 처리량이 26배 개선될 수 있다. 다만 BWT의 큰 블록은 압축 비율을 높이는 대신 지연을 증가시킨다. 1TB/월 전송 기준으로 30%를 추가 절감하면 네트워크 비용이 월 수백 달러수천 달러 줄어들 수 있으며, 실제 절감액은 단가 가정에 따라 달라진다. 블록화와 CRC를 함께 사용하면 손상 범위를 국소화해 재처리 비용을 50% 이상 줄일 수 있다.

기법	성능(압축률/속도)	확장성(블록/스트리밍)	일관성(재현/모델)	안정성(에러 민감도)	운영 편의(구현/지원)
Arithmetic Coding	압축률 우수, 속도 중간	스트리밍 우수, 블록도 가능	정수 고정소수점 권장, 모델 관리 필요	비트 에러 전파 큼, 블록화·CRC 필요	구현 난도 중~상, 라이브러리 보급 중
BWT(전처리)	압축률 향상 기여, 속도 블록 크기 의존	대블록 처리/병렬화 우수, 스트리밍 부적합	결정적, SA 구현 선택 영향	블록 손상 시 해당 블록만 영향	구현 난도 중, 성숙한 구현 다수
Delta Encoding	데이터 특성 의존, 시계열에 고효율	스트리밍·블록 모두 적합	규칙/초기값 고정 시 재현성 높음	노이즈 크면 효율 저하	구현 용이, 경량 코덱 다수

데이터 유형별 인코딩 경로

⤢✕

운영 조건을 압축 포맷에 반영하기

블록 크기는 256KB~1MB에서 시작해 메모리와 지연 예산 안에서 최대값을 찾는다. 블록이 커질수록 압축률은 올라가지만 오류 영향 범위도 커진다. 주기적인 동기화 마커, 블록별 CRC32/XXH3, 산술 부호화 상태 스냅샷은 손상 국소화에 사용한다.

텍스트에는 n-gram 같은 컨텍스트 모델과 산술 부호화를 결합할 수 있고, 시계열에는 델타 뒤에 저복잡 코덱을 둔다. 데이터 드리프트가 있다면 적응형 모델을 사용할 수 있지만, 재현성이 요구되면 정적 모델을 고정해야 한다. BWT와 블록 파이프라인은 병렬 처리하고, 산술 부호화는 블록 단위로 병렬화하되 블록 간 모델은 독립적으로 유지한다.

플랫폼 간 결과를 일정하게 만들려면 부동소수점 대신 32/64비트 정수 고정소수점을 사용한다. 입력 길이와 블록 크기 상한, 사전 할당, 타임아웃을 설정하고, 비정상 분포를 유도하는 공격을 막기 위한 모델 스케일링·리셋 조건도 정한다.

텍스트 파이프라인은 BWT → MTF/RLE → AC, 시계열 파이프라인은 Delta → Rice/AC로 분리해 설계할 수 있다. 압축률, 복구성, 지연은 블록 크기와 코덱 선택, 모델링 복잡도에 따라 함께 조정해야 한다.