본문으로 이동

비손실 압축

위키백과, 우리 모두의 백과사전.
(무손실 압축에서 넘어옴)

비손실 압축(非損失 壓縮) 또는 무손실 압축(無損失 壓縮)은 압축된 자료로부터 원래의 자료를 정보의 손실 없이 완벽하게 재구성할 수 있는 데이터 압축의 한 부류이다. 비손실 압축은 대부분의 실제 데이터가 통계적 여유도(statistical redundancy)를 보이기 때문에 가능하다.[1] 대조적으로 손실 압축은 원래 자료의 근사치만을 재구성할 수 있지만, 일반적으로 비트레이트가 크게 개선되어 미디어 크기를 줄일 수 있다.

비둘기집 원리의 작용에 의해, 모든 가능한 자료의 크기를 줄일 수 있는 비손실 압축 알고리즘은 존재할 수 없다. 어떤 자료는 적어도 하나의 기호나 비트만큼 길이가 길어지게 된다.

압축 알고리즘은 보통 인간이나 기계가 읽을 수 있는 문서에는 효과적이지만, 여유도가 없는 무작위 자료의 크기는 줄일 수 없다. 입력 자료의 특정 유형을 염두에 두거나, 압축되지 않은 자료에 포함될 가능성이 높은 여유도의 종류에 대한 구체적인 가정을 바탕으로 설계된 다양한 알고리즘이 존재한다.

비손실 데이터 압축은 많은 응용 분야에서 사용된다. 예를 들어, ZIP 파일 형식과 GNU 도구인 Gzip에서 사용된다. 또한 손실 데이터 압축 기술 내의 구성 요소로도 자주 사용된다(예: MP3 인코더 및 기타 손실 오디오 인코더에 의한 비손실 미드/사이드 조인트 스테레오 전처리).[2]

비손실 압축은 원본 데이터와 압축 해제된 데이터가 동일해야 하는 것이 중요하거나 원본 데이터와의 편차가 바람직하지 않은 경우에 사용된다. 일반적인 예로는 실행 프로그램, 텍스트 문서, 소스 코드 등이 있다. PNG나 GIF와 같은 일부 이미지 파일 형식은 비손실 압축만을 사용하는 반면, TIFF나 MNG와 같은 형식은 비손실 또는 손실 방법을 모두 사용할 수 있다. 비손실 오디오 형식은 보관이나 제작 목적으로 가장 자주 사용되는 반면, 더 작은 손실 오디오 파일은 일반적으로 휴대용 플레이어나 저장 공간이 제한된 경우, 또는 오디오의 정확한 복제가 불필요한 경우에 사용된다.

기술

[편집]

대부분의 비손실 압축 프로그램은 두 가지 일을 순차적으로 수행한다. 첫 번째 단계는 입력 자료에 대한 통계 모델을 생성하고, 두 번째 단계는 이 모델을 사용하여 "있을 법한"(즉, 자주 발생하는) 자료가 "있을 법하지 않은" 자료보다 더 짧은 출력 시퀀스를 생성하도록 입력 자료를 비트 시퀀스에 매핑한다.

비트 시퀀스를 생성하는 데 사용되는 주요 인코딩 알고리즘은 허프먼 부호화(deflate 알고리즘에서도 사용됨)와 산술 부호화이다. 산술 부호화는 정보 엔트로피로 주어지는 특정 통계 모델에 대해 가능한 최선에 가까운 압축률을 달성하는 반면, 허프먼 압축은 더 단순하고 빠르지만 기호 확률이 1에 가까운 모델에서는 좋지 않은 결과를 낸다.

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

비손실 압축 방법은 압축하도록 설계된 자료의 유형에 따라 분류될 수 있다. 원칙적으로 모든 범용 비손실 압축 알고리즘(모든 비트 문자열을 수용할 수 있는 범용)은 모든 유형의 자료에 사용될 수 있지만, 많은 알고리즘은 설계된 형태가 아닌 자료에 대해서는 유의미한 압축을 달성하지 못한다. 텍스트에 사용되는 많은 비손실 압축 기술은 인덱스 컬러 이미지에서도 상당히 잘 작동한다.

