LZ77 및 LZ78

LZ77 and LZ78

LZ77과 LZ78은 Abraham Lempel과 Jacob Ziv가 1977년과 [2]1978년에 발표한[1] 두 개의 무손실 데이터 압축 알고리즘이다.이들은 [3]각각 LZ1과 LZ2로도 알려져 있습니다.이들 2개의 알고리즘은 LZW, LZSS, LZMA 등 다양한 종류의 기초가 됩니다.이러한 알고리즘은 학술적 영향 외에도 GIF 및 PNG 및 ZIP에서 사용되는 DEFLATE 알고리즘을 포함한 여러 유비쿼터스 압축 방식의 기초를 형성했습니다.

둘 다 이론적으로 사전 부호화이다.LZ77은 압축 중에 슬라이딩 윈도우를 유지합니다.이것은 나중에 LZ78에 의해 구축된 명시적 사전과 동등한 것으로 판명되었다.다만, 이러한 사전은 전체 데이터를 압축 해제하려는 경우에만 동등하다.

LZ77은 슬라이딩 윈도우에서 이전에 본 문자를 인코딩 및 디코딩하므로 압축 해제는 항상 입력 시작부터 시작해야 합니다.개념적으로 LZ78 압축해제는 사전 전체가 미리 알려진 경우 입력에 대한 랜덤 액세스를 허용할 수 있습니다.그러나 실제로는 토큰이 [4]출력될 때마다 새로운 문구를 생성하여 인코딩 및 디코딩 중에 사전이 생성됩니다.

이 알고리즘은 2004년에 [5]IEEE 마일스톤으로 명명되었습니다.2021년 Jacob Ziv는 그들의 [6]개발에 기여한 공로로 IEEE 명예 훈장을 받았습니다.

이론적인 효율

이들 알고리즘을 소개한 두 번째 논문에서는 유한 상태 기계에 의해 정의된 인코더로 분석됩니다.(확률론적 앙상블과는 대조적으로) 개별 시퀀스에 대해 정보 엔트로피와 유사한 척도가 개발된다.이 척도는 달성할 수 있는 데이터 압축률에 대한 한계를 제공합니다.다음으로 시퀀스의 길이가 무한대로 증가함에 따라 이 경계를 달성하는 모든 시퀀스에 대해 유한 무손실 인코더가 존재하는 것으로 나타납니다.이런 의미에서 이 스킴에 기초한 알고리즘은 점근적으로 최적의 인코딩을 생성한다.이 결과는 Peter Shor의 [7]메모에서처럼 보다 직접적으로 입증될 수 있습니다.

LZ77

