LZ77 및 LZ78

LZ77과 LZ78은 1977년^[1]과 1978년^[2] 아브라함 렘펠과 야코브 지브가 논문으로 발표한 두 가지 비손실 데이터 압축 알고리즘이다. 이들은 각각 렘펠-지브 1 (LZ1)과 렘펠-지브 2 (LZ2)로도 알려져 있다.^[3] 이 두 알고리즘은 LZW, LZSS, LZMA 및 기타 여러 변형의 기초를 형성한다. 학술적 영향 외에도 이 알고리즘은 GIF 및 이동식 네트워크 그래픽과 ZIP에서 사용되는 DEFLATE 알고리즘을 포함하여 여러 유비쿼터스 압축 체계의 기반을 형성했다.

둘 다 이론적으로는 사전 기반 부호화 방식이다. LZ77은 압축 중에 슬라이딩 윈도우를 유지한다. 이는 나중에 LZ78이 구성한 명시적 사전과 동등하다는 것이 밝혀졌지만, 전체 데이터가 압축 해제될 때만 동등하다.

LZ77은 이전에 본 문자를 슬라이딩 윈도우를 통해 인코딩하고 디코딩하므로 압축 해제는 항상 입력의 시작 부분에서 시작해야 한다. 개념적으로 LZ78 압축 해제는 전체 사전이 미리 알려져 있다면 입력에 대한 임의 접근을 허용할 수 있다. 그러나 실제로는 토큰이 출력될 때마다 새 구문을 생성하여 인코딩 및 디코딩 중에 사전이 생성된다.^[4]

이 알고리즘은 2004년에 IEEE 마일스톤으로 지정되었다.^[5] 2021년 야코브 지브는 이들의 개발에 참여한 공로로 IEEE 명예의 메달을 수상했다.^[6]

이론적 효율성

이 알고리즘들을 소개한 두 논문 중 두 번째 논문에서는 이들을 유한 상태 기계로 정의된 인코더로 분석한다. (확률적 앙상블이 아닌) 개별 시퀀스에 대해 정보 엔트로피와 유사한 측정값이 개발된다. 이 측정값은 달성할 수 있는 데이터 압축비에 대한 경계를 제공한다. 그런 다음 시퀀스 길이가 무한대로 증가함에 따라 이 경계를 달성하는 모든 시퀀스에 대해 유한 비손실 인코더가 존재함을 보여준다. 이러한 의미에서 이 체계에 기반한 알고리즘은 점근적으로 최적의 인코딩을 생성한다. 이 결과는 피터 쇼어의 노트에서와 같이 더 직접적으로 증명될 수 있다.^[7]

형식적으로는 (정리 13.5.2^[8]).

LZ78은 범용적이고 엔트로피적이다.—${\textstyle X}$가 정지적이고 에르고딕적인 이진 소스라면, $${\displaystyle \limsup _{n}{\frac {1}{n}}l_{LZ78}(X_{1:n})\leq h(X)}$$는 확률 1로 성립한다. 여기서 ${\textstyle h(X)}$는 소스의 엔트로피율이다.

유사한 정리들이 LZ 알고리즘의 다른 버전에도 적용된다.

LZ77

LZ77 알고리즘은 압축되지 않은 데이터 스트림에 이전에 존재하는 단일 데이터 복사본에 대한 참조로 데이터의 반복적인 발생을 대체하여 압축을 달성한다. 일치하는 부분은 길이-거리 쌍이라고 불리는 두 개의 숫자로 인코딩되며, 이는 "다음 길이 문자 각각은 압축되지 않은 스트림에서 정확히 거리만큼 뒤에 있는 문자와 같다"는 진술과 동일하다. (거리는 때때로 오프셋이라고도 불린다.)

일치하는 부분을 찾기 위해 인코더는 가장 최근 데이터의 일부, 예를 들어 지난 2 KB, 4 KB 또는 32 KB를 추적해야 한다. 이 데이터를 담는 구조를 슬라이딩 윈도우라고 부르며, 이 때문에 LZ77을 슬라이딩 윈도우 압축이라고도 한다. 인코더는 일치하는 부분을 찾기 위해 이 데이터를 유지해야 하며, 디코더는 인코더가 참조하는 일치하는 부분을 해석하기 위해 이 데이터를 유지해야 한다. 슬라이딩 윈도우가 클수록 인코더가 참조를 생성하기 위해 더 오래 전으로 검색할 수 있다.