멀티미디어

[편집]

이러한 기술은 유사한 톤이 인접한 2차원 영역에 나타나는 일반적인 현상과 같은 이미지의 특정 특성을 활용한다. 첫 번째 화소를 제외한 모든 화소는 왼쪽 인웃 화소와의 차이값으로 대체된다. 이는 큰 값보다 작은 값이 훨씬 더 높은 확률을 갖게 만든다. 이는 사운드 파일에도 자주 적용되며, 주로 저주파와 낮은 볼륨을 포함하는 파일을 압축할 수 있다. 이미지의 경우 이 단계는 위쪽 화소와의 차이를 취함으로써 반복될 수 있으며, 비디오에서는 다음 프레임의 화소와의 차이를 취할 수 있다.

적응형 인코딩은 사운드 인코딩에서는 이전 샘플의 확률을, 이미지 인코딩에서는 왼쪽 및 위쪽 화소의 확률을, 비디오 인코딩에서는 추가적으로 이전 프레임의 확률을 사용한다. 웨이블릿 변환에서는 확률이 계층 구조를 통해서도 전달된다.[3]

역사적 법적 문제

[편집]

이러한 방법 중 다수는 오픈 소스 및 독점 도구, 특히 LZW 및 그 변형으로 구현되어 있다. 일부 알고리즘은 미국 및 기타 국가에서 특허를 받았으며 이를 합법적으로 사용하려면 특허 보유자의 라이선스가 필요하다. 특정 종류의 LZW 압축에 대한 특허, 특히 많은 개발자가 남용이라고 간주한 특허 보유자 유니시스(Unisys)의 라이선스 관행 때문에, 일부 오픈 소스 지지자들은 정지 이미지 파일 압축을 위해 GIF를 사용하는 대신 LZ77 기반의 deflate 알고리즘과 도메인별 예측 필터들을 결합한 PNG를 사용할 것을 권장했다. 그러나 LZW에 대한 특허는 2003년 6월 20일에 만료되었다.[4]

텍스트에 사용되는 많은 비손실 압축 기술은 인덱스 이미지에서도 상당히 잘 작동하지만, 전형적인 텍스트에는 작동하지 않지만 일부 이미지(특히 단순 비트맵)에 유용한 다른 기술들도 있으며, 이미지의 특정 특성(유사한 톤의 인접한 2차원 영역 현상, 색 공간에서 표현 가능한 색상 중 제한된 범위의 색상이 압도적으로 많다는 사실 등)을 활용하는 다른 기술들도 있다.

앞서 언급했듯이 무손실 음원 압축은 다소 전문적인 분야이다. 무손실 음원 압축 알고리즘은 데이터의 파동과 같은 특성에서 나타나는 반복적인 패턴을 활용할 수 있다. 즉, 자기회귀 모델을 사용하여 "다음" 값을 예측하고 예상 값과 실제 데이터 간의 (작을 수 있는) 차이를 인코딩하는 방식이다. 예측된 데이터와 실제 데이터 사이의 차이(오차라고 함)가 작아지는 경향이 있으면, 특정 차이값(샘플 값에서 0, +1, -1 등)이 매우 빈번해지며, 이를 적은 출력 비트로 인코딩하여 활용할 수 있다.

파일의 두 버전 사이의 차이점만 압축하는 것이 유익한 경우가 가끔 있다(또는 영상 압축에서 시퀀스 내의 연속된 이미지들 사이). 이를 델타 부호화(수학에서 차이를 나타내는 그리스 문자 Δ)라고 하지만, 이 용어는 일반적으로 두 버전이 압축 및 압축 해제 외부에서도 의미가 있는 경우에만 사용된다. 예를 들어, 위에서 언급한 비손실 오디오 압축 방식에서 오차를 압축하는 과정은 근사된 음파에서 원래 음파로의 델타 부호화로 설명될 수 있지만, 근사된 버전의 음파는 다른 문맥에서는 의미가 없다.

방법

[편집]