LZ77 알고리즘은 반복적으로 발생하는 데이터를 압축되지 않은 데이터 스트림의 초기에 존재하는 데이터의 단일 복사본에 대한 참조로 대체함으로써 압축을 실현합니다.일치는 length-distance pair라고 불리는 숫자의 쌍으로 부호화됩니다.이는 "다음 길이의 각 문자는 압축되지 않은 스트림에서 뒤에 있는 문자와 동일합니다." (이 문자는 오프셋이라고도 합니다.

일치하는 것을 특정하려면 인코더는 최신 데이터(마지막 2kB, 4kB, 32kB 등)를 추적해야 합니다.이 데이터가 보관되는 구조를 슬라이딩 윈도우라고 하며, 이것이 LZ77을 슬라이딩 윈도우 압축이라고 부르기도 합니다.인코더는 일치를 검색하기 위해 이 데이터를 보관해야 하며, 디코더는 인코더가 참조하는 일치를 해석하기 위해 이 데이터를 보관해야 합니다.슬라이딩 윈도우가 클수록 인코더는 참조 작성을 검색하는 시간이 길어집니다.

거리 쌍이 실제로 거리를 초과하는 길이를 지정할 수 있도록 하는 것이 허용될 뿐만 아니라 자주 유용합니다.copy 명령어로서 "4글자를 되돌리고 그 위치에서 현재 위치로 10글자를 복사하십시오."라는 난해한 내용이 있습니다.그 중 4개의 문자만 버퍼에 있는데 어떻게 10개의 문자를 복사할 수 있을까요?한 번에 1바이트씩 처리하면 바이트가 복사될 때 copy 명령에 대한 입력으로 다시 공급될 수 있기 때문에 이 요청을 처리하는 데 문제가 없습니다.copy-from 위치가 초기 수신인 위치에 도달하면 copy-from 위치의 시작부터 붙여진 데이터가 공급됩니다.따라서 이 작업은 "지정된 데이터를 복사하여 적합할 때까지 반복적으로 붙여넣기" 문과 동일합니다.이러한 유형의 쌍은 단일 데이터 복사본을 여러 번 반복하므로 유연하고 쉬운 형식의 런타임 인코딩을 통합하기 위해 사용할 수 있습니다.

사물을 보는 또 다른 방법은 다음과 같습니다.부호화 중 검색 포인터가 검색 창의 끝을 지나 일치하는 쌍을 계속 찾으려면 오프셋D에서 일치하는 첫 번째 문자부터 검색 창의 끝까지 일치하는 모든 문자가 일치해야 합니다.이 문자는 길이R L의 단일 실행 단위를 구성하는 (앞에서 확인한) 문자여야 합니다.이 문자는 D와 같아야 합니다.그런 다음 검색 포인터가 검색 창을 지나 앞으로 진행되면 입력에서 실행 패턴이 반복되는 한 검색과 입력 포인터는 동기화되어 실행 패턴이 중단될 때까지 문자를 일치시킵니다.그 후 L 문자의 합계가 L > D이고 코드는 [D, L, c]입니다.

[D, L, c]를 디코딩할 때 D = LR. 첫 번째R L 문자를 출력에 읽을 때 출력 버퍼에 추가된 단일 실행 장치에 해당합니다.이 시점에서 읽기 포인터는 단일 버퍼링된 실행 유닛의 시작까지 int(LR/L) + (LR mod L 0 0인 경우 1) 회를 반환하고 L 문자를 판독하여R 총 L 문자를 읽을 때까지 반복하기만 하면 된다고 생각할 수 있습니다.그러나, 부호화 프로세스를 미러링 하는 경우는, 패턴이 반복하고 있기 때문에, 읽기 포인터는, L자가 카피되어 전체적으로 출력될 때까지, 실행 길이R L과 같은 일정한 거리만큼만 기입 포인터와 동기하면 됩니다.

상기의 점을 고려하면, 특히 데이터 실행의 압축이 우세할 것으로 예상되는 경우, 윈도우 검색은 윈도우의 끝에서 시작하여 뒤로 진행되어야 합니다. 왜냐하면, 실행 패턴이 존재한다면, 먼저 발견되고 검색이 종료될 수 있기 때문입니다. 만약 현재의 최대 일치 시퀀스 길이가 충족된다면, 또는 적절한 경우, 절대적으로 검색이 종료될 수 있습니다.충분한 길이가 충족되고 마지막으로 데이터가 보다 최신이며 다음 입력과 더 잘 관련될 수 있다는 단순한 가능성을 위해.

유사 코드

의사 코드는 LZ77 압축 알고리즘슬라이딩 윈도우를 재현한 것입니다. 

입력이 비어 있지 않은 동안 match : = 창에서 시작하는 입력의 가장 긴 반복 발생 : = 일치하는 경우 match l : = match c : = char의 시작까지의 거리 d : = 입력 d : = 0 l : = 0 c : = 출력의 경우 입력 끝의 첫 번째 문자 d : =창 앞에 있는 l + 1자를 삭제합니다. : = pop l + 1자를 입력 앞에 있는 창 뒤에 추가합니다.

실장

모든 LZ77 알고리즘은 동일한 기본 원리로 정의되어 동작하지만 압축된 데이터를 부호화하는 방법은 매우 다양하며, 길이와 거리 쌍의 숫자 범위를 변경하고, 길이와 거리 쌍을 리터럴로부터 구별합니다(원래 데이터 자체로서 부호화된 래트).장거리 쌍의 일부로서보다 더 많은 정보를 얻을 수 있습니다).몇 가지 예:

  • Lempel과 Ziv의 원래 1977년 기사에 설명된 알고리즘은 버퍼에서 발견된 가장 긴 일치의 길이와 거리, 그리고 일치하는 리터럴의 세 가지 값을 한번에 모든 데이터를 출력합니다.입력 스트림에서 연속되는2개의 문자를 리터럴로만 부호화할 수 있는 경우, 길이와 거리 쌍의 길이는 0이 됩니다.
  • LZSS는 1비트플래그를 사용하여 다음 데이터 청크가 리터럴인지 길이와 거리 중 어느 쪽인지를 나타내고 길이와 거리 중 어느 쪽이 긴지 리터럴을 사용함으로써 LZ77에서 개선됩니다.
  • PalmDoc 형식에서는 길이와 거리의 쌍은 항상 2바이트 시퀀스로 부호화됩니다.이들 2바이트를 구성하는 16비트 중 11비트는 디스턴스 부호화, 3비트는 길이 부호화, 나머지 2비트는 디코더가 이러한 2바이트 시퀀스의 선두로 첫 번째 바이트를 식별할 수 있도록 하기 위해 사용됩니다.
  • 구현 많은 게임용 전자 Arts,[8]에서 사용하는에서 한 length–distance 한쌍의 크기를 바이트 단위로 그 length–distance 한쌍 그 자체의 첫번째 바이트다. 이 첫번째 바이트는 0,10,110,111( 때 빅 엔디언 비트 방위에 읽), 전체 length–distance/값 쌍의 길이 될 수 있는 것에서 시작한다에 따라 안에 지정할 수 있다.로.4 바이트
  • 2008년 현재 가장 일반적인 LZ77 기반 압축 방식은 DEFLATE입니다. LZSS와 Huffman 부호화를 [9]결합합니다.리터럴, 길이 및 현재 데이터 블록의 끝을 나타내는 기호가 모두 하나의 알파벳으로 배치됩니다.거리는 다른 알파벳으로 안전하게 배치할 수 있습니다. 거리는 길이가 끝난 직후에만 발생하므로 다른 종류의 기호로 오인할 수 없습니다.

