맨위로가기

비손실 압축

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

비손실 압축은 데이터를 압축하여 저장 공간을 절약하면서 원본 데이터를 완벽하게 복원할 수 있는 기술이다. 이 기술은 통계적 모델을 사용하여 데이터를 비트 시퀀스로 매핑하며, 허프만 코딩과 산술 코딩이 주요 인코딩 알고리즘으로 사용된다. 정적 모델과 적응형 모델의 두 가지 통계 모델 구성 방식이 있으며, 압축하려는 데이터 유형에 따라 다양한 알고리즘이 존재한다.

LZ77 및 LZ78 기반의 렘펠-지브 압축을 비롯하여 Deflate, LZMA, LZSS, LZW, Burrows–Wheeler 변환, PPM, 런 길이 인코딩 등 다양한 기술들이 사용된다. 이러한 기술들은 텍스트, 오디오, 이미지, 비디오, 유전체 데이터, 실행 파일 등 다양한 분야에서 활용된다.

그러나 모든 데이터를 효율적으로 압축할 수 있는 알고리즘은 존재하지 않으며, 비둘기집 원리에 의해 압축 후 데이터 크기가 증가하는 경우도 발생할 수 있다. LZW와 같은 일부 압축 기술은 과거에 특허 분쟁의 대상이 되었으며, 현재는 특허가 만료되었다. 비손실 압축 알고리즘과 구현체는 정기적으로 벤치마크에서 테스트되며, 압축률과 속도를 비교하는 다양한 벤치마크가 존재한다.

더 읽어볼만한 페이지

  • 데이터 압축 - 해상도
    해상도는 1인치당 픽셀 또는 점의 수를 나타내는 지표로, 이미지의 선명도를 결정하며 DPI와 PPI 단위를 사용하고, 높을수록 섬세한 표현이 가능하다.
  • 데이터 압축 - MP3
    MP3는 MPEG 표준의 오디오 압축 형식으로, 인간의 청각 심리를 이용하여 음질 저하를 최소화하며 데이터를 압축하고, 1991년에 발명되어 2017년 특허 만료로 퍼블릭 도메인이 되었다.
  • 무손실 압축 알고리즘 - VP9
    VP9는 구글이 개발한 오픈 소스 비디오 코덱으로, VP8보다 압축 효율을 높이고 HEVC보다 나은 성능을 목표로 개발되었으며, WebM 형식으로 사용되고 주요 웹 브라우저와 넷플릭스, 유튜브 등에서 지원했으나 AV1의 등장으로 개발이 중단되었다.
  • 무손실 압축 알고리즘 - FLAC
    FLAC은 조시 콜슨이 개발한 무손실 오디오 코덱으로, 원본 음질을 유지하면서 파일 크기를 줄이기 위해 오디오 데이터를 압축하며, 4~32비트 샘플 크기, 최대 8 채널을 지원하고, 미국 국립 문서 기록 관리청에서 디지털 오디오에 선호되는 형식으로 지정되었다.
비손실 압축

2. 무손실 압축의 원리 및 기술

비손실 압축은 데이터의 중복성을 제거하거나 효율적인 표현 방식을 사용하여 파일 크기를 줄이는 방법이다.

대부분의 비손실 압축 프로그램은 두 가지 단계를 거친다. 먼저 입력 데이터의 통계적 모델을 생성하고, 이 모델을 사용하여 입력 데이터를 비트 시퀀스에 매핑한다. 이때 "확률적인"(자주 발생하는) 데이터는 "확률적이지 않은" 데이터보다 짧은 출력을 생성한다.

비트 시퀀스를 생성하는 데 사용되는 주요 인코딩 알고리즘은 허프만 코딩(deflate 알고리즘)과 산술 코딩이다. 산술 코딩은 정보 엔트로피에 의해 주어지는 최상의 압축률에 근접하지만, 허프만 압축은 더 간단하고 빠르다. 그러나 허프만 압축은 기호 확률이 1에 가까운 모델에서는 성능이 좋지 않다.