모든 가능한 자료를 효율적으로 압축할 수 있는 비손실 압축 알고리즘은 없다 (이에 대한 자세한 내용은 § 한계 참조). 이러한 이유로, 특정 유형의 입력 자료를 염두에 두거나 압축되지 않은 자료에 포함될 가능성이 있는 여유도의 종류에 대한 구체적인 가정을 바탕으로 설계된 많은 다양한 알고리즘이 존재한다.

가장 일반적인 비손실 압축 알고리즘 중 일부는 다음과 같다.

범용

[편집]
  • ANS – 엔트로피 부호화, LZFSE 및 Zstd에서 사용됨
  • 산술 부호화 – 엔트로피 부호화
  • 버로우즈-휠러 변환 – 텍스트 자료를 더 압축하기 쉽게 만드는 가역 변환, Bzip2에서 사용됨
  • 허프먼 부호화 – 엔트로피 부호화, 다른 알고리즘과 잘 결합됨
  • 렘펠-지브 압축 (LZ77 및 LZ78) – 많은 다른 알고리즘의 기초가 되는 사전 기반 알고리즘
    • DEFLATE – LZ77과 허프먼 부호화를 결합, ZIP, Gzip, Zlib 및 PNG 이미지에서 사용됨
    • 브로틀리 – 높은 슬라이딩 윈도우 크기(최대 16 MiB), 허프먼 부호화 및 컨텍스트 모델링과 함께 LZ77을 사용함
    • LZ4 – 매우 빠른 압축 및 압축 해제
    • LZMA (Lempel–Ziv–Markov chain algorithm) – 매우 높은 압축률, 7-Zip 및 XZ Utils에서 사용됨
    • LZSS (Lempel–Ziv–Storer–Szymanski) – WinRAR에서 허프먼 부호화와 함께 사용됨
    • LZW (Lempel–Ziv–Welch) – GIF 이미지 및 유닉스의 compress 유틸리티에서 사용됨
  • Prediction by partial matching (PPM) – 플레인 텍스트 압축에 최적화됨
  • 런 렝스 부호화 (RLE) – 동일한 값의 연속이 많은 자료에 좋은 압축을 제공하는 단순한 방식

오디오

[편집]

래스터 그래픽

[편집]

3D 그래픽

[편집]
  • OpenCTM – 3D 삼각형 메시의 비손실 압축

비디오

[편집]

비손실 비디오 코덱 목록 참조

암호학

[편집]

암호 해독 시스템은 종종 보안 강화를 위해 암호화 전에 데이터("평문")를 압축한다. 적절하게 구현될 경우, 압축은 암호 해독을 용이하게 할 수 있는 패턴을 제거함으로써 고유성 거리(unicity distance)를 크게 증가시킨다.[9] 그러나 많은 일반적인 비손실 압축 알고리즘은 헤더, 래퍼, 테이블 또는 암호 해독을 오히려 쉽게 만들 수 있는 다른 예측 가능한 출력을 생성한다. 따라서 암호 시스템은 이러한 예측 가능한 패턴을 포함하지 않는 압축 알고리즘을 활용해야 한다.

유전학 및 유전체학

[편집]

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

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

실행 파일

[편집]

자가 해제 실행 파일에는 압축된 애플리케이션과 압축 해제기가 포함되어 있다. 실행 시 압축 해제기는 투명하게 압축을 풀고 원래 애플리케이션을 실행한다. 이는 특히 1킬로바이트 정도로 엄격한 크기 제한이 있는 데모 경연 대회가 열리는 데모 코딩에서 자주 사용된다. 이러한 유형의 압축은 이진 실행 파일에만 엄격하게 제한되지 않고 자바스크립트와 같은 스크립트에도 적용될 수 있다.

벤치마크

[편집]