LZ78

LZ78 알고리즘은 입력으로부터 토큰 시퀀스의 사전을 구축한 후 데이터 스트림에서 시퀀스의 두 번째 이후의 발생을 사전 엔트리에 대한 참조로 대체함으로써 시퀀셜 데이터를 압축합니다.관찰 결과, 반복된 시퀀스의 수는 시퀀스의 비랜덤 성질을 잘 나타내는 척도입니다.알고리즘은 사전을 n-ary 트리로 나타냅니다.n은 토큰 시퀀스를 형성하기 위해 사용되는 토큰 수입니다.각 사전 항목은 다음 형식입니다.dictionary[...] = {index, token}여기서 index는 이전에 본 시퀀스를 나타내는 딕셔너리 엔트리에 대한 인덱스입니다.token은 이 엔트리를 사전에서 일의로 만드는 입력의 다음 토큰입니다.알고리즘의 부하가 높은 것에 주의해 주세요.따라서 고유 메이킹토큰이 발견될 때까지 테이블에 아무것도 추가되지 않습니다.알고리즘은 마지막 일치 인덱스 = 0 및 다음 사용 가능한 인덱스 = 1을 초기화한 다음 입력 스트림의 각 토큰에 대해 사전에서 일치 항목을 검색했습니다.{last matching index, token}일치하는 것이 발견되면 일치하는 엔트리의 인덱스로 마지막 일치 인덱스가 설정되고 아무것도 출력되지 않으며 마지막 일치 인덱스는 지금까지의 입력을 나타냅니다.일치하는 항목을 찾을 수 없을 때까지 입력이 처리됩니다.그러면 새 사전 항목이 생성됩니다.dictionary[next available index] = {last matching index, token}알고리즘은 마지막 일치 인덱스와 토큰을 출력한 다음 마지막 일치 인덱스 = 0을 재설정하고 사용 가능한 다음 인덱스를 증가시킵니다.예를 들어 사전을 조립하는 일련의 토큰을 고려합니다.

0 {0,_} 1 {0,A} 2 {1,B} 3 {0,B}

