LZSSL 압축

LZSS with Literal copy command
기반이 되는 LZSS 압축 알고리즘은 LZ77의 개량형으로, 압축이 필요하지 않은 부분(압축을 했을 때 오히려 압축 전보다 크기가 늘어나는 부분)은 단일 문자로 저장하도록 개선되었다. 이를 이진 파일에 적용할 경우, 단일 문자/오프셋, 길이 형식 토큰 여부를 설정하는 비트를 읽고 검사함으로써 이를 달성할 수 있다.
나는 여기에 더해 첫 바이트에 압축 여부 비트에 더해 문자의 갯수를 결정하는 비트를 추가함으로써 긴 비압축 문자의 표현을 효율적으로 할 수 있도록 하는 LZSS 알고리즘의 변형을 구상했다.
이것이 LZSSL 알고리즘이라 부르는 알고리즘이다.
이 알고리즘으로 압축한 결과물은 바이트 단위로 정렬되어 비트 단위 접근이 필요하지 않으며, 1비트 검사 비트가 첫 바이트의 최상위 비트에 할당되어 있고, 나머지 비트는 검사 비트의 결과에 따라 출력할 문자의 갯수 또는 복사할 문자의 갯수 + 복사할 문자의 위치의 최상위 비트들이 따라온다. (이 경우 다음 바이트는 이 위치의 하위 비트로 할당된다.)
이를 '토큰'이라 하며, 압축 결과물은 모두 토큰으로 구성되어 있다. 토큰의 구조는 다음과 같다.
- 첫 바이트의 최상위 비트: 검사 비트
- 검사 비트가 1(비압축 문자의 배열)인 경우, 나머지 7개 비트는 출력할 문자의 갯수를 의미한다. 이후 이 비트값 +1 만큼의 바이트가 따라오며, 이들은 압축 없이 출력할 일련의 문자를 의미한다. 또한 이들 문자는 슬라이딩 윈도우의 끝부분에 하나씩 저장된다.
- 검사 비트가 0(문자열 복사)인 경우, 뒤의 4비트는 복사할 문자열의 길이 + 3, 나머지 3비트는 복사할 문자열의 위치의 상위 3비트에 할당되며, 다음에 오는 바이트는 복사할 문자열의 위치의 하위 8비트에 할당된다. 이들 정보를 가지고 슬라이딩 윈도우에 있는 문자들을 복사해 출력한다.
- 따라서 본 알고리즘에서 사용하는 슬라이딩 윈도우의 크기는 2KiB(2의 11승)이다.
슬라이딩 윈도우는 처음에는 모두 0으로 초기화되어 0값의 배열로 시작하는 파일에 대한 압축 효율성에 도모한다.

또한 이 알고리즘의 변형으로 가변 길이 바이트 토큰을 사용하는 것도 있는데, 이는 각각 출력할 문자의 개수와 복사할 문자의 위치 값의 최상위 비트를 이들의 가변 바이트 플래그로 전용하여 더 큰 파일에 대한 압축 효율성을 꾀한다. 다만 이 변형은 파일이 어느정도 이상 클 경우에만 최대한의 효과를 발휘한다.

다음은 이 알고리즘을 ANSI C로 구현한 구현체이며, 기존에 존재하는 LZSS의 ANSI C 구현체의 포크임과 동시에 개조판이다.

https://github.com/cam900/lzss/tree/lzss_literal

GitHub - cam900/lzss: lzss: An ANSI C implementation of the LZSS compression algorithm