LZ4 (압축 알고리즘)

LZ4는 압축 및 압축 해제 속도에 초점을 맞춘 비손실 데이터 압축 알고리즘이다. 이는 바이트 지향 압축 방식인 LZ77 계열에 속한다.

특징
LZ4 알고리즘은 속도와 압축률 간의 좋은 절충점을 제공하는 것을 목표로 한다. 일반적으로 유사한 LZO 알고리즘보다 압축률이 더 낮고(즉, 나쁘고), LZO는 다시 DEFLATE와 같은 알고리즘보다 나쁘다. 그러나 LZ4의 압축 속도는 LZO와 유사하며 DEFLATE보다 몇 배 빠르며, 압축 해제 속도는 LZO보다 훨씬 빠르다.

설계
LZ4는 사전 일치 단계(LZ77)만 사용하며, 다른 일반적인 압축 알고리즘과는 달리 이를 엔트로피 부호화 단계(예: DEFLATE의 허프먼 부호화)와 결합하지 않는다.

LZ4 알고리즘은 데이터를 일련의 시퀀스로 표현한다. 각 시퀀스는 두 개의 4비트 필드로 나뉜 1바이트 토큰으로 시작한다. 첫 번째 필드는 출력으로 복사될 리터럴 바이트 수를 나타낸다. 두 번째 필드는 이미 디코딩된 출력 버퍼에서 복사할 바이트 수를 나타낸다 (0은 최소 일치 길이인 4바이트를 나타낸다). 두 비트 필드 중 하나에서 15 값은 길이가 더 크며 길이에 추가될 추가 바이트 데이터가 있음을 나타낸다. 이러한 추가 바이트에서 255 값은 또 다른 바이트가 추가될 것임을 나타낸다. 따라서 임의의 길이는 255 값을 포함하는 일련의 추가 바이트로 표현된다. 리터럴 문자열은 토큰과 문자열 길이를 나타내는 데 필요한 추가 바이트 뒤에 온다. 그 다음에는 출력 버퍼에서 얼마나 뒤로 복사를 시작할지를 나타내는 오프셋이 온다. 일치 길이의 추가 바이트(있는 경우)는 시퀀스의 끝에 온다.

압축은 스트림 또는 블록 단위로 수행할 수 있다. 최적의 일치를 찾는 데 더 많은 노력을 기울임으로써 더 높은 압축률을 달성할 수 있다. 이는 더 작은 출력과 더 빠른 압축 해제를 모두 가능하게 한다.

LZ4는 두 가지 프레임 형식을 가지고 있다. 이전 형식은 매우 제한적이었고 외부 파일 끝 신호에 의존했는데, 이는 리눅스 Initramfs에서 제로 패딩을 처리하기 위한 해결책이 필요하다는 문제로 나타났다. 새로운 형식은 훨씬 더 유연하며 자체적인 프레임 끝 마커를 가지고 있다. 이는 Zstd 프레임 형식과 디자인이 유사하다.

구현
얀 콜레의 C로 된 참조 구현은 BSD 라이선스에 따라 라이선스된다. 자바, C#, 러스트, 파이썬을 포함한 다양한 언어로 포트 및 바인딩이 존재한다. 아파치 하둡 시스템은 이 알고리즘을 빠른 압축을 위해 사용한다. LZ4는 리눅스 커널 3.11에도 네이티브로 구현되었다. FreeBSD, Illumos, 리눅스의 ZFS, ZFS-OSX의 ZFS 파일 시스템 구현은 즉석 압축을 위한 LZ4 알고리즘을 지원한다. 리눅스는 3.19-rc1부터 SquashFS에 LZ4를 지원한다. LZ4는 얀 콜레의 최신 Zstd 명령줄 유틸리티와 7-Zip-zstd라는 7-Zip 포크에서도 지원된다.7-zip-zstd

 각주 

 외부 링크 


분류:C 라이브러리
분류:데이터 압축
분류:무손실 압축 알고리즘
분류:자유 압축 소프트웨어