렘펠-지브-스택

Lempel–Ziv–Stac

Lempel-Ziv-Stac(LZS, 또는 Stac 압축 또는 Stacker 압축[1])은 LZ77 슬라이딩 윈도우 압축 알고리즘과 고정 허프만 코딩의 조합을 사용하는 무손실 데이터 압축 알고리즘이다.원래는 Stac Electronics가 테이프 압축을 위해 개발했으며, 이후 하드 디스크 압축에 맞게 개조되어 Stacker 디스크 압축 소프트웨어로 판매되었다.나중에 다양한 네트워크 프로토콜에 대한 압축 알고리즘으로 지정되었다.LZS는 Cisco IOS 스택에 지정되어 있다.

표준

LZS 압축은 INCITS(이전의 ANSI) 표준으로 표준화되어 있다.[2]

LZS 압축은 다양한 인터넷 프로토콜에 대해 지정된다.

  • RFC 1967PPP LZS-DCP 압축 프로토콜(LZS-DCP)
  • RFC 1974PPP Stac LZS 압축 프로토콜
  • RFC 2395LZS를 이용한 IP 페이로드 압축
  • RFC 3943LMS(Lempel-Ziv-Stac)를 이용한 TLS(Transport Layer Security(Transport Layer Security)

알고리즘.

LZS 압축 및 압축 해제는 LZ77 유형 알고리즘을 사용한다.마지막 2KB의 압축되지 않은 데이터를 슬라이딩 윈도우 사전으로 사용한다.

LZS 압축기는 압축할 데이터와 마지막 2KB의 데이터 사이에서 일치하는 데이터를 찾는다.일치하는 것을 찾으면 사전에 오프셋/길이 참조를 인코딩한다.일치하는 것을 찾지 못하면, 다음 데이터 바이트는 "문자" 바이트로 암호화된다.압축된 데이터 스트림은 엔드 마커로 끝난다.

압축 데이터 형식

데이터는 가변 비트 폭 토큰의 스트림으로 인코딩된다.

리터럴 바이트

리터럴 바이트는 '0' 비트에 이어 바이트의 8비트로 인코딩된다.

간격띄우기/길이 참조

오프셋/길이 참조는 '1' 비트에 이어 인코딩된 오프셋에 이어 인코딩된 길이로 인코딩된다.하나의 예외적인 인코딩은 아래에 설명된 엔드 마커다.

오프셋은 최소값 1과 최대값 2047을 가질 수 있다.값 1은 처리할 다음 데이터 바이트 바로 앞에 있는 기록 버퍼에서 가장 최근 바이트를 가리킨다.오프셋은 다음과 같이 인코딩된다.

  • 오프셋이 128: '1' 비트에 이어 7비트 오프셋 값이 되는 경우.
  • 오프셋이 128보다 크거나 같은 경우: '0' 비트에 이어 11비트 오프셋 값이 나오는 경우.

길이는 다음과 같이 인코딩된다.

길이 비트 인코딩
2 00
3 01
4 10
5 1100
6 1101
7 1110
8-22 1111 xxxxx, 여기서 xxxxx는 길이 - 8
23대 37 1111 1111 xxxxx, 여기서 xxxxx는 길이 - 23
길이 > 37 (1111번 반복 N번) xxxxx, 여기서

N은 (길이 + 7) / 15의 정수 결과로서,
xxxxx는 길이 - (N*15 - 7)

끝마커

엔드 마커는 9비트 토큰 110000000으로 인코딩된다.엔드 마커에 이어, 필요에 따라 0~7개의 추가 '0' 비트가 추가되어 스트림을 다음 바이트 경계까지 패딩한다.

특허

Stac Electronics의 스핀오프 Hifn은 LZS 압축 특허를 여러 번 보유하고 있다.[3][4]이들 특허는 수수료 미납으로 소멸돼 2007년 복권 시도가 실패했다.

1993-94년, Stac Electronics는 MS-DOS 6.0에 포함된 더블 스페이스 디스크 압축 프로그램에서 마이크로소프트사를 LZS 특허 침해로 성공적으로 고소했다.[5]

참고 항목

참조

  1. ^ "Understanding Data Compression". Cisco. Retrieved 2021-05-07.
  2. ^ INCITS/ANSI X3.241-1994 - 데이터 압축 방법 - 정보 교환을 위한 슬라이딩 창을 사용한 적응적 코드화
  3. ^ Friend, Robert C. "Hifn's Statement about IPR claimed in draft-friend-tls-lzs-compression, RFC1967, RFC1974, RFC2118, RFC2395, and RFC3078". Retrieved 21 July 2010.
  4. ^ Friend, Robert. "Hifn's Statement on IPR Claimed in LZS and MPPC compression algorithms". Retrieved 21 July 2010.
  5. ^ Stac Electronics v Microsoft Corporation의 Wayback Machine2007-05-09년 보관된 특허 침해 및 배심 재판 수요에 대한 불만