비손실 압축 알고리즘과 그 구현체들은 정기적으로 일대일 벤치마크 테스트를 받는다. 잘 알려진 여러 압축 벤치마크가 있다. 일부 벤치마크는 데이터 압축비만을 다루므로, 이러한 벤치마크의 우승자는 최고 성능 수치의 느린 속도로 인해 일상적인 사용에는 부적합할 수 있다. 일부 벤치마크의 또 다른 단점은 데이터 파일이 알려져 있다는 것인데, 그래서 일부 프로그램 작성자는 특정 데이터 세트에서 최고의 성능을 내도록 프로그램을 최적화할 수도 있다. 이러한 벤치마크의 승자는 종종 컨텍스트 믹싱 압축 소프트웨어 클래스에서 나온다.

매트 마호니는 그의 2010년 2월 무료 소책자 Data Compression Explained에서 추가로 다음을 나열한다.[12]

  • 1987년으로 거슬러 올라가는 Calgary Corpus는 작은 크기 때문에 더 이상 널리 사용되지 않는다. 매트 마호니는 1996년 5월 21일부터 2016년 5월 21일까지 레오니드 A. 브루키스(Leonid A. Broukhis)가 만들고 유지 관리한 Calgary Compression Challenge를 유지했다.
  • Large Text Compression Benchmark와 유사한 Hutter Prize는 모두 다듬어진 위키백과 XML UTF-8 데이터 세트를 사용한다.
  • 매트 마호니가 유지 관리하는 Generic Compression Benchmark는 무작위 튜링 기계에 의해 생성된 데이터의 압축을 테스트한다.
  • 사미 룬사스(Sami Runsas, NanoZip의 저자)는 Maximum Compression 다중 파일 테스트와 유사하지만 최소 속도 요구 사항이 있는 Compression Ratings를 유지했다. 이는 사용자가 속도와 압축률의 중요성에 가중치를 둘 수 있는 계산기를 제공했다. 속도 요구 사항 때문에 상위 프로그램들은 상당히 달랐다. 2010년 1월 기준 상위 프로그램은 NanoZip이었고 FreeArc, CCM, flashzip, 7-Zip이 그 뒤를 이었다.
  • Nania Francesco Antonio의 Monster of Compression 벤치마크는 40분의 시간 제한 내에 1Gb의 공개 데이터에 대한 압축을 테스트했다. 2009년 12월 기준 상위 순위 아카이버는 NanoZip 0.07a였고 상위 순위 단일 파일 압축기는 ccmx 1.30c였다.

Compression Ratings 웹사이트는 압축률과 시간의 "프런티어" 요약 차트를 게시했다.[13]

Silesia 코퍼스

[편집]

Silesia 코퍼스는 2003년에 Canterbury corpus 및 Calgary corpus가 현대적인 파일들을 얼마나 잘 대표하는지에 대한 우려를 바탕으로 그 대안으로 만들어진 컴퓨터 파일 모음이다. 여기에는 대규모 텍스트 문서, 실행 파일, 데이터베이스 등 다양한 데이터 유형이 포함되어 있다.[14] 이는 데이터 압축 연구에서 널리 사용된다.[15]

코퍼스는 총 211MB 크기의 12개 파일로 구성되어 있다. 파일들은 저자가 시간이 지남에 따라 크기가 빠르게 증가할 가능성이 높다고 생각한 데이터 유형(컴퓨터 프로그램 및 데이터베이스 등)과 대형 텍스트 파일과 같은 보다 전통적인 압축 벤치마크를 대표하도록 선택되었다.[14]

파일 개요, 크기, 설명 및 데이터 유형
파일 크기 (B) 설명 데이터 유형
dickens 10192446 찰스 디킨스의 작품들 영어 텍스트
mozilla 51220480 모질라 1.0의 실행 파일들 실행 파일
mr 9970564 MRI 이미지 3D 이미지
nci 33553445 화학 구조 데이터베이스 데이터베이스
office 6152192 OpenOffice.org의 공유 라이브러리 실행 파일
osdb 10085684 오픈 소스 데이터베이스 벤치마크의 샘플 MySQL 데이터베이스 데이터베이스
reymont 6625583 브와디스와프 레이몬트의 소설 농민(Chłopi) 텍스트 폴란드어 PDF
samba 21606400 삼바 2-2.3의 소스 코드 실행 파일
sao 7251944 SAO 항성 목록 이진 데이터베이스
webster 41458703 1913년판 웹스터 무삭제 사전 HTML
xml 5345280 수집된 XML 파일들 XML
x-ray 8474240 의료용 X-Ray 이미지
합계 211938580

