감압

Deflate

컴퓨팅에서 데플레이트(DEFLATE로 표기)는 LZ77허프만 코딩의 조합을 사용하는 무손실 데이터 압축 파일 형식이다.PKZ 버전 2를 위해 필 캣츠가 설계했다.IP 보관 도구.감압은 나중에 RFC 1951(1996)에 지정되었다.[1]

Katz는 또한 Deflate 스트림을 구성하는 데 사용되는 원래의 알고리즘을 설계했다.이 알고리즘은 미국 특허 5,051,745특허를 받았으며 PKWARE, Inc.에 할당되었다.[2][3]RFC 문서에 언급된 바와 같이, Deflate 파일을 생성하는 알고리즘은 특허에 의해 다루어지지 않는 방식으로 구현될 수 있다고 널리 생각되었다.[1]이로 인해 Gzip 압축 파일과 PNG 이미지 파일뿐만 아니라 Katz가 원래 설계한 ZIP 파일 형식도 널리 사용하게 되었다.그 특허는 그 후 만료되었다.

스트림 형식

감압 하천은 일련의 블록으로 이루어져 있다.각 블록에는 3비트 헤더가 선행된다.

  • 첫 번째 비트: 스트림 내 마지막 블록 마커:
    • 1: 여기가 개울의 마지막 블록이다.
    • 0: 이 블록 이후에 처리할 블록이 더 많다.
  • 두 번째 및 세 번째 비트:이 블록 유형에 사용되는 인코딩 방법:
    • 00: 0에서 65,535바이트 사이의 저장된 섹션(원시 또는 리터럴)
    • 01: RFC에 정의된 사전 승인된 허프먼 트리를 사용하는 정적 허프먼 압축 블록
    • 10: Huffman 테이블이 제공된 압축 블록
    • 11: 예약됨—사용하지 않음.

저장된 블록 옵션은 오버헤드를 최소화하고 압축할 수 없는 데이터에 사용된다.

대부분의 압축 가능한 데이터는 결국 방법을 사용하여 인코딩될 것이다.10각 데이터 블록에 대해 개별적으로 사용자 정의된 최적화된 허프만 트리를 생성하는 동적 허프만 인코딩.필요한 Huffman 트리를 생성하기 위한 지시사항은 블록 헤더를 즉시 따른다.정적 Huffman 옵션은 트리를 생략함으로써 얻는 고정된 절약이 비최적(기술적으로 Huffman이 아닌) 코드 사용으로 인한 압축 손실 백분율을 초과하는 짧은 메시지에 사용된다.

압축은 다음 두 단계를 통해 달성된다.

  • 포인터가 있는 중복 문자열의 일치 및 교체.
  • 사용 빈도에 따라 가중치가 부여된 새로운 기호로 기호 교체.

비트감소

두 번째 압축 단계는 일반적으로 사용되는 기호를 더 짧은 표현으로 대체하고 덜 자주 사용되지 않는 기호는 더 긴 표현으로 대체하는 것으로 구성된다.사용된 방법은 Huffman 코딩으로, 각 시퀀스의 길이는 인코딩이 필요한 기호의 확률의 로그에 반비례하는, 겹치지 않는 간격의 고정되지 않은 트리를 만든다.기호를 암호화해야 할 가능성이 높을수록 그 비트 시퀀스는 짧아진다.

288개의 기호를 사용할 수 있는 공간이 포함된 트리가 생성됨:

  • 0–123: 리터럴 바이트/리터럴 0–123을 나타낸다.
  • 256: 블록 끝 – 마지막 블록인 경우 처리를 중지하고, 그렇지 않은 경우 다음 블록 처리를 시작하십시오.
  • 257–285: 3–258바이트의 일치 길이인 추가 비트와 결합.
  • 286, 287: 사용되지 않고, 유보적이고 불법적이지만 여전히 나무의 일부분이다.

