LZSS

렘펠-지브-스토러-시만스키(Lempel–Ziv–Storer–Szymanski, LZSS)는 비손실 데이터 압축 알고리즘으로, LZ77의 파생형이며 1982년 제임스 A. 스토러와 토마스 시만스키가 만들었다. LZSS는 Journal of the ACM에 실린 "Data compression via textual substitution"(1982, pp. 928–951) 기사에서 설명되었다.^[1]

LZSS는 사전 기반 부호화 기술이다. 이는 기호 문자열을 동일한 문자열의 사전 위치 참조로 바꾸려고 시도한다.

LZ77과 LZSS의 주요 차이점은 LZ77에서는 사전 참조가 실제로 대체하는 문자열보다 길 수 있다는 것이다. LZSS에서는 길이가 "손익분기점"보다 작으면 이러한 참조가 생략된다. 또한 LZSS는 다음 데이터 덩어리가 리터럴(바이트)인지 오프셋/길이 쌍에 대한 참조인지 나타내는 1비트 플래그를 사용한다.

예시

다음은 편의를 위해 줄 시작 부분에 문자 번호가 붙은 닥터 수스의 녹색 달걀과 햄의 시작 부분이다. 녹색 달걀과 햄은 책 자체는 170단어임에도 불구하고 50개의 고유한 단어만을 포함하고 있기 때문에 LZSS 압축을 설명하는 좋은 예이다.^[2] 따라서 단어는 반복되지만 연속적이지는 않다.

  0: I am Sam
  9:
 10: Sam I am
 19:
 20: That Sam-I-am!
 35: That Sam-I-am!
 50: I do not like
 64: that Sam-I-am!
 79:
 80: Do you like green eggs and ham?
112:
113: I do not like them, Sam-I-am.
143: I do not like green eggs and ham.

이 텍스트는 압축되지 않은 형태로 177바이트를 차지한다. 손익분기점을 2바이트(따라서 2바이트 포인터/오프셋 쌍)로 가정하고 한 바이트의 개행 문자를 가정하면, 이 텍스트는 LZSS로 압축되어 95바이트가 된다.

작동 중인 LZSS 압축의 색상 코드 예시.

 0: I am Sam
 9:
10: (5,3) (0,4)
16:
17: That(4,4)-I-am!(19,15)
32: I do not like
46: t(21,14)
50: Do you(58,5) green eggs and ham?
79: (49,14) them,(24,9).(112,15)(92,18).

참고: 여기에는 다음 텍스트 덩어리가 포인터인지 리터럴인지를 나타내는 11바이트의 플래그는 포함되지 않았다. 이를 추가하면 텍스트는 106바이트가 되며, 이는 여전히 원래의 177바이트보다 짧다.

구현

ARJ, RAR, ZOO, LHarc와 같은 많은 인기 있는 압축 프로그램은 LZ77 대신 LZSS를 주 압축 알고리즘으로 사용한다. 리터럴 문자와 길이-거리 쌍의 인코딩은 다양하며, 가장 일반적인 옵션은 허프먼 부호화이다. 대부분의 구현은 하루히코 오쿠무라가 1989년에 만든 퍼블릭 도메인 코드에서 파생되었다.^[3][4] 알레그로 라이브러리 버전 4는 LZSS 형식을 인코딩 및 디코딩할 수 있지만^[5] 버전 5에서는 이 기능이 제거되었다. 게임보이 어드밴스 BIOS는 약간 수정된 LZSS 형식을 디코딩할 수 있다.^[6] 애플의 macOS는 LZSS를 커널 코드의 압축 방식 중 하나로 사용한다.^[7]

같이 보기

• LZW