LZMA

3. 기술적 특징

LZMA는 슬라이딩 윈도우 방식의 LZ77 알고리즘을 개선하여 사용하며, 범위 코더를 통해 압축된 데이터를 표현한다.

LZMA는 큰 사전 크기와 반복적으로 사용되는 일치 거리에 대한 특별한 지원을 갖춘 LZ77의 변형이다. 그 결과는 복잡한 모델을 사용하여 각 비트의 확률 예측을 하는 범위 인코더로 인코딩된다. 사전 압축기는 정교한 사전 데이터 구조를 사용하여 일치를 찾고, 리터럴 기호와 구문 참조의 스트림을 생성하며, 이는 범위 인코더에 의해 한 번에 한 비트씩 인코딩된다. 많은 인코딩이 가능하며, 특정 근사치 하에서 최적의 인코딩을 선택하기 위해 동적 프로그래밍 알고리즘이 사용된다.^[8]

LZMA 이전에는 대부분의 인코더 모델이 순수하게 바이트 기반이었다. LZMA의 주요 혁신은 일반적인 바이트 기반 모델 대신 리터럴 또는 구문의 각 표현에서 비트 필드에 특정한 컨텍스트를 사용한다는 것이다. 이는 일반적인 바이트 기반 모델만큼 간단하지만 동일한 컨텍스트에서 관련 없는 비트를 혼합하는 것을 피하므로 훨씬 더 나은 압축을 제공한다. 또한 고전적인 사전 압축(zip 및 gzip 형식에서 사용되는 압축)과 비교하여 사전 크기가 훨씬 더 클 수 있으며, 현대 시스템에서 사용 가능한 대량의 메모리를 활용한다.^[8]

LZ77과 마찬가지로 딕셔너리에서 복사하는 것은 복사가 바이트 단위로 수행되어 거리가 일정하게 유지되는 것처럼 정의되므로 길이는 거리에 의해 제한되지 않는다. 거리는 논리적으로 32비트이며 거리 0은 딕셔너리에 가장 최근에 추가된 바이트를 가리킨다.

거리 인코딩은 6비트 "거리 슬롯"으로 시작하여 추가로 필요한 비트 수를 결정한다. 다음 표에 따라 거리 슬롯에 따라 두 비트, 고정 0.5 확률로 인코딩된 일부 비트, 일부 컨텍스트 인코딩 비트의 이진 연결로 디코딩된다(거리 슬롯 0-3은 직접 거리 0-3을 인코딩한다).^[8]

3. 1. LZMA 알고리즘

3. 2. LZMA2 형식

• 40은 4GB − 1 사전 크기를 나타낸다.
• 40보다 작은 짝수 값은 2^{''v''/2 + 12} 바이트 사전 크기를 나타낸다.
• 40보다 작은 홀수 값은 3×2^{(''v'' − 1)/2 + 11} 바이트 사전 크기를 나타낸다.
• 40보다 큰 값은 유효하지 않다.

• 0은 파일의 끝을 나타낸다.
• 1은 압축되지 않은 청크가 뒤따르는 사전 재설정을 나타낸다.
• 2는 사전 재설정 없이 압축되지 않은 청크를 나타낸다.
• 3–0x7f는 유효하지 않은 값이다.
• 0x80–0xff는 LZMA 청크를 나타내며, 여기서 최하위 5비트는 압축되지 않은 크기에서 1을 뺀 값의 비트 16–20으로 사용되고, 비트 5–6은 무엇을 재설정해야 하는지 나타낸다.

• 0: 아무것도 재설정되지 않음
• 1: 상태 재설정
• 2: 상태 재설정, 속성 바이트를 사용하여 속성 재설정
• 3: 상태 재설정, 속성 바이트를 사용하여 속성 재설정, 사전 재설정

• 범위 코더
• ''상태'' 값
• 반복 일치에 대한 마지막 거리
• 모든 LZMA 확률

• 데이터 크기에서 1을 뺀 값을 인코딩하는 16비트 빅 엔디안 값
• 사전 및 출력에 그대로 복사될 데이터

• 압축되지 않은 크기에서 1을 뺀 값의 하위 16비트를 인코딩하는 16비트 빅 엔디안 값
• 압축된 크기에서 1을 뺀 값을 인코딩하는 16비트 빅 엔디안 값
• 제어 바이트의 비트 6이 설정된 경우 속성/lclppb 바이트
• 범위 코더를 초기화하는 데 사용되는 5바이트로 시작하는 LZMA 압축 데이터(이 중 첫 번째는 무시됨) (압축된 크기에 포함됨)

3. 3. XZ 및 7z 형식

4. 구현 및 사용 사례