더 넓고 현대적인 데이터 유형 선택을 갖추고 있기 때문에, Calgary corpus와 비교할 때 압축 알고리즘의 테스트 데이터 소스로 더 적합한 것으로 간주된다.[16]

한계

[편집]

비손실 데이터 압축 알고리즘은 모든 입력 데이터 세트에 대해 압축을 보장할 수 없다. 다시 말해, 어떤 비손실 데이터 압축 알고리즘에 대해서도 알고리즘에 의해 처리될 때 크기가 줄어들지 않는 입력 데이터 세트가 존재하며, 적어도 하나의 파일을 작게 만드는 모든 비손실 데이터 압축 알고리즘에는 그것이 더 크게 만드는 파일이 적어도 하나 존재할 것이다. 이는 다음과 같이 비둘기집 원리라고 불리는 계수 논증을 사용하는 기초 수학으로 쉽게 증명된다:[17][18]

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

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

사실, 길이 N의 파일들을 고려할 때, 모든 파일이 동일한 확률을 가진다면, 일부 파일의 크기를 줄이는 모든 비손실 압축에 대해 압축된 파일의 기대 길이(길이 N의 모든 가능한 파일에 대한 평균)는 반드시 N보다 커야 한다. 따라서 우리가 압축하려는 자료의 속성에 대해 아무것도 모른다면, 전혀 압축하지 않는 것이 나을 수도 있다. 비손실 압축 알고리즘은 다른 파일보다 특정 유형의 파일을 압축할 가능성이 더 높을 때만 유용하며, 그때 알고리즘은 그러한 유형의 자료를 더 잘 압축하도록 설계될 수 있다.

따라서 이 논증의 주요 교훈은 큰 손실을 감수해야 한다는 것이 아니라, 단순히 항상 이길 수는 없다는 것이다. 알고리즘을 선택한다는 것은 항상 유용하게 짧아질 모든 파일의 하위 집합을 암시적으로 선택하는 것을 의미한다. 이것이 서로 다른 종류의 파일에 대해 서로 다른 압축 알고리즘을 가져야 하는 이론적인 이유이다. 모든 종류의 자료에 좋은 알고리즘은 있을 수 없다.

설계된 자료 유형에 사용되는 비손실 압축 알고리즘이 그러한 파일을 일관되게 더 짧은 형태로 압축할 수 있게 해주는 "속임수"는, 알고리즘이 작용하도록 설계된 파일들이 모두 알고리즘이 제거하도록 설계된 어떤 형태의 모델링하기 쉬운 여유도를 가지고 있으며, 따라서 그 알고리즘이 더 짧게 만들 수 있는 파일의 하위 집합에 속한다는 것이다. 반면 다른 파일들은 압축되지 않거나 심지어 더 커질 것이다. 알고리즘은 일반적으로 특정 유형의 파일에 매우 구체적으로 조정된다. 예를 들어 비손실 오디오 압축 프로그램은 텍스트 파일에서 잘 작동하지 않으며 그 반대도 마찬가지이다.

특히, 무작위 자료 파일은 어떤 생각할 수 있는 비손실 데이터 압축 알고리즘으로도 일관되게 압축될 수 없다. 실제로 이 결과는 콜모고로프 복잡도에서 무작위성 개념을 정의하는 데 사용된다.[19]

모든 자료를 비손실 압축할 수 있는 알고리즘을 만드는 것은 증명 불가능하다. 수년 동안 임의의 N개 무작위 비트를 항상 N − 1 비트로 압축할 수 있는 "완벽한 압축"을 달성했다는 회사들의 주장이 많았지만, 이러한 종류의 주장은 제안된 압축 방식에 대한 더 이상의 세부 사항을 보지도 않고 안전하게 무시할 수 있다. 그러한 알고리즘은 수학의 근본적인 법칙에 위배되는데, 왜냐하면 그것이 존재한다면 모든 파일을 길이 1로 비손실하게 줄이기 위해 반복적으로 적용될 수 있기 때문이다.[18]

