동적 마르코프 압축

Dynamic Markov compression

동적 마르코프 압축(DMC)은 Gordon Cormack과 Nigel Horspool에 [1]의해 개발된 무손실 데이터 압축 알고리즘입니다.입력이 (한 번에 1바이트가 아니라) 한 번에 1비트씩 예측된다는 점을 제외하고는 PPM(부분 매칭)에 의한 예측과 유사한 예측 산술 부호화를 사용합니다.DMC는 PPM과 마찬가지로 압축률이 좋고 속도도 보통이지만 메모리를 약간 더 필요로 하기 때문에 널리 구현되어 있지 않습니다.최근 구현된 일부에는 Nania Francesco Antonio의 실험 압축 프로그램, Frank Schinger의 ocamyd 및 Matt Mahoney의 paq8l 하위 모델이 포함됩니다.이것들은 Gordon Cormack의 1993년 C에서의 실장에 근거하고 있습니다.

알고리즘.

DMC는 한 번에 1비트를 예측하고 코드화합니다.이는 바이트가 아닌 비트를 코드화한다는 점에서 PPM과 다르며 예측마다 컨텍스트가1개밖에 없다는 점에서 PAQ 등의 컨텍스트 혼합 알고리즘과는 다릅니다.그런 다음 예측 비트가 산술 부호화를 사용하여 부호화됩니다.

산술 부호화