7-Zip에서 추출된 LZMA 구현은 LZMA SDK로 사용할 수 있으며, 원래는 GNU LGPL과 공통 공중 사용 허가서 이중 라이선스로 배포되었으나,^[12] 2008년 12월 2일 버전 4.62 릴리스와 함께 이고르 파블로프에 의해 퍼블릭 도메인으로 공개되었다.^[11]

LZMA의 개선된 버전인 LZMA2 압축은^[13] 2012년 10월 26일 버전 9.30부터 .7z 형식의 기본 압축 방법이 되었다.^[14]

오픈 소스 라이선스 LZMA 압축 라이브러리는 C++로 작성되었지만, ANSI C, C# 및 자바로 이식되었다.^[11] C++ 라이브러리에 대한 제3자 파이썬 바인딩과 더불어 파스칼, Go 및 에이다로 LZMA를 이식한 버전도 있다.^{[15][16][17][18]}

7-Zip 구현은 사전 검색 알고리즘의 기반으로 여러 변형된 해시 체인, 이진 트리 및 패트리샤 트리를 사용한다.

LZMA 외에도 SDK와 7-Zip은 압축 개선을 위해 여러 전처리 필터를 구현하는데, 여기에는 단순한 델타 인코딩 (이미지용) 및 실행 코드를 위한 BCJ 등이 포함된다. 또한 7z에서 사용되는 다른 압축 알고리즘도 제공한다.

LZMA용 압축 해제 전용 코드는 일반적으로 약 5KB로 컴파일되며, 압축 해제 시 필요한 RAM의 양은 주로 압축 중에 사용되는 슬라이딩 윈도우의 크기에 의해 결정된다. 작은 코드 크기, 상대적으로 낮은 메모리 오버헤드(특히 더 작은 사전 길이에서), 그리고 자유로운 소스 코드는 LZMA 압축 해제 알고리즘을 임베디드 시스템 응용 프로그램에 적합하게 만든다.

7-Zip 참조 구현 외에도 다음이 LZMA 형식을 지원한다.

• xz: xz 파일 형식에서 LZMA 및 LZMA2를 모두 지원하는 gzip과 유사한 명령줄 도구를 포함하는 스트리밍 구현이다. 높은 성능(bzip2에 비해)과 작은 크기(gzip에 비해)로 유닉스 계열 세계의 여러 소프트웨어에 도입되었다.^[2] 리눅스 커널, dpkg 및 RPM 시스템에는 xz 코드가 포함되어 있으며, kernel.org, 데비안^[19] 및 페도라와 같은 많은 소프트웨어 배포판에서 이제 릴리스를 압축하는 데 xz를 사용한다.
• lzip: 주로 유닉스 계열 시스템을 위한 또 다른 LZMA 구현으로 xz와 직접 경쟁한다.^[20] 주로 더 간단한 파일 형식을 특징으로 하므로 오류 복구가 더 쉽다.
• ZIPX: WinZip에서 버전 12.1부터 시작하여 생성된 ZIP 압축 형식의 확장이다. 또한 BZip 및 PPMd와 같은 다양한 다른 압축 방법을 사용할 수 있다.^[21]

오픈 소스 레퍼런스 구현인 LZMA 압축 라이브러리는 C++로 작성되었으며, 다음과 같은 특징을 가지고 있다.

• 압축 속도: 2GHz CPU에서 약 1MB/초
• 압축 해제 속도: 2GHz CPU에서 10~20MB/초
• 멀티 스레드 및 펜티엄 4 마이크로프로세서의 하이퍼 스레딩 기능을 지원

• p7zip: 7-Zip의 7z와 7za 커맨드 라인 툴의 이식판이다. p7zip은 표준 7z 아카이브 스트림을 생성한다.
• LZMA Utils: LZMA 코드 ''만''으로 구성된 이식판이다. 현재는 XZ Utils가 메인 스트림이 되어, LZMA Utils의 개발은 종결되었다.
• XZ Embedded: XZ Utils의 압축 해제 코드만 뽑아서 정리한 라이브러리로, 주로 리눅스 커널의 부팅 시에 사용하는 것을 전제로 설계되어 있다.

5. 라이선스

7-Zip에서 추출된 LZMA 구현은 LZMA SDK로 사용할 수 있다. 이고르 파블로프는 2008년 12월 2일 버전 4.62 릴리스와 함께 LZMA SDK를 퍼블릭 도메인으로 공개했다.^[11] 이전에는 GNU LGPL과 공통 공중 사용 허가서 이중 라이선스로 배포되었으며,^[12] 연결된 바이너리에 대한 추가적인 특별 예외 조항이 있었다.

