Lempel–Ziv–Markov chain Algorithm
1. 개요
7-Zip의 제작자인 러시아의 Igor Pavlov(러: Игорь Павлов, 1950~)에 의해 개발된 데이터 압축 알고리즘. 7z 포맷에 사용되고 있으며, 퍼블릭 도메인으로 SDK를 공개하였다.LZMA SDK 홈페이지
2. 특징
이 압축 알고리즘은 1차적으로 LZ77 알고리즘[1]을 이용해서 데이터를 압축하고, 2차적으로 Adaptive Binary Range Coder를 이용해서 압축을 수행한다.일반적으로 RAR포맷에서 사용하는 압축 알고리즘보다 압축률이 좋은 것으로 알려져 있으며, 효율이 좋은 이유는 매우 큰 LZ77 윈도우(4GiB 까지)를 사용하고, 압축 효율을 높이기 위한 최적화가 잘 되었기 때문.
SDK는 공개되어 있지만, 속도 향상을 위해서 코드가 복잡하고, 주석도 한 줄 안 달려 있기 때문에 공개된 소스를 가지고 변형해서 뭔가 다른걸 만들어 보는 것은 거의 불가능한 수준.
LZMA2는 LZMA가 멀티 코어 지원에 취약(최대 2개의 스레드만 지원)한 점을 개선하기 위해서 만들어진 알고리즘이며, 사용 가능한 수만큼 스레드를 사용하여 병렬로 압축을 하기 때문에 속도가 무척 빠르지만, 메모리도 그만큼 정수 배로 사용하기 때문에 메모리 사용량도 엄청나다. 예를 들어 압축률 최대를 사용하여 8스레드로 압축할 경우 최대 4×8GiB 메모리를 필요로 한다.
압축 효율이 좋으며, 퍼블릭 도메인으로 공개된 압축 알고리즘이기 때문에 ZIP이나 EGG 포맷에서도 이 압축 알고리즘을 사용한다.
2.1. LZMA2
LZMA 알고리즘이 압축률은 매우 높지만, 멀티코어를 활용할 수 없다는 단점을 보완하기 위해서 약간 개선된 알고리즘이다. 멀티코어 활용이 목적이기 때문에 압축률은 LZMA와 거의 차이가 없다.이 압축 알고리즘을 이용하면 압축할 데이터를 여러개로 쪼개서 동시에 병렬로 압축을 할 수 있기 때문에 현재의 멀티코어 CPU에서 압축속도를 크게 향상 시킬 수 있다. 예를 들어서 4개의 코어를 가진 시스템에서 4개의 스레드로 압축을 할 경우, 디스크 I/O만 받쳐준다면 싱글 스레드로 압축을 할 때보다 3배 이상 빠르게 압축하는게 가능하다.
다만, 모토가 되는 LZ77 알고리즘의 특성상 압축률을 떨어트리지 않고 압축하기 위해서는 압축하는데 필요한 메모리 사용량이 스레드 개수만큼 늘어나게 된다. 예를 들어 LZ77용 사전의 크기를 4GiB 지정하고, 압축 스레드를 4개로 지정한 경우, 16GiB 이상의 메모리가 필요하다.
3. 기타
이스트소프트에서 공개한 EGG 포맷은 공개된 압축 알고리즘인 Deflate, Bzip2, LZMA 이외에도 자체적으로 개발한 AZO 알고리즘을 사용하는데, 이 알고리즘은 LZMA와 거의 똑같은 방식을 사용하는 것으로 보인다. 반디집 6.0에서 이스트소프트 요청에 따라 AZO 압축 해제가 제외되었지만, 이후 리버스 엔지니어링으로 자체 구현하면서 6.19 버전부터 다시 압축 해제가 가능해졌다.4. 관련 문서
[1]
Abraham Lempel과 Jacob Ziv이 제작한 알고리즘. LZMA의 Lempel과 Ziv는 이 개발자들의 이름에서 따온 것이다.