반면에, 파일이 콜모고로프 복잡도 측면에서 압축 불가능한지 여부를 결정하는 알고리즘은 없다는 것도 증명되었다.[20] 따라서 어떤 특정 파일이 무작위로 보일지라도, 압축 해제기의 크기를 포함하더라도 상당히 압축될 가능성이 있다. 한 예로 수학 상수인 π의 자릿수가 있는데, 이는 무작위로 보이지만 아주 작은 프로그램으로 생성될 수 있다. 그러나 특정 파일이 압축 불가능한지 여부를 판단할 수는 없지만, 압축 불가능한 문자열에 대한 간단한 정리는 임의의 주어진 길이의 파일 중 99% 이상이 (압축 해제기의 크기를 포함하여) 1바이트 이상 압축될 수 없음을 보여준다.

수학적 배경

[편집]

추상적으로, 압축 알고리즘은 시퀀스(보통 옥텟)에 대한 함수로 볼 수 있다. 결과 시퀀스가 원래 시퀀스(및 압축 해제 맵에 대한 지침)보다 짧으면 압축에 성공한 것이다. 압축 알고리즘이 비손실이 되려면 압축 맵이 "평문"에서 "압축된" 비트 시퀀스로의 단사 함수를 형성해야 한다. 비둘기집 원리는 길이 N의 시퀀스 모음과 길이 N-1의 시퀀스 모음의 하위 집합 사이의 전단사 함수를 금지한다. 따라서 모든 가능한 입력 시퀀스의 크기를 줄이는 비손실 알고리즘을 생성하는 것은 불가능하다.[21]

실제 압축 이론에서의 적용 지점

[편집]

실제 압축 알고리즘 설계자들은 정보 엔트로피가 높은 스트림은 압축될 수 없음을 인정하고, 그에 따라 이러한 조건을 감지하고 처리하는 기능을 포함한다. 감지의 명백한 방법은 원시 압축 알고리즘을 적용하고 출력이 입력보다 작은지 테스트하는 것이다. 때때로 감지는 휴리스틱에 의해 이루어진다. 예를 들어, 압축 애플리케이션은 이름이 ".zip", ".arj" 또는 ".lha"로 끝나는 파일은 더 정교한 감지 없이 압축 불가능한 것으로 간주할 수 있다. 이 상황을 처리하는 일반적인 방법은 입력 또는 입력의 압축 불가능한 부분을 출력에 인용하여 압축 오버헤드를 최소화하는 것이다. 예를 들어, zip 데이터 형식은 아카이브에 그대로 복사된 입력 파일에 대해 'Stored'라는 '압축 방법'을 지정한다.[22]

같이 보기

[편집]

각주