길이-거리 쌍이 실제로 거리보다 긴 길이를 지정하는 것을 허용하는 것은 허용될 뿐만 아니라 자주 유용하다. 복사 명령으로서 이것은 혼란스러울 수 있다: "네 글자 뒤로 돌아가서 그 위치에서 열 글자를 현재 위치로 복사하시오." 단 네 글자만 버퍼에 있는데 어떻게 열 글자를 복사할 수 있는가? 한 번에 한 바이트씩 처리하면 이 요청을 처리하는 데 문제가 없다. 바이트가 복사될 때마다 복사 명령의 입력으로 다시 공급될 수 있기 때문이다. 복사-원본 위치가 초기 대상 위치에 도달하면 결과적으로 복사-원본 위치의 시작 부분에서 붙여넣어진 데이터를 공급받는다. 따라서 이 작업은 "주어진 데이터를 복사하여 맞을 때까지 반복적으로 붙여넣으시오"라는 진술과 동일하다. 이 유형의 쌍은 단일 데이터 복사본을 여러 번 반복하므로 런 렝스 부호화의 유연하고 쉬운 형태를 통합하는 데 사용될 수 있다.

다른 방식으로 보자면 다음과 같다. 인코딩하는 동안 검색 포인터가 검색 윈도우의 끝을 지나서 일치하는 쌍을 계속 찾으려면 오프셋 D에서 첫 번째 일치 항목부터 검색 윈도우 끝까지의 모든 문자가 입력과 일치해야 하며, 이들은 길이 L_R의 단일 실행 단위를 구성하는 (이전에 본) 문자여야 하며, 이는 D와 같아야 한다. 그런 다음 검색 포인터가 검색 윈도우를 지나서 앞으로 진행하면서, 입력에서 실행 패턴이 반복되는 한, 검색 및 입력 포인터는 동기화되어 실행 패턴이 중단될 때까지 문자를 일치시킨다. 그러면 총 L 문자가 일치했고, L > D이며, 코드는 [D, L, c]이다.

[D, L, c]를 디코딩할 때도 마찬가지로 D = L_R이다. 첫 번째 L_R 문자가 출력으로 읽힐 때, 이는 출력 버퍼에 추가된 단일 실행 단위에 해당한다. 이 시점에서 읽기 포인터는 해당 단일 버퍼링된 실행 단위의 시작 부분으로 int(L/L_R) + (L mod L_R ≠ 0일 경우 1)번만 돌아가서 L_R 문자를 읽고(또는 마지막 반환 시 더 적은 수) 총 L 문자가 읽힐 때까지 반복하면 된다고 생각할 수 있다. 그러나 인코딩 프로세스를 반영하여 패턴이 반복적이므로 읽기 포인터는 총 L 문자가 출력으로 복사될 때까지 쓰기 포인터와 실행 길이 L_R과 동일한 고정된 거리만큼 동기화되어 따라가기만 하면 된다.

위의 내용을 고려할 때, 특히 데이터 실행 압축이 지배적일 것으로 예상되는 경우, 윈도우 검색은 윈도우 끝에서 시작하여 뒤로 진행해야 한다. 실행 패턴이 존재한다면 먼저 발견되어 검색을 종료할 수 있기 때문이다. 현재 최대 일치 시퀀스 길이가 충족되면 절대적으로, 또는 충분한 길이가 충족되면 신중하게, 그리고 마지막으로 데이터가 더 최근이고 다음 입력과 더 잘 연관될 가능성이 있다는 단순한 이유 때문에 그렇게 해야 한다.

의사 코드

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