일치 길이 코드는 항상 거리 코드를 따른다.판독된 거리 코드에 기초하여 최종 거리를 생성하기 위해 추가 "추가" 비트를 판독할 수 있다.거리 트리에는 32개의 기호를 사용할 수 있는 공간이 포함되어 있다.

  • 0–3: 거리 1–4
  • 4–5: 거리 5–8, 1 비트
  • 6-7: 거리 9-16, 추가 비트 2개
  • 8–9: 거리 17–32, 추가 비트 3개
  • ...
  • 26–27: 거리 8,198–16,384, 12개의 추가 비트
  • 28–29: 거리 16,385–32,768, 13개의 추가 비트
  • 30–31: 사용되지 않고, 유보적이며, 불법이지만 여전히 나무의 일부분이다.

매치 거리 기호 2-29의 경우, 여분의 비트 수는 2 - }{2}}\로 계산할 수 있다.

두 개의 코드(기호 288-심볼 길이/문자수 및 32-심볼 거리수)는 각 기호에 대한 코드 비트 길이를 부여하여 표준 허프만 코드로 자체 암호화된다.비트 길이는 그 자체로 런 길이 인코딩되어 가능한 컴팩트한 표현을 만들어 낸다.트리 표현을 포함하는 대안으로, "정적 트리" 옵션은 표준 고정 허프먼 트리를 제공한다.정적 트리를 사용한 압축 크기는 동적 트리를 생성하는 데 사용되는 것과 동일한 통계량(각 기호가 나타나는 횟수)을 사용하여 계산할 수 있으므로 압축기가 더 작은 것 중 하나를 쉽게 선택할 수 있다.

중복 문자열 제거