통계 모델을 구성하는 주요 방법에는 정적 모델과 적응형 모델이 있다. 정적 모델에서는 데이터를 분석하고 모델을 구성한 다음, 이 모델을 압축된 데이터와 함께 저장한다. 이 방식은 단순하고 모듈성이 뛰어나지만, 모델 자체를 저장하는 데 비용이 많이 들 수 있다. 또한 압축되는 모든 데이터에 대해 단일 모델을 사용해야 하므로 이질적인 데이터를 포함하는 파일에서는 성능이 저하된다. 적응형 모델은 데이터가 압축됨에 따라 모델을 동적으로 업데이트한다. 인코더와 디코더는 모두 사소한 모델로 시작하여 초기 데이터의 압축률이 낮지만, 데이터에 대해 더 많이 학습함에 따라 성능이 향상된다. 현재 실제로 사용되는 대부분의 인기 있는 압축 유형은 적응형 코더를 사용한다.

비손실 압축 방법은 압축하도록 설계된 데이터 유형에 따라 분류될 수 있다. 원칙적으로 모든 범용 비손실 압축 알고리즘은 모든 유형의 데이터에 사용할 수 있지만, 많은 알고리즘은 압축하도록 설계된 형식의 데이터에 대해 상당한 압축을 달성할 수 없다. 텍스트에 사용되는 많은 비손실 압축 기술은 인덱싱된 이미지에도 상당히 잘 작동한다.

모든 데이터를 효과적으로 압축할 수 있는 무손실 압축 알고리즘은 존재하지 않는다. 따라서 데이터 종류에 따라 많은 알고리즘이 존재한다.

2. 1. 통계적 모델링

대부분의 비손실 압축 프로그램은 두 단계를 거쳐 작동한다. 첫 단계에서는 입력 데이터의 ''통계적 모델''을 만들고, 두 번째 단계에서는 이 모델을 사용하여 입력 데이터를 비트 시퀀스로 바꾼다. 이때 "자주 나오는"(확률이 높은) 데이터는 "자주 나오지 않는" 데이터보다 짧게 출력된다.

비트 시퀀스를 만드는 데 주로 사용되는 인코딩 알고리즘에는 허프만 코딩(deflate 알고리즘)과 산술 코딩이 있다. 산술 코딩은 정보 엔트로피에 의해 결정되는, 이론상 가능한 최고의 압축률에 가깝게 데이터를 압축할 수 있다. 반면 허프만 압축은 더 간단하고 빠르지만, 기호 확률이 1에 가까운 경우에는 압축 효율이 떨어진다.

통계적 모델을 만드는 방법에는 크게 두 가지가 있다. ''정적'' 모델은 데이터를 분석하여 모델을 만든 후, 이 모델을 압축된 데이터와 함께 저장한다. 이 방법은 단순하고 모듈 방식이지만, 모델 자체를 저장하는 데 추가 공간이 필요하다. 또한 모든 데이터에 대해 하나의 모델만 사용하기 때문에, 다양한 종류의 데이터가 섞여 있는 파일에서는 압축 효율이 낮아질 수 있다. ''적응형'' 모델은 데이터가 압축되는 과정에서 모델을 계속 업데이트한다. 인코더와 디코더는 모두 간단한 모델에서 시작하여 초기에는 압축률이 낮지만, 데이터에 대해 더 많이 알게 될수록 압축 성능이 좋아진다. 실제로 사용되는 대부분의 인기 있는 압축 방식은 적응형 코더를 사용한다.

2. 2. 엔트로피 인코딩

대부분의 비손실 압축 프로그램은 두 단계를 거칩니다. 첫 단계는 입력 데이터의 통계적 모델을 만드는 것이고, 두 번째 단계는 이 모델을 사용하여 입력 데이터를 비트 시퀀스에 매핑하여 자주 발생하는 데이터가 그렇지 않은 데이터보다 짧은 출력을 생성하도록 합니다.