[편집]
  1. ↑ “Unit 4 Lab 4: Data Representation and Compression”. 《BJC.EDC.org》. 6쪽. 2022년 4월 9일에 확인함.
  2. ↑ Price, Andy (2022년 3월 3일). “Lossless Streaming – the future of high res audio”. 《Audio Media International》. 2025년 10월 25일에 확인함.
  3. 1 2 Unser, M.; Blu, T. (2003). 《Mathematical Properties of the JPEG2000 Wavelet Filters》 (PDF). 《IEEE Transactions on Image Processing》 12. 1080–1090쪽. Bibcode:2003ITIP...12.1080U. doi:10.1109/TIP.2003.812329. PMID 18237979.
  4. ↑ “LZW Patent Information”. 《About Unisys》. Unisys. 2009년 6월 2일에 원본 문서에서 보존된 문서.
  5. ↑ Sullivan, Gary (December 8–12, 2003). “General characteristics and design considerations for temporal subband video coding”. 《ITU-T》. 영상 부호화 전문가 그룹. 2019년 9월 13일에 확인함.
  6. ↑ Bovik, Alan C. (2009). 《The Essential Guide to Video Processing》. Academic Press. 355쪽. ISBN 9780080922508.
  7. ↑ Ahmed, Nasir; Mandyam, Giridhar D.; Magotra, Neeraj (1995년 4월 17일). Rodriguez, Arturo A.; Safranek, Robert J.; Delp, Edward J. (편집). 《DCT-based scheme for lossless image compression》. 《Digital Video Compression: Algorithms and Technologies 1995》 2419 (International Society for Optics and Photonics). 474–478쪽. Bibcode:1995SPIE.2419..474M. doi:10.1117/12.206386.
  8. ↑ Komatsu, K.; Sezaki, K. (1998). 〈Reversible discrete cosine transform〉. 《Proceedings of the 1998 IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP '98 (Cat. No.98CH36181)》. 1769–1772쪽. doi:10.1109/ICASSP.1998.681802. ISBN 0-7803-4428-6.
  9. ↑ Menezes, Alfred J.; van Oorschot, Paul C.; Vanstone, Scott A. (1996년 10월 16일). 《Handbook of Applied Cryptography》. CRC Press. ISBN 978-1-4398-2191-6.
  10. ↑ Chanda, P.; Elhaik, E.; Bader, J.S. (2012). 《HapZipper: sharing HapMap populations just got easier》. 《Nucleic Acids Res》 40. e159쪽. doi:10.1093/nar/gks709. PMC 3488212. PMID 22844100.
  11. ↑ Pratas, D.; Pinho, A.J.; Ferreira, P.J.S.G. (2016). 《Efficient compression of genomic sequences》 (PDF). Data Compression Conference. Snowbird, Utah.
  12. ↑ Mahoney, Matt (2010). “Data Compression Explained” (PDF). 3–5쪽.
  13. ↑ “Summary”. 2016년 9월 1일. 2016년 9월 1일에 원본 문서에서 보존된 문서.
  14. 1 2 Deorowicz, Sebastian. 《Universal Lossless Data Compression Algorithms》 (PDF) (학위논문). Silesian University of Technology. 93–95쪽. 2024년 8월 28일에 원본 문서 (PDF)에서 보존된 문서.
  15. ↑ Maulidina, Alysha Puti; Wijaya, Rachel Anastasia; Mazel, Kimberly; Astriani, Maria Seraphina (2024). 《Comparative Study of Data Compression Algorithms: Zstandard, zlib & LZ4》. 《Science, Engineering Management and Information Technology》. Communications in Computer and Information Science 2198. 394–406쪽. doi:10.1007/978-3-031-72284-4_24. ISBN 978-3-031-72283-7.
  16. ↑ Gupta, Apoorv; Bansal, Aman; Khanduja, Vidhi (2017년 2월 22일). 〈Modern lossless compression techniques: Review, comparison and analysis〉. 《2017 Second International Conference on Electrical, Computer and Communication Technologies (ICECCT)》. IEEE. 1–8쪽. doi:10.1109/ICECCT.2017.8117850. ISBN 978-1-5090-3239-6.
  17. ↑ Sayood 2002, 41쪽.
  18. 1 2 Bell, Tim (2015). 〈Surprising Computer Science〉. 《Informatics in Schools. Curricula, Competences, and Competitions》. Lecture Notes in Computer Science 9378. 1–11쪽. doi:10.1007/978-3-319-25396-1_1. ISBN 978-3-319-25395-4. 특히 8–9쪽 참조.
  19. ↑ Sayood 2002, 38쪽.
  20. ↑ Li, Ming; Vitányi, Paul (1993). 《An Introduction to Kolmogorov Complexity and its Applications》. New York: Springer. 102쪽. ISBN 0-387-94053-7. Theorem 2.6 The function is not partial recursive.
  21. ↑ Joshi, Mark (2015). 〈The Pigeonhole Principle〉. 《Proof Patterns》. 19–23쪽. doi:10.1007/978-3-319-16250-8_3. ISBN 978-3-319-16249-2.
  22. ↑ “.ZIP File Format Specification”. PKWARE, Inc. chapter V, section J.
원본 주소 "https://ko.wikipedia.org/w/index.php?title=비손실_압축&oldid=41451416"