while 입력이 비어 있지 않다면 do
    match := 윈도우에서 시작하는 입력의 가장 긴 반복 일치

    if 일치하는 부분이 존재한다면 then
        d := 일치하는 부분 시작까지의 거리
        l := 일치하는 부분의 길이
        c := 입력에서 일치하는 부분 다음에 오는 문자
    else
        d := 0
        l := 0
        c := 입력의 첫 번째 문자
    end if

    output (d, l, c)

    윈도우 앞에서 l + 1 문자를 버린다.
    s := 입력 앞에서 l + 1 문자를 꺼낸다.
    s를 윈도우 뒤에 추가한다.
repeat

구현

모든 LZ77 알고리즘은 정의상 동일한 기본 원리로 작동하지만, 길이-거리 쌍의 숫자 범위를 변경하고, 길이-거리 쌍에 사용되는 비트 수를 변경하고, 길이-거리 쌍과 리터럴(길이-거리 쌍의 일부가 아닌 자체로 인코딩된 원시 데이터)을 구별하는 방식에 따라 압축된 데이터를 인코딩하는 방식이 크게 달라질 수 있다. 몇 가지 예는 다음과 같다.

• 렘펠과 지브의 1977년 원본 논문에서 설명된 알고리즘은 버퍼에서 찾은 가장 긴 일치 항목의 길이와 거리, 그리고 그 일치 항목 다음에 오는 리터럴 등 세 가지 값을 한 번에 모두 출력한다. 입력 스트림의 두 연속 문자가 리터럴로만 인코딩될 수 있다면, 길이-거리 쌍의 길이는 0이 된다.
• LZSS는 1비트 플래그를 사용하여 다음 데이터 덩어리가 리터럴인지 길이-거리 쌍인지 나타내고, 길이-거리 쌍이 더 길 경우 리터럴을 사용하여 LZ77을 개선한다.
• PalmDoc 형식에서는 길이-거리 쌍이 항상 2바이트 시퀀스로 인코딩된다. 이 두 바이트를 구성하는 16비트 중 11비트는 거리를 인코딩하는 데 사용되고, 3비트는 길이를 인코딩하는 데 사용되며, 나머지 2비트는 디코더가 첫 번째 바이트를 이러한 2바이트 시퀀스의 시작으로 식별할 수 있도록 하는 데 사용된다.
• 일렉트로닉 아츠의 여러 게임에 사용된 구현에서,^[9] 길이-거리 쌍의 바이트 크기는 길이-거리 쌍 자체의 첫 번째 바이트 내에서 지정될 수 있다. 첫 번째 바이트가 0, 10, 110 또는 111로 시작하는지 여부( 빅 엔디언 비트 방향으로 읽을 때)에 따라 전체 길이-거리 쌍의 길이는 1에서 4바이트가 될 수 있다.
• 틀:2008년 기준, 가장 널리 사용되는 LZ77 기반 압축 방식은 DEFLATE이다. 이는 LZSS와 허프먼 부호화를 결합한다.^[10] 리터럴, 길이, 그리고 현재 데이터 블록의 끝을 나타내는 기호는 모두 하나의 알파벳으로 함께 배치된다. 거리는 별도의 알파벳으로 안전하게 배치될 수 있다. 거리는 길이 바로 뒤에만 나타나기 때문에 다른 종류의 기호로 오해되거나 그 반대가 될 수 없다.

LZ78

LZ78 알고리즘은 입력에서 토큰 시퀀스의 사전을 구축한 다음, 데이터 스트림에서 해당 시퀀스의 두 번째 및 이후 발생을 사전 항목에 대한 참조로 대체하여 순차 데이터를 압축한다. 여기서의 관찰은 반복되는 시퀀스의 수가 시퀀스의 무작위적이지 않은 특성을 잘 나타내는 척도라는 것이다. 이 알고리즘은 사전을 n진 트리로 표현하며, 여기서 n은 토큰 시퀀스를 형성하는 데 사용되는 토큰의 수이다. 각 사전 항목은 dictionary[...] = {index, token} 형식으로, 여기서 index는 이전에 본 시퀀스를 나타내는 사전 항목에 대한 색인이고, token은 이 항목을 사전에서 고유하게 만드는 입력의 다음 토큰이다. 알고리즘이 탐욕적이어서 고유한 토큰이 발견될 때까지는 아무것도 테이블에 추가되지 않는다는 점에 유의해야 한다. 알고리즘은 마지막 일치 색인 = 0 및 다음 사용 가능한 색인 = 1로 초기화한 다음, 입력 스트림의 각 토큰에 대해 사전을 검색하여 일치하는 부분을 찾는다: last matching index, token}. 일치하는 부분이 발견되면 마지막 일치 색인이 일치하는 항목의 색인으로 설정되고, 아무것도 출력되지 않으며, 마지막 일치 색인은 지금까지의 입력을 계속 나타낸다. 일치하는 부분이 발견되지 않을 때까지 입력이 처리된다. 그런 다음 새 사전 항목이 생성된다: dictionary[next available index] = {last matching index, token}, 그리고 알고리즘은 마지막 일치 색인과 토큰을 출력한 다음, 마지막 일치 색인을 0으로 재설정하고 다음 사용 가능한 색인을 1 증가시킨다. 예를 들어, AABBA 토큰 시퀀스를 고려하면 다음과 같은 사전이 구성된다.

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