압축된 블록 내에서 중복된 바이트 시리즈(반복된 문자열)가 발견되면 백 레퍼런스가 삽입되어 동일한 문자열의 이전 위치에 대신 연결된다.이전 문자열과의 인코딩된 일치는 8비트 길이(3–258바이트)와 15비트 거리(1–32,768바이트)로 구성된다.거리가 압축되지 않은 데이터의 마지막 32KiB(슬라이딩 윈도우라고 함) 내에서 나타나는 한(상대적인 역 참조는 임의의 수의 블록에 걸쳐 이루어질 수 있다.

거리가 길이보다 짧으면 중복 자체가 겹쳐 반복을 나타낸다.예를 들어, 10개의 동일한 바이트의 실행은 1바이트로 인코딩될 수 있으며, 그 다음에 이전 바이트로 시작하는 길이 9의 중복이 뒤따른다.

앞의 텍스트에서 중복 서브스트링을 검색하는 것은 DEFLAT 알고리즘에서 계산적으로 가장 비용이 많이 드는 부분이며 압축 수준 설정이 영향을 미치는 연산이다.

인코더/컴프레서

압축 단계에서는 일치하는 문자열을 찾는 데 소요되는 시간을 선택하는 것이 인코더다.zlib/gzip 참조 구현을 통해 사용자는 압축 수준 대 인코딩 속도의 슬라이딩 스케일 중에서 선택할 수 있다.옵션 범위0(압축 시도하지 않고 압축되지 않은 상태로 저장)9zlib/gzip으로 참조 구현의 최대 기능을 나타낸다.

다른 디플레이트 인코더가 생산되었는데, 이 인코더는 모두 기존의 디플레이트 디코더에 의해 압축 해제될 수 있는 호환 가능한 비트스트림을 생산할 것이다.서로 다른 구현은 최종 암호화된 비트 스트림에 변화를 일으킬 가능성이 높다.일반적으로 인코더의 압축 버전이 아닌 버전의 인코더는 더 효율적으로 압축되고 더 작은 인코딩 스트림을 생성하는 데 초점을 맞추었다.

감압64/향상 감압

PKWARE가 지정한 Deflate64는 Deflate의 독점 변종이다.근본적으로 같은 알고리즘이다.바뀐 것은 사전 크기가 32KB에서 64KB로 증가하고 거리 코드가 16비트로 확장되어 64KB의 범위를 다룰 수 있으며 길이 코드가 16비트로 확장되어 3에서 65,538바이트의 길이를 정의할 수 있다.[4]이것은 Delflate64가 Delflate보다 압축 시간이 더 길고 잠재적으로 약간 더 높은 압축 비율을 갖게 한다.[5]7-Zip과 같은 여러 무료 및/또는 오픈 소스 프로젝트에서는 Deflate64를 지원하지만 zlib와 같은 다른 프로젝트에서는 절차의[7] 독점적 특성과 Deflate에 비해 매우 낮은 성능의 결과로 Defflate64를 지원하지 않는다.[6][8]

새 소프트웨어에서 감압 사용

디플레이트 구현은 많은 언어로 자유롭게 이용할 수 있다.C로 작성된 앱은 일반적으로 zlib 라이브러리(허용 zlib License 이하)를 사용한다.볼랜드 파스칼과 (호환 언어)의 앱은 파스즈립을 사용할 수 있다.C++의 앱은 7-Zip의 향상된 Deflate 라이브러리를 이용할 수 있다.Java .NET Framework는 라이브러리에서 Deflate에 대한 즉각적인 지원을 제공한다(존중,java.util.zip그리고 시스템.IO.압축).에이다의 앱은 Zip-Aada(순수)나 ZLib-Aada를 사용할 수 있다.

인코더 구현

  • PKZIP: 첫 번째 구현, 원래 PKZIP의 일부로 Phil Katz에 의해 수행됨
  • zlib: 오픈 소스, 허용 라이센스 때문에 많은 앱에서 채택된 표준 참조 구현
  • zlib-ng: 최신 CPU 본질을 사용하여 zlib의 포크가 빨라짐.
  • Crypto++: 잠재적인 보안 취약점을 줄이기 위한 C++의 공용 도메인 구현이 포함되어 있다.저자 웨이 다이(Wei Dai)는 "라고 말한다.This code is less clever, but hopefully more understandable and maintainable [than zlib]
  • 7-Zip: 이고르 파블로프가 C++로 작성한 이 버전은 자유롭게 라이센스가 부여되며 CPU 사용량을 희생하여 zlib보다 높은 압축을 달성한다.DEFLAT64 저장소 형식을 사용할 수 있는 옵션 있음
  • PuTTY 'sshzlib.c': Simon Tatham에 의한 MIT 라이선스에 의한 독립 실행형 구현, 완전한 디코딩 기능을 가지고 있지만 정적 트리만 생성 지원
  • libflate:[9] Bell Labs의 Plan 9 운영 체제의 일부, 감압 압축 구현
  • Hyperbac: DEFLAT64 스토리지 형식을 구현하는 옵션과 함께 전용 압축 라이브러리(C++ 및 어셈블리) 사용
  • Zopfli: 구글의 Apache License에 따른 C 구현; CPU 사용량을 희생하여 가장 높은 압축을 달성한다.ZopfliPNG는 PNG 파일과 함께 사용하기 위한 Zopfli의 변형이다.
  • igzip: x86 어셈블리 언어로 작성된 인코더로, Intel이 MIT 라이센스 하에 출시했다.zlib -1보다 3배 빠른 속도.유전체 데이터를 압축하는 데 유용하다.[10]

AdvanceCOMP는 7-Zip(또는 선택적으로 최근 버전에서는 Zopfli)에 의해 구현된 Deflate의 높은 압축 비율 버전을 사용하여 zlib보다 작은 파일 크기가 가능한 gzip, PNG, MNGZIP 파일을 최대 설정에서 다시 압축할 수 있다.

하드웨어 인코더

  • 컴텍 AHA의 AHA361-PCIX/AHA362-PCIX.컴텍은 PCI-X 카드(PCI-ID:193f:0001 압축되지 않은 수신 데이터에 대해 최대 3.0Gbit/s(375MB/s)의 속도로 Delflate를 사용하여 스트림을 압축할 수 있는 기능.AHA361-PCIX를 위해 Linux 커넬드리버를 동반하는 것은 "ahagzip"유틸리티 및 맞춤형 "mod_deflate_aha " Apache에서 하드웨어 압축 기능을 사용할 수 있음.하드웨어는 XilinxVirtexFPGA와 4개의 사용자 정의 AHA3601 ASIC를 기반으로 한다.AHA361/AHA362 보드는 정적 허프먼 블록만을 취급하는 것으로 제한되며, 지원을 추가하기 위해 소프트웨어를 수정하도록 요구한다. 즉, 카드는 완전한 디플레이트 사양을 지원할 수 없었으며, 이는 카드의 자체 출력(동적 허프먼 타입 2 블록을 포함하지 않은 스트림)만 신뢰성 있게 디코딩할 수 있었음을 의미한다.
  • StorCompress 300/MX3 Indra Networks에서 압축.PCI(PCI-ID:17b4:0011) 또는 PCI-X 카드에는 최대 3.6Gbit/s(450MB/s)의 처리 속도로 1~6대의 압축 엔진이 탑재되어 있다.카드 버전은 SAN이나 백업 용도가 아닌 웹 서비스용으로 특별히 설계된 별도의 브랜드 WebEnhance와 함께 사용할 수 있으며 PCIe 개정판 MX4E도 제작된다.
  • AHA363-PCIe/AHA364-PCIe/AHA367-PCIe.2008년 컴텍은 PCIe 카드 2장을 생산하기 시작했다.PCI-ID: 193f:0363/193f:0364새 하드웨어 AHA3610 인코더 칩 포함.이 새로운 칩은 2.5 Gbit/s를 지속할 수 있도록 설계되었다.AHA363-PCIe 보드는 이들 칩 중 2개를 사용하여 최대 5.0Gbit/s(625MB/s)의 속도로 Deblate를 처리할 수 있다(압축 2개와 감압 2개).AHA364-PCIe 변형은 외부 로드 밸런싱 장치용으로 설계된 카드의 인코드 전용 버전이며, 대신 두 개의 물리적 압축 엔진에 32개의 독립적 가상 압축 채널이 공급될 수 있도록 여러 개의 레지스터 세트를 가지고 있다.Linux, Microsoft WindowsOpenSolaris 커널 장치 드라이버는 동적으로 연결된 애플리케이션이 내부 수정 없이 자동으로 하드웨어 지원을 사용할 수 있도록 수정된 zlib 시스템 라이브러리와 함께 새로운 카드 모두에 사용할 수 있다.AHA367-PCIe 보드 (PCI-ID: 193f:0367)은 AHA363-PCIe와 유사하지만 10Gbit/s(1250MB/s)의 지속적 압축률을 위해 4개의 AHA3610 칩을 사용한다.AHA362-PCIX와 달리, AHA363-PCIe 보드와 AHA367-PCIe 보드의 감압 엔진은 완전히 감압 규정을 준수한다.
  • Cavium, Inc.의 NitroxOcteon[permanent dead link] 프로세서는 ZLIB 및 GZIP와 호환되는 고속 하드웨어 감압 및 팽창 엔진을 내장하고 있으며, 일부 장치는 다중 동시 데이터 스트림을 처리할 수 있다.
  • HDL-감압 GPL FPGA 구현.
  • CAST사ZipAccel-C.Deflate, Zlib, Gzip 압축을 지원하는 실리콘 IP 코어 입니다.ZipAccel-C는 ASIC 또는 FPGA에서 구현 가능하며, 동적 및 정적 허프만 테이블을 모두 지원하며, 100Gbps를 초과하는 처리량을 제공할 수 있다.이 회사는 인텔 FPGA(ZipAccel-RD-INT)와 시린x FPGA(ZipAccel-RD-XIL)에 압축/압축 가속기 보드 참조 디자인을 제공한다.
  • Intel Xeon E5-2600 및 E5-2400 프로세서 시리즈(Sandy Bridge-EP/EN)용 Intel Communications Chipset 89xx Series(케이브 크릭)는 QuickAssist Technology를 사용하여 하드웨어 압축 및 압축 해제를 지원한다.칩셋에 따라 5Gbit/s, 10Gbit/s 또는 20Gbit/s의 압축 및 압축 해제 속도를 사용할 수 있다.[11]
  • IBM z15 CPU는 RFC1951에서 지정한 하드웨어 감압 및 감압에 대한 z14 시스템에 사용되는 zEDC Express I/O 확장 카드에서 향상된 버전의 NXU(Nest Accelerator Unit) 하드웨어 가속을 통합한다.[12][13]
  • POWER9 아키텍처를 시작으로 IBM은 POWER7+로 도입된 이전의 암호중심 네스트 액셀러레이터(NX) 코어에 데플레이트(RFC 1951에서 지정한 대로) 압축 및 압축 해제를 위한 하드웨어 지원을 추가했다.이 지원은 zlibNX 라이브러리를 통해 AIX 7.2 Technology Level 4 Expansion Pack 또는 AIX 7.2 Technology Level 5 Service Pack 2로 실행되는 프로그램에 대해 이용할 수 있다.[14][15]

디코더/디컴프레서

가압은 감압에 대해 감압 비트스트림을 사용하고 원래의 전체 크기 데이터나 파일을 올바르게 생성하는 디코딩 프로세스다.

가압 전용 구현

대체적인 팽창 구현을 통한 정상적인 의도는 고도로 최적화된 디코딩 속도, 또는 마이크로컨트롤러 임베디드 시스템의 극도로 예측 가능한 RAM 사용이다.

  • 조립
    • 6502 팽창, 피오트르 푸식(Piotr Fusik)이 6502 어셈블리 언어로 썼다.
    • SAMFLATESAM Coupé에 대한 선택적 메모리 페이징 지원으로 Z80 어셈블리 언어로 작성되었으며 BSD/GPL/LGPL/DFSG 라이센스에 따라 사용할 수 있게 되었다.
    • Laurns Holst가 MSX를 위해 Z80 어셈블리 언어로 작성한 gunzip.
    • keir Fraser에 의해 작성되어 Public Domain에 배포된 M68000 기계 언어로 빠르고 효율적인 구현인 guarm.asm.
  • C/C++
    • "KZIP"와는 무관한 마이클 콘의 쿤집.GNU LGPL 라이센스 하에 C 소스 코드가 함께 제공됨.KIMP 설치 관리자에서 사용.
    • puff.c(zlib)는 zlib 배포의 /snmp/snmp 디렉터리에 포함된 소규모, 번호 없는 단일 파일 참조 구현.
    • Yörgen Ibsen이 ANSI C에서 작성한 tinf는 zlib 라이선스와 함께 제공된다.약 2k 코드를 추가한다.
    • tinfl.c (miniz), Public domain Glump 구현은 전적으로 단일 C 함수에 포함되어 있다.
  • PCDEZIP, 밥 플랜더스와 마이클 홈즈, PC 매거진 1994-01-11에 게재.
  • inflate.cl by John Forderaro.GNU LGPL 라이선스와 함께 배포되는 독립형 공통 리스포더.
  • Thomas Mertes가 Deflate와 gzip 압축을 순수 Seed7로 구현한 gplan.s7i/gzip.s7i.GNU LGPL 라이센스에 따라 사용 가능.
  • Pyflate, Paul Sladen의 순수 피톤 독립형 데플레이트(gzip) 및 bzip2 디코더.연구/프로토타이핑을 위해 작성되었으며 BSD/GPL/LGPL/DFSG 라이센스에 따라 사용 가능.
  • David Manura에 의해 Deflate와 gzip/zlib 감압의 순수 Lua 구현.
  • Chris Dickinson에 의한 Flump의 순수 자바스크립트 구현을 부풀리다.
  • Pako: JavaScript 속도에 최적화된 zlib 포트.가압만 있는 별도의 빌드 포함.

하드웨어 디코더

  • BitSim에서 직렬 가압 GPU.가압의 하드웨어 구현.임베디드 시스템을 위한 BitSim의 BAD(Bitsim Accelerated Display Graphics Engine) 컨트롤러의 일부.
  • HDL-감압 GPL FPGA 구현.
  • CAST사ZipAccel-D.Deflate, Zlib, Gzip 파일의 압축을 지원하는 실리콘 IP 코어 입니다.ASIC 또는 FPGA에서 구현할 수 있는 ZipAccel-D IP 코어.이 회사는 인텔 FPGA(ZipAccel-RD-INT)와 시린x FPGA(ZipAccel-RD-XIL)에 압축/압축 가속기 보드 참조 디자인을 제공한다.
  • IBM z15 CPU는 RFC1951에서 지정한 하드웨어 감압 및 감압에 대한 z14 시스템에 사용되는 zEDC Express I/O 확장 카드에서 향상된 버전의 NXU(Nest Accelerator Unit) 하드웨어 가속을 통합한다.[12][13]
  • POWER9 아키텍처를 시작으로 IBM은 POWER7+로 도입된 이전의 암호중심 네스트 액셀러레이터(NX) 코어에 데플레이트(RFC 1951에서 지정한 대로) 압축 및 압축 해제를 위한 하드웨어 지원을 추가했다.이 지원은 zlibNX 라이브러리를 통해 AIX 7.2 Technology Level 4 Expansion Pack 또는 AIX 7.2 Technology Level 5 Service Pack 2로 실행되는 프로그램에 대해 이용할 수 있다.[14][15]

참고 항목

참조

  1. ^ a b Deutsch, L. Peter (May 1996). DEFLATE Compressed Data Format Specification version 1.3. IETF. p. 1. sec. Abstract. doi:10.17487/RFC1951. RFC 1951. Retrieved 2014-04-23.
  2. ^ 1991-09-24, 발행된 미국 특허 5051745, Katz, Phillip W, "String Searcher 및 Compressor Using Same"은 PKWare Inc.에 할당되어 1991-09-24를 발행했다.
  3. ^ David, Salomon (2007). Data Compression: The Complete Reference (4 ed.). Springer. p. 241. ISBN 978-1-84628-602-5.
  4. ^ "Binary Essence – Deflate64". Archived from the original on 21 June 2017. Retrieved 22 May 2011.{{cite web}}: CS1 maint : bot : 원본 URL 상태 미상(링크)
  5. ^ "Binary Essence – "Calgary Corpus" compression comparisons". Archived from the original on 27 December 2017. Retrieved 22 May 2011.{{cite web}}: CS1 maint : bot : 원본 URL 상태 미상(링크)
  6. ^ 7-Zip 설명서 및 설명서 – 압축 방법
  7. ^ 무손실 데이터 압축 알고리즘의 역사 - 감압64
  8. ^ zlib FAQ – zlib가 PKWare에서 도입한 새로운 "Deflate64" 형식을 지원하는가?
  9. ^ "Plan 9 from Bell Labs's /n/sources/plan9/sys/src/libflate". plan9.bell-labs.com. Lucent Technologies. Archived from the original on 2006-03-15.
  10. ^ "High Performance DEFLATE Compression with Optimizations for Genomic Data Sets". Intel Software. 1 October 2019. Retrieved 18 January 2020.
  11. ^ "Intel® Xeon® Processor E5-2600 and E5-2400 Series with Intel® Communications Chipset 89xx Series". Retrieved 2016-05-18.
  12. ^ a b "Introducing the IBM z15 - The enterprise platform for mission-critical hybrid multicloud". Retrieved 2021-11-01.
  13. ^ a b Lascu, Octavian (28 April 2021). IBM z15 (8562) Technical Guide, Page 97. ISBN 9780738458991. Retrieved 2021-11-01.
  14. ^ a b "Data compression by using the zlibNX library - IBM Documentation". Retrieved 2021-11-01.
  15. ^ a b "Exploitation of In-Core Acceleration of POWER Processors for AIX". Retrieved 2021-11-01.

외부 링크