렘펠 지브 스토르 시만스키

Lempel–Ziv–Storer–Szymanski

Lempel-Ziv-Storer-Szymanski(LZSS)무손실 데이터 압축 알고리즘으로 1982년에 James A에 의해 작성되었습니다. 스토어토마스 시만스키.LZSS는 ACM 저널(1982년, 페이지 928–951)[1]에 게재된 "텍스트 치환을 통한 데이터 압축" 기사에서 설명되었다.

LZSS는 사전 코딩 기법입니다.기호 문자열을 동일한 문자열의 사전 위치에 대한 참조로 바꾸려고 시도합니다.

LZ77과 LZSS의 주요 차이점은 LZ77에서는 딕셔너리 참조가 실제로 치환된 문자열보다 길 수 있다는 것입니다.LZSS에서는 길이가 "손익분기점"보다 작을 경우 이러한 참조는 생략됩니다.또한 LZSS는 1비트 플래그를 사용하여 다음 데이터 청크가 리터럴(바이트)인지 오프셋/길이 쌍에 대한 참조인지를 나타냅니다.

여기 Dr.의 시작이 있다.수스의 그린 에그와 햄, 줄 맨 앞에 문자 번호가 붙어 있어 편리합니다.Green Eggs and Ham은 LZSS 압축의 좋은 예입니다.왜냐하면 이 책 자체에는 단어 수가 [2]170개임에도 불구하고 50개의 고유 단어만 포함되어 있기 때문입니다.따라서, 단어들은 반복되지만, 연속해서 반복되지는 않는다.

0: 나는 Sam 9: 10: Sam 19: 20: That Sam-I-am! 35: That Sam-I-am! 50: 나는 64: 저 Sam-I-am! 79: 80: 너는 녹색 달걀과 햄을 좋아하니? 112: 113: 나는 그것들을 좋아하지 않아, Sam-I-am: 143: 나는 녹색을 좋아하지 않아. 

이 텍스트는 압축되지 않은 형식으로 177바이트입니다.손익분기점 2바이트(따라서2바이트 포인터/오프셋쌍)와 1바이트의 줄바꿈이라고 가정하면 LZSS로 압축된 이 텍스트는 94바이트 길이가 됩니다.

A color coded example to help illustrate the recycling of repeated information to minimize storage.
동작하고 있는 LZSS 압축의 컬러 코드화된 예.
0: 나는 Sam 9: 10: (5,3) (0,4) 16: 17: That (4,4)-I-am! (19,16)나는 45: t(21,14) 49: 녹색 달걀과 햄을 좋아하나요? 78:(49,14)그것들,(24,9),(112,15)(92,18) 

주의: 여기에는 다음 텍스트 청크가 포인터인지 리터럴인지를 나타내는 12바이트의 플래그는 포함되지 않습니다.이를 더하면 텍스트 길이는 106바이트가 되는데, 이는 원래 177바이트보다 여전히 짧습니다.

실장

PKZip, ARJ, RAR, ZOO, LHarc같은 많은 인기 있는 아카이브버들은 LZ77 대신 LZSS를 사용합니다.리터럴 문자와 장거리 쌍의 인코딩은 다양하며 가장 일반적인 옵션은 Huffman 코딩입니다.대부분의 구현은 오쿠무라 [3][4]하루히코1989년 퍼블릭 도메인 코드에서 비롯되었습니다.Allegro 라이브러리의 버전4에서는 LZSS [5]포맷을 인코딩 및 디코딩할 수 있습니다만, 이 기능은 버전5에서 잘라졌습니다.게임보이 어드밴스 BIOS는 약간 변경된 LZSS [6]포맷을 디코딩할 수 있습니다.Apple의 Mac OS X는 커널 [7]코드의 압축 방법 중 하나로 LZSS를 사용합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Storer, James A.; Szymanski, Thomas G. (October 1982). "Data Compression via Textual Substitution". Journal of the ACM. 29 (4): 928–951. doi:10.1145/322344.322346.
  2. ^ "10 stories behind Dr. Seuss stories". CNN. January 23, 2009. Retrieved 2009-01-26.
  3. ^ Simtel.net 미러1989년의 오쿠무라 하루히코 실장.1999년 2월 3일에 아카이브 완료.
  4. ^ 오쿠무라 하루히코일본의 데이터 압축 역사2016년 1월 10일 보관.
  5. ^ 하그리브스, 숀[pl]알레그로 소스 코드: lzss.c.2016년 7월 13일에 접속.
  6. ^ Korth, Martin. "GBATEK LZ Decompression Functions". problemkaputt.de. Retrieved 7 June 2022.{{cite web}}: CS1 maint :url-status (링크)
  7. ^ "kext_tools/compression.c". GitHub. Apple Open Source. Retrieved 28 December 2019.