비트 시퀀스를 생성하는 주요 인코딩 알고리즘에는 허프만 코딩(deflate 알고리즘)과 산술 코딩이 있습니다. 산술 코딩은 정보 엔트로피에 의해 주어지는 최상의 압축률에 근접하지만, 허프만 압축은 더 간단하고 빠릅니다. 하지만 허프만 압축은 기호 확률이 1에 가까운 모델에서는 성능이 좋지 않습니다.

통계 모델을 구성하는 방법에는 정적 모델과 적응형 모델이 있습니다. 정적 모델은 데이터를 분석하여 모델을 구성하고 압축된 데이터와 함께 저장합니다. 이 방식은 단순하지만 모델 저장 비용이 들고 이질적인 데이터에는 성능이 떨어집니다. 적응형 모델은 데이터가 압축됨에 따라 모델을 동적으로 업데이트합니다. 인코더와 디코더는 초기에는 낮은 압축률을 보이지만, 데이터 학습에 따라 성능이 향상됩니다.

엔트로피 인코딩의 종류는 다음과 같습니다.

  • ANS – LZFSE 및 Zstandard에서 사용됩니다.
  • 산술 코딩
  • 허프만 코딩 - 다른 알고리즘과 잘 결합됩니다.

2. 3. 사전 기반 압축

LZ77 및 LZ78은 사전 기반 알고리즘으로, 많은 다른 알고리즘의 기초가 된다.

  • Deflate는 LZ77 압축과 허프만 코딩을 결합하여 ZIP, gzip, PNG 이미지에서 사용된다.
  • 렘펠-지브-마르코프 체인 알고리즘(LZMA)은 매우 높은 압축률을 제공하며, 7z 및 xz에서 사용된다.
  • 렘펠-지브-스토러-시만스키(LZSS)는 허프만 코딩과 함께 WinRAR에서 사용된다.
  • 렘펠-지브-웰치(LZW)는 GIF 이미지 및 Unix의 `compress` 유틸리티에서 사용된다.

2. 4. 기타 기술


  • Burrows–Wheeler 변환: 텍스트 데이터를 더 압축하기 쉽도록 변환하는 전처리 기술로, bzip2에서 사용된다.
  • 부분 일치 예측(PPM): 일반 텍스트 압축에 최적화된 알고리즘이다.
  • 런 길이 인코딩(RLE): 연속적으로 반복되는 데이터를 효과적으로 압축하는 간단한 방식이다.

3. 다양한 분야에서의 활용