DMC 등의 비트 연산 부호화기는 프레딕터와 연산 부호화의 2가지 성분을 가진다.예측 변수는 n비트 입력 문자열 x = xx12..를 받아들입니다..xn 및 p(x)p(xx21)p1(xx12)...p(xx312...xn–1)...p(xxn...x)라는 일련의 예측의 곱으로 표현되는 확률 p(x)를 할당합니다.산술 부호화기는 두 개의 고정밀 이진수 p와lowhigh p를 유지하며, 지금까지 본 x의 비트를 고려할 때 모델이 사전 편찬적으로 x보다 작은 모든 문자열에 할당할 수 있는 총 확률의 범위를 나타냅니다.x 의 압축 코드는 p 입니다x.p와 phigh 사이의 숫자를low 나타내는 최단 비트 문자열입니다.이 범위에서는 항상 Shannon 한계(log2 1 / p(x'))보다 긴 1비트 이하의 숫자를 찾을 수 있습니다. p와 다른low 첫 번째 비트 뒤에 있는 모든 후행 비트를 드롭함으로써 p로부터 이러한high 수치를 얻을 수 있다.

압축은 다음과 같이 진행됩니다.초기 범위는 p = 0, phigh = 1로 설정됩니다low.예측 변수는 각 비트에 대해 각각 0 또는 1의 확률인i p = p(x = 012 xx...xi–1) 및1 p = 1 - p를0 추정합니다0.그런 다음 산술 부호화기는 전류 범위(plow, phigh)를 p와1 p에 비례하여0 두 부분으로 나눕니다.다음으로 다음 비트i x에 대응하는 서브 범위가 새로운 범위가 됩니다.

압축 해제의 경우 지금까지 압축 해제된 비트를 고려할 때 예측 변수는 동일한 일련의 예측을 수행합니다.산술 코더는 일련의 동일한 범위 분할을 수행한 다음 p를 포함하는x 범위를 선택하고 해당 하위 범위에 해당하는 비트i x를 출력합니다.

실제로는 메모리에 p와high p를 고정밀로 유지할low 필요가 없습니다.범위가 좁혀짐에 따라 두 숫자의 선행 비트가 동일해지고 즉시 출력할 수 있습니다.

DMC 모델

DMC 프레딕터는 (비트 단위로) 콘텍스트를 카운트 쌍n과01 n에 매핑하는 테이블로, 이 콘텍스트에서 이전에 관찰된0과 1의 수를 나타냅니다.따라서 다음 비트는 확률0 p0 = n / n0 = n / (n01 + n) 및1 확률 p1 = 1 - p0 = n / n의 1이 될 것으로 예측합니다. 또한 각 테이블 항목에는 현재 컨텍스트의 오른쪽에 0 또는 1을 추가하여 얻은 컨텍스트에 대한 포인터 쌍이 있습니다.따라서 테이블에서 현재 콘텍스트를 검색할 필요는 없습니다.현재 콘텍스트에 대한 포인터를 유지하고 링크를 따라가면 충분합니다.

원래의 DMC 실장에서는 첫 번째 테이블은 바이트 경계에서 시작하는 길이8 ~ 15 비트의 모든 컨텍스트의 세트입니다.초기 상태는 8비트콘텍스트 중 하나입니다.카운트는 0.2와 같은 0이 아닌 작은 상수로 초기화된 부동 소수점 숫자입니다.현재 컨텍스트에서 이전에 볼 수 없었던 값이라도 코드화할 수 있도록 카운트는 0으로 초기화되지 않습니다.

압축 및 압축 해제에 대한 모델링은 동일합니다.각 비트에 대해0 p, p를1 연산하고 비트i x를 부호화 또는 복호화하며 x에 대응하는i 카운트에 1을 가산하여 모델을 갱신하고 x에 대응하는i 링크를 경유하여 다음 콘텍스트를 구한다.


새로운 콘텍스트 추가

위에서 설명한 DMC는 order-1 컨텍스트모델에 해당합니다.단, 압축을 개선하기 위해 긴 콘텍스트를 추가하는 것은 일반적입니다.현재 콘텍스트가 A이고 다음 콘텍스트B가 왼쪽에 비트를 드롭하는 경우 DMC는 B에서 새로운 콘텍스트C를 추가할 수 있습니다(클론).C는 B와 함께 오른쪽에 1비트를 추가한 후 A와 같은 콘텍스트를 나타내지만 왼쪽에 비트를 드롭하지 않습니다.따라서 A로부터의 링크는 B에서 C로 이동합니다.B와 C는 모두 같은 예측을 하고 다음 상태의 같은 쌍을 가리킵니다.C의 총 카운트 n = n0 + n은1 A의 카운트x n(입력 비트 x의 경우)과 같으며, 이 카운트는 B에서 차감됩니다.

예를 들어 상태 A가 컨텍스트 11111을 나타낸다고 가정합니다.입력 비트 0에서는, 좌측에 3비트를 떨어뜨려 얻은 콘텍스트 110을 나타내는 상태 B로 이행한다.컨텍스트 A에서는 4개의 제로 비트와 몇 개의 1비트가 있습니다.컨텍스트 B에서는 3개의 0과 7개의 1(n = 10)이 있으며, 이는 p = 0.7을 예측합니다1.

주 n0 n1 다음에0 다음에1
A = 11111 4 B
B = 110 3 7 E F

C는 B에서 복제됩니다.콘텍스트 111110을 나타냅니다.B와 C는 모두 p = 0.7을 예측하고1 둘 다 동일한 다음 상태 E와 F로 이동합니다.C의 카운트는 n = 4이며, A의 경우 n과 같습니다0.그러면 B의 경우 n = 6이 남습니다.

주 n0 n1 다음에0 다음에1
A = 11111 4 C
B = 110 1.8 4.2 E F
C = 111110 1.2 2.8 E F

상태는 상태가 전환되기 직전에 복제됩니다.원래 DMC에서는 A에서B로의 이행이 2 이상, B의 카운트 수가 2 이상일 때(두 번째 임계값이 0보다 클 경우 복제 후에도 다른 상태가 B로 이행하는 것을 보증합니다).훅 등의 일부 구현에서는 이러한 임계값을 파라미터로 설정할 수 있습니다.paq8l에서는, 이러한 문턱치는, 새로운 상태의 증가율을 늦추기 위해서 메모리가 사용되기 때문에 증가합니다.대부분의 구현에서는 메모리가 소진되면 모델이 폐기되고 원래 바이트 단위 순서 1 모델로 다시 초기화됩니다.

레퍼런스

  1. ^ Gordon Cormack과 Nigel Horspool, "Dynamic Markov Modeling을 사용한 데이터 압축", 컴퓨터 저널 30:6(1987년 12월)

외부 링크