LZMA 압축 해제 전용 코드는 일반적으로 약 5KB로 컴파일되며, 압축 해제 시 필요한 RAM의 양은 주로 압축 중에 사용되는 슬라이딩 윈도우의 크기에 의해 결정된다. 작은 코드 크기, 상대적으로 낮은 메모리 오버헤드, 자유로운 소스 코드는 LZMA 압축 해제 알고리즘을 임베디드 시스템 응용 프로그램에 적합하게 만든다.

LZMA 압축 및 해제를 위한 SDK는 [http://sevenzip.sourceforge.jp/sdk.html] 에서 확인할 수 있으며, 문서, 샘플, 헤더 파일, 소스 코드 등을 포함한다.

6. 관련 소프트웨어

• GNU Tar는 버전 1.20 이후부터 "--lzma" 옵션을 통해 LZMA 압축을 지원한다.^[1]
• Nullsoft Scriptable Install System과 Inno Setup은 설치 파일 압축에 LZMA를 사용한다.
• lrzip는 "long range zip" 또는 "LZMA rzip"라고도 불리며, LZMA를 기반으로 한 압축 도구이다.^[2]

참조

_[1] 웹사이트 7z Format https://web.archive.[...] 2001-12-05
_[2] 웹사이트 A Quick Benchmark: Gzip vs. Bzip2 vs. LZMA http://tukaani.org/l[...] 2015-10-21
_[3] 웹사이트 Gzip, Bzip2 and Lzma compared http://blog.i-no.de/[...] 2013-06-16
_[4] 웹사이트 7z Format http://www.7-zip.org[...] 2013-06-16
_[5] 웹사이트 Data Compression Explained http://mattmahoney.n[...] 2013-11-13
_[6] 웹사이트 Xz format inadequate for long-term archiving http://lzip.nongnu.o[...] 2018-07-20
_[7] 웹사이트 Lzip Stream Format https://www.nongnu.o[...] 2019-11-14
_[8] 웹사이트 LZMA Specification.7z in LZMA SDK https://www.7-zip.or[...]
_[9] 웹사이트 lib/xz/xz_dec_lzma2.c https://git.kernel.o[...] 2013-06-16
_[10] 웹사이트 The .xz File Format http://tukaani.org/x[...] 2013-06-16
_[11] 웹사이트 LZMA SDK (Software Development Kit) http://7-zip.org/sdk[...] 2013-06-16
_[12] 웹사이트 Browse /LZMA SDK/4.23 http://sourceforge.n[...] SourceForge 2014-02-12
_[13] 웹사이트 Inno Setup Help http://www.jrsoftwar[...] jrsoftware.org 2013-06-16
_[14] 웹사이트 HISTORY of the 7-Zip http://www.7-zip.org[...] 2013-06-16
_[15] 웹사이트 PyLZMA – Platform independent python bindings for the LZMA compression library. http://www.joachim-b[...] 2013-06-16
_[16] 웹사이트 Programming Help: Pascal LZMA SDK http://www.birtles.o[...] 2013-06-16
_[17] 웹사이트 compress/lzma package for Go 1 http://lzma.googleco[...] 2013-06-16
_[18] 웹사이트 Zip-Ada http://unzip-ada.sou[...]
_[19] 웹사이트 Accepted dpkg 1.17.0 (source amd64 all) http://packages.qa.d[...] 2015-10-21
_[20] 웹사이트 Lzip Benchmarks http://lzip.nongnu.o[...] LZIP (nongnu)
_[21] 웹사이트 What is a Zipx File? http://kb.winzip.com[...] WinZip.com 2016-03-14
_[22] 웹사이트 LZHAM – Lossless Data Compression Codec https://github.com/r[...] Richard Geldreich
_[23] 웹사이트 The .xz File Format http://tukaani.org/x[...] 2018-04-22
_[24] 웹사이트 LZMA SDK (Software Development Kit) http://7-zip.org/sdk[...] 2018-04-22
_[25] 문서 SDK 역사 파일에는 1996년부터라고 이야기하고 있지만 [[7-zip]]에 처음 쓰인 것은 2001년 8월 30일이다. 일부 참조가 없는 의견에는 1998년으로 되어 있지만 이 알고리즘은 [[7-zip]]에 쓰이기 전까지는 출판된 적이 없는 것으로 보인다.
_[26] 웹인용 One of many forum posts with this claim. http://sourceforge.n[...] 소스포지 2013-06-16
_[27] 웹인용 A Quick Benchmark: Gzip vs. Bzip2 vs. LZMA http://tukaani.org/l[...] 2008-09-02
_[28] 웹인용 Gzip, Bzip2 and Lzma compared http://blog.i-no.de/[...] 2011-01-29
_[29] 문서 Overview of the LZMA format http://www.7-zip.org[...]