무손실 압축은 다양한 종류의 데이터를 압축하는 데 사용된다. 모든 데이터를 효과적으로 압축할 수 있는 무손실 압축 알고리즘은 존재하지 않기 때문에([#무손실 압축의 한계|무손실 압축의 한계] 절 참조) 데이터 종류에 따라 많은 알고리즘이 존재한다.

3. 1. 일반 데이터


  • ANS – LZFSE 및 Zstandard에서 사용되는 엔트로피 인코딩 방식이다.[1]
  • 산술 코딩 – 엔트로피 인코딩 방식이다.[1]
  • Burrows–Wheeler 변환 – 텍스트 데이터를 더 압축하기 쉽게 만드는 가역적 변환으로, bzip2에서 사용된다.[1]
  • 허프만 코딩 – 엔트로피 인코딩 방식으로, 다른 알고리즘과 잘 결합된다.[1]
  • 렘펠-지브 압축(LZ77 및 LZ78) – 많은 다른 알고리즘의 기초가 되는 사전 기반 알고리즘이다.[1]
  • * Deflate – LZ77 압축과 허프만 코딩을 결합하여 ZIP, gzip, 및 PNG 이미지에서 사용된다.[1]
  • * 렘펠-지브-마르코프 체인 알고리즘(LZMA) – 매우 높은 압축률을 가지며, 7zip 및 xz에서 사용된다.[1]
  • * 렘펠-지브-스토러-시만스키(LZSS) – 허프만 코딩과 함께 WinRAR에서 사용된다.[1]
  • * 렘펠-지브-웰치(LZW) – GIF 이미지 및 Unix의 `compress` 유틸리티에서 사용된다.[1]
  • 부분 일치 예측(PPM) – 일반 텍스트 압축에 최적화되어 있다.[1]
  • 런 길이 인코딩(RLE) – 동일한 값의 연속(런)이 많은 데이터를 효과적으로 압축하는 간단한 방식이다.[1]

3. 2. 오디오

FLAC, 애플 무손실(ALAC), 웨이브팩(WavPack), 몽키 오디오(Monkey's Audio APE), TTA 등 다양한 무손실 오디오 코덱이 존재한다. MPEG-4 ALS, MPEG-4 SLS(HD-AAC), 돌비 트루HD, DTS-HD 마스터 오디오 등 고음질 오디오 포맷도 무손실 압축을 사용한다.

3. 3. 이미지

PNG, GIF는 무손실 압축을 지원하는 대표적인 이미지 포맷이다.[5] JPEG 2000, JPEG-LS, JPEG XL, WebP, AVIF, HEIF 등은 무손실 압축 옵션을 제공한다.

3. 4. 비디오

무손실 비디오 코덱은 원본 화질을 유지해야 하는 영상 편집, 보관 등의 분야에서 활용된다.

무손실 비디오 코덱을 참조하라.

3. 5. 유전체 데이터

유전체 압축 알고리즘 (유전 알고리즘과는 혼동하지 말 것)은 일반적인 압축 알고리즘과 유전 데이터에 맞춰진 특정한 알고리즘을 모두 사용하여 데이터를 압축하는 (일반적으로 뉴클레오티드 서열) 최신 세대의 무손실 알고리즘이다. 2012년, 존스 홉킨스 대학교의 과학자 팀은 압축을 위해 외부 유전 데이터베이스에 의존하지 않는 최초의 유전 압축 알고리즘을 발표했다. HAPZIPPER는 HapMap 데이터에 맞춰졌으며, 20배 이상의 압축(파일 크기 95% 감소)을 달성하여, 선두적인 범용 압축 유틸리티보다 2~4배 더 나은 압축 성능을 훨씬 빠르게 제공한다.[10]

유전체 시퀀스 압축 알고리즘은 DNA 시퀀스 압축기라고도 하며, DNA 시퀀스가 역반복과 같은 특징적인 속성을 가지고 있다는 사실을 탐구한다. 가장 성공적인 압축기는 XM과 GeCo이다.[11] 진핵생물의 경우 XM이 압축률이 약간 더 좋지만, 100MB보다 큰 시퀀스에 대해서는 계산 요구 사항이 비실용적이다.

3. 6. 실행 파일

실행 파일 압축은 프로그램의 크기를 줄여 배포 및 설치 시간을 단축하는 데 사용된다.

4. 무손실 압축의 한계

비둘기집 원리에 따라, 모든 데이터를 압축할 수 있는 무손실 압축 알고리즘은 존재하지 않는다.[17] 압축 알고리즘은 특정 유형의 데이터에 최적화되어 있으며, 모든 종류의 데이터에 대해 높은 압축률을 보장할 수 없다.

다음은 비둘기집 원리를 이용한 증명이다.


  • 각 파일은 임의의 길이의 비트 문자열로 표현된다고 가정한다.
  • 모든 파일을 원래 파일보다 더 길지 않은 출력 파일로 변환하고, 최소한 하나의 파일을 원래 파일보다 짧은 출력 파일로 압축하는 압축 알고리즘이 있다고 가정한다.
  • 압축 길이가 더 짧은 파일 ''F''가 있는 최소 숫자 ''M''을 ''M''으로 한다. ''N''을 ''F''의 압축 버전의 길이(비트 단위)로 한다.
  • ''N''<''M''이므로, 길이 ''N''인 '''모든''' 파일은 압축 중에 크기를 유지한다. 가능한 파일은 2''N''개가 있다. ''F''와 함께, 이것은 모두 길이 ''N''의 2''N''개 파일 중 하나로 압축되는 2''N''+1개의 파일을 만든다.
  • 그러나 2''N''은 2''N''+1보다 작으므로 비둘기집 원리에 따라 압축 함수의 출력이 두 개의 서로 다른 입력인 길이 ''N''인 파일이 있어야 한다. 그 파일은 안정적으로 압축 해제할 수 없으며(두 원본 중 어느 것을 생성해야 하는가?), 이는 알고리즘이 무손실이라는 가정과 모순된다.


대부분의 실용적인 압축 알고리즘은 인코딩 시 더 커질 파일에 대해 일반적인 코딩을 끌 수 있는 "탈출" 기능을 제공한다.[18] 이론적으로는 전체 입력을 위해 일반 코딩이 꺼졌음을 디코더에 알리기 위해 단일 추가 비트만 필요하다. 그러나 대부분의 인코딩 알고리즘은 이 목적을 위해 최소한 1바이트(일반적으로 1바이트 이상)를 사용한다. 예를 들어, deflate 압축 파일은 65,535바이트의 입력당 5바이트 이상으로 커질 필요가 없다.

콜모고로프 복잡성에 따라 무작위 데이터는 압축이 불가능하다. 어떤 데이터라도 무손실로 압축할 수 있는 알고리즘을 만드는 것은 증명 불가능하며, 콜모고로프 복잡성의 의미에서 파일을 압축할 수 없는지 여부를 결정하는 알고리즘이 없다는 것도 증명되었다.[19]

5. 역사적 법적 문제

LZW 압축 특허, 특히 유니시스의 라이선스 관행 때문에, 일부 오픈 소스 지지자들은 정지 이미지 파일을 압축하기 위해 그래픽스 인터체인지 포맷 (GIF) 대신 PNG를 사용할 것을 권장했다.[3] 그러나 LZW 특허는 2003년 6월 20일에 만료되었다.[3]

6. 벤치마크

벤치마크는 비손실 압축 알고리즘 및 구현체의 성능을 경쟁적으로 테스트하는 데 사용된다. 여러 벤치마크가 존재하며, 이들은 데이터 압축률뿐만 아니라 압축 속도, 메모리 사용량 등 다양한 요소를 평가한다.[12]

일부 벤치마크는 압축률만을 고려하여 일상적인 사용에 적합하지 않은 느린 속도의 프로그램이 우승할 수 있다. 또한, 데이터 파일이 공개되어 있어 특정 데이터 세트에 최적화된 프로그램이 유리할 수 있다는 단점도 존재한다. 이러한 벤치마크에서는 컨텍스트 혼합 압축 소프트웨어가 좋은 성적을 거두는 경향이 있다.

맷 마호니는 자신의 책에서 다음과 같은 벤치마크를 언급했다.[12]


  • 캘거리 코퍼스: 1987년에 만들어졌으며, 작은 크기로 인해 현재는 널리 사용되지 않는다.
  • 대규모 텍스트 압축 벤치마크[13]와 후터 상: 잘라낸 위키백과 XML UTF-8 데이터 세트를 사용한다.
  • 일반 압축 벤치마크[14]: 맷 마호니가 관리하며, 무작위 튜링 머신으로 생성된 데이터의 압축을 테스트한다.


사미 룬사스는 최소 속도 요구 사항을 포함한 최대 압축 다중 파일 테스트 순위를 관리했다. 사용자가 속도와 압축률의 중요도를 가중치로 설정할 수 있는 계산기를 제공하여, 속도 요구 사항에 따라 상위 프로그램이 달라졌다. 2010년 1월에는 NanoZip, FreeArc, CCM, flashzip, 7-Zip 순으로 높은 순위를 기록했다.

난이아 프란체스코 안토니오의 몬스터 압축 벤치마크는 40분 시간 제한으로 1GB의 공개 데이터 압축을 테스트했다. 2009년 12월, NanoZip 0.07a가 최고 순위 아카이버, ccmx 1.30c가 최고 순위 단일 파일 압축기로 기록되었다.

압축 순위 웹사이트는 압축률과 시간의 "프론티어"에 대한 차트 요약을 제공한다.[15]

압축 분석 도구[16]는 LZF4, Deflate, ZLIB, GZIP, BZIP2, LZMA의 스트리밍 구현 성능을 벤치마킹하는 Windows 응용 프로그램이다. 사용자는 압축 속도, 압축 해제 속도, 압축률을 비교하고, 압축 수준, 버퍼 크기, 플러싱 작업이 결과에 미치는 영향을 확인할 수 있다.

가역 압축 알고리즘의 벤치마크로는 Calgary corpus영어가 널리 사용된다.[28][29] 압축률, 속도, 메모리 사용량은 트레이드 오프 관계에 있으며, 압축률이 높은 알고리즘은 메모리 사용량이 많은 경향이 있다.[29]

참조

[1] 웹사이트 Unit 4 Lab 4: Data Representation and Compression, Page 6 https://bjc.edc.org/[...] 2022-04-09
[2] 뉴스 Lossless Streaming – the future of high res audio https://audiomediain[...] Audio Media International 2022-03-03
[3] 웹사이트 LZW Patent Information http://www.unisys.co[...] Unisys
[4] 웹사이트 General characteristics and design considerations for temporal subband video coding https://www.itu.int/[...] Video Coding Experts Group 2019-09-13
[5] 논문 Mathematical properties of the JPEG2000 wavelet filters https://pdfs.semanti[...] 2003
[6] 서적 The Essential Guide to Video Processing https://books.google[...] Academic Press 2009
[7] 논문 DCT-based scheme for lossless image compression International Society for Optics and Photonics 1995-04-17
[8] 서적 Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '98 (Cat. No.98CH36181) 1998
[9] 서적 Handbook of Applied Cryptography https://books.google[...] CRC Press 1996-10-16
[10] 논문 HapZipper: sharing HapMap populations just got easier
[11] 서적 Data Compression Conference http://sweet.ua.pt/p[...] 2016
[12] 웹사이트 Data Compression Explained http://nishi.dreamho[...]
[13] 웹사이트 Large Text Compression Benchmark http://mattmahoney.n[...]
[14] 웹사이트 Generic Compression Benchmark http://mattmahoney.n[...]
[15] 웹사이트 Summary http://compressionra[...] 2016-09-01
[16] 웹사이트 Compression Analysis Tool https://www.noemax.c[...] Noemax Technologies
[17] 서적 8th International Conference on Informatics in Schools: Situation, Evolution, and Perspectives Springer 2015-09-28
[18] 웹사이트 Lossless Compression - an overview {{!}} ScienceDirect Topics https://www.scienced[...] 2022-10-30
[19] 서적 An Introduction to Kolmogorov Complexity and its Applications https://archive.org/[...] Springer
[20] 서적 Proof Patterns Springer 2021-08-24
[21] 웹사이트 .ZIP File Format Specification http://www.pkware.co[...] PKWARE, Inc.
[22] 웹사이트 The Million Random Digit Challenge Revisited https://marknelson.u[...] 2006-06-20
[23] 웹사이트 The $5000 Compression Challenge http://www.patrickcr[...] 2009-06-08
[24] 웹사이트 可逆圧縮 2023-09-05
[25] 웹사이트 無歪み圧縮 2023-09-05
[26] 간행물 Surprising Computer Science https://books.google[...] Springer 2015-09-28
[27] 서적 Lossless Compression Handbook (Communications, Networking and Multimedia) Academic Press 2002-12-18
[28] 간행물 アルファベットサイズが未知の情報源に対する効率的なベイズ符号化法の一考察 https://www.ieice.or[...] 2011-08-22
[29] 웹사이트 Data Compression Explained https://nishi.dreamh[...] 2023-09-05


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com