그리고 압축된 데이터의 출력 시퀀스는 입니다.알고리즘은 다음에 무엇을 할지 알 수 없기 때문에 마지막 A는 아직 표현되지 않았습니다.실제로 입력에 EOF 마커가 추가됩니다(예:또한 이 경우 출력은 원래 입력보다 길지만 사전이 커짐에 따라 압축률이 크게 향상되고 바이너리에서는 인덱스를 최소 비트 [10]수 이상으로 표시할 필요가 없습니다.

압축 해제에는 압축된 시퀀스에서 사전을 재구축하는 작업이 포함됩니다.시퀀스의 첫 번째 엔트리는 항상 터미네이터이고 시퀀스 첫 번째 엔트리는 입니다.가 출력에 추가됩니다.입력의 두 번째 쌍은 이며 결과적으로 사전의 엔트리 번호 2가 됩니다.토큰 "B"가 출력되고 그 앞에 사전 엔트리 1로 표시되는 시퀀스가 출력됩니다.엔트리 1은 'A'이므로(뒤에 'entry 0' - nothing) 출력에 추가됩니다.다음 엔트리에 따라 [Next]가 딕셔너리에 추가되고 출력에 [B](우선)가 추가됩니다.마지막으로 의 사전 엔트리가 생성되어 공간 및 EOF 마커를 생성 또는 삭제하여 출력됩니다.

LZW

LZW는 LZ78 기반의 알고리즘으로 가능한 모든 문자(심볼) 또는 사전 초기화 사전의 에뮬레이션을 사용하여 사전 초기화됩니다.LZW의 주요 개선사항은 일치를 찾을 수 없을 때 현재 입력 스트림 문자는 사전에서 기존 문자열의 첫 번째 문자로 간주되므로(사전이 가능한 모든 문자로 초기화되므로), 마지막 일치 색인만 출력됩니다(사전 초기화 사전 색인일 수 있음).이전(또는 첫 번째) 입력 문자로 이동합니다.실장의 상세한 것에 대하여는, LZW 문서를 참조해 주세요.

BTLZ는 실시간 통신 시스템(원래 모뎀)에서 사용하기 위해 개발된 LZ78 기반의 알고리즘으로 CCITT/ITU에 의해 V.42bis로 표준화되었습니다.Trie 구조화된 사전이 가득 차면 사전이 변화하는 데이터에 계속 적응할 수 있도록 간단한 재사용/복구 알고리즘이 사용됩니다.카운터가 사전을 순환합니다.새로운 엔트리가 필요한 경우 카운터는 리프 노드(의존자가 없는 노드)가 검출될 때까지 딕셔너리를 스텝으로 진행합니다.이것은 삭제되고 공간은 새 엔트리에 다시 사용됩니다.이는 LRU나 LFU보다 구현이 간단하고 동등한 성능을 실현합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Ziv, Jacob; Lempel, Abraham (May 1977). "A Universal Algorithm for Sequential Data Compression". IEEE Transactions on Information Theory. 23 (3): 337–343. CiteSeerX 10.1.1.118.8921. doi:10.1109/TIT.1977.1055714.
  2. ^ Ziv, Jacob; Lempel, Abraham (September 1978). "Compression of Individual Sequences via Variable-Rate Coding". IEEE Transactions on Information Theory. 24 (5): 530–536. CiteSeerX 10.1.1.14.2892. doi:10.1109/TIT.1978.1055934.
  3. ^ 미국 특허 제5532693호 수축기 문자열 매칭 로직을 갖춘 적응형 데이터 압축 시스템
  4. ^ "Data Compression "The Concept"".
  5. ^ "Milestones:Lempel-Ziv Data Compression Algorithm, 1977". IEEE Global History Network. Institute of Electrical and Electronics Engineers. 22 July 2014. Retrieved 9 November 2014.
  6. ^ Joanna, Goodrich. "IEEE Medal of Honor Goes to Data Compression Pioneer Jacob Ziv". IEEE Spectrum: Technology, Engineering, and Science News. Retrieved 18 January 2021.{{cite web}}: CS1 maint :url-status (링크)
  7. ^ Peter Shor (14 October 2005). "Lempel-Ziv notes" (PDF). Retrieved 9 November 2014.
  8. ^ "QFS Compression (RefPack)". Niotso Wiki. Retrieved 9 November 2014.
  9. ^ Feldspar, Antaeus (23 August 1997). "An Explanation of the Deflate Algorithm". comp.compression newsgroup. zlib.net. Retrieved 9 November 2014.
  10. ^ https://math.mit.edu/~goemans/18310S15/lempel-ziv-notes.pdf[베어 URL PDF]

외부 링크

  • "The LZ78 algorithm". Data Compression Reference Center: RASIP working group. Faculty of Electrical Engineering and Computing, University of Zagreb. 1997. Archived from the original on 7 January 2013. Retrieved 22 June 2012.
  • "The LZW algorithm". Data Compression Reference Center: RASIP working group. Faculty of Electrical Engineering and Computing, University of Zagreb. 1997. Archived from the original on 7 January 2013. Retrieved 22 June 2012.