그리고 압축된 데이터의 출력 시퀀스는 0A1B0B가 된다. 마지막 A는 알고리즘이 다음에 무엇이 올지 알 수 없으므로 아직 표현되지 않는다는 점에 유의해야 한다. 실제로는 EOF 마커가 입력에 추가된다. 예를 들어 AABBA$와 같이. 또한 이 경우 출력 0A1B0B1$가 원본 입력보다 길지만, 사전이 커질수록 압축률이 상당히 향상되며, 이진에서는 색인을 최소 비트 수 이상으로 표현할 필요가 없다는 점도 유의해야 한다.^[11]

압축 해제는 압축된 시퀀스에서 사전을 재구성하는 것으로 구성된다. 시퀀스 0A1B0B1$에서 첫 번째 항목은 항상 종결자 0 {...} 이며, 시퀀스에서 첫 번째 항목은 1 {0,A} 가 된다. A는 출력에 추가된다. 입력에서 두 번째 쌍은 1B이며, 사전에서 항목 번호 2, 1,B}를 생성한다. 토큰 "B"가 출력되고, 그 앞에 사전 항목 1이 나타내는 시퀀스가 붙는다. 항목 1은 'A' (그 뒤에 "항목 0" - 아무것도 없음)이므로 AB가 출력에 추가된다. 다음으로 0B는 사전의 다음 항목으로 추가되며, 3 {0,B} 가 되고, B (그 앞에 아무것도 없음)가 출력에 추가된다. 마지막으로 1$에 대한 사전 항목이 생성되고 A$가 출력되어 A AB B A$ 또는 공백과 EOF 마커를 제거한 AABBA가 된다.

LZW

LZW는 모든 가능한 문자(기호) 또는 사전 초기화 에뮬레이션으로 미리 초기화된 사전을 사용하는 LZ78 기반 알고리즘이다. LZW의 주요 개선 사항은 일치하는 항목을 찾을 수 없는 경우 현재 입력 스트림 문자가 사전의 기존 문자열의 첫 번째 문자라고 가정하므로(사전이 모든 가능한 문자로 초기화되었기 때문에) 마지막 일치 색인만 출력된다는 것이다(이것은 이전 (또는 초기) 입력 문자에 해당하는 미리 초기화된 사전 색인일 수 있다). 구현 세부 사항은 LZW 문서를 참조하라.

BTLZ는 실시간 통신 시스템(원래 모뎀)에 사용하기 위해 개발된 LZ78 기반 알고리즘으로, CCITT/ITU에 의해 V.42bis로 표준화되었다. 트라이 구조 사전이 가득 차면, 사전이 변화하는 데이터에 계속 적응할 수 있도록 간단한 재사용/복구 알고리즘이 사용된다. 카운터는 사전을 순환한다. 새 항목이 필요하면 카운터는 리프 노드(종속 노드가 없는 노드)를 찾을 때까지 사전을 순환한다. 이 노드는 삭제되고 공간은 새 항목에 재사용된다. 이는 LRU 또는 LFU보다 구현이 간단하고 동등한 성능을 달성한다.

같이 보기

• 렘펠–지브–스택 (LZS)