범위 부호화

Range coding

범위 부호화(또는 범위 부호화)는 1979년 [1]G. Nigel N. Martin에 의해 정의된 엔트로피 부호화 방법으로 [2]1976년 리처드 클라크 파스코에 의해 처음 도입된 FIFO 산술 코드를 효과적으로 재발견했습니다.심볼의 스트림과 그 확률이 주어지면 레인지 코더는 이들 심볼을 나타내는 공간 효율적인 비트스트림을 생성하고 스트림과 확률에 따라 레인지 디코더는 프로세스를 반전시킨다.

범위 부호화는 비트가 아닌 임의의 베이스의 디지트로 이루어지기 때문에 압축 [3]효율에서 적은 비용으로 더 큰 베이스(: 바이트)를 사용할 때 더 빠르다는 점을 제외하면 산술 부호화와 매우 유사합니다.제1회(1978)[4] 산술 부호화 특허가 만료된 후 범위 부호화는 특허 침해로부터 확실히 자유로워 보였다.이것은 특히 오픈 소스 커뮤니티에서 기술에 대한 관심을 불러일으켰다.그 이후로, 잘 알려진 다양한 산술 부호화 기술에 대한 특허도 만료되었다.

범위 코딩의 구조

코딩 프로세스를 그래픽으로 표현한 것입니다.여기서 인코딩되는 메시지는 "AABA <EOM>"입니다.

각 심볼에 비트 패턴을 할당하고 모든 비트 패턴을 연결하는 허프만 코딩과는 달리 범위 코딩은 개념적으로 메시지의 모든 심볼을 하나의 번호로 인코딩합니다.따라서 범위 코딩은 Huffman 코딩의 심볼당 1비트 하한보다 더 큰 압축비를 달성할 수 있으며 Huffman이 2의 정확한 거듭제곱이 아닌 확률을 처리할 때 발생하는 비효율성을 겪지 않습니다.

범위 코딩의 배후에 있는 중심 개념은 다음과 같다. 넓은 범위의 정수 및 기호에 대한 확률 추정이 주어지면 초기 범위는 기호가 나타내는 확률에 비례하는 크기를 가진 하위 범위로 쉽게 나눌 수 있다.그 후, 메시지의 각 심볼은, 현재의 범위를 다음에 부호화할 심볼에 대응하는 서브 레인지만으로 축소하는 것으로 차례차례 부호화할 수 있다.디코더는 인코더가 사용하는 확률과 동일한 추정치를 가져야 합니다.이 추정치는 이미 전송된 데이터에서 도출되거나 압축기와 압축 해제기의 일부가 될 수 있습니다.

모든 심볼이 부호화되어 있는 경우, 서브 범위를 식별하는 것만으로 메시지 전체를 통신할 수 있습니다(물론 디코더가 메시지 전체를 추출했을 때 어떤 식으로든 통지되는 것으로 가정합니다).서브레인지 식별에는 1개의 정수만으로 충분하며, 정수 전체를 송신할 필요도 없습니다.그 프리픽스로 시작하는 모든 정수가 서브레인지 내에 들어가는 일련의 디짓이 있는 경우, 서브레인지 식별에 프리픽스만으로 충분하고, 그 결과 메시지가 송신됩니다.

메시지 "AABA <EOM>"를 부호화한다고 가정합니다.< EOM >는 메시지 종료 기호입니다.이 예에서는 디코더가 확률 분포 {A: .60; B: .20; <EOM>: .20}을 사용하여 기본 10 번호 시스템에서 정확히 5개의 기호를 부호화하려는 것을 알고 있다고 가정합니다(범위가 [0, 100000]인 10개의 다른 기호 조합을 허용5).인코더는 [0, 100000] 범위를 다음 3개의 서브 범위로 나눕니다.

A: [0, 60000] B: [60000, 80000] <EOM>: [80000, 100000]

첫 번째 기호는 A이므로 초기 범위가 [0, 60000]으로 줄어듭니다.두 번째 기호를 선택하면 이 범위의 하위 범위가 3개 남습니다.이미 인코딩된 'A' 뒤에 표시됩니다.

AA: [0, 36000] AB: [36000, 48000]A<EOM > [ 48000 、 60000 ]

두 개의 기호를 인코딩하면 범위가 [0, 36000]이고 세 번째 기호는 다음과 같은 선택 항목으로 이어집니다.

AAA: [0, 21600] AAB: [21600, 28800] AA <EOM > [ 28800 、 36000 ]

이번에는 부호화하는 메시지를 나타내는3가지 선택지 중 두 번째 선택지가 되어 범위가 [21600, 28800]가 됩니다.이 경우 서브범위를 판별하는 것은 어려워 보이지만 실제로는 그렇지 않습니다.이 경우 상한에서 하한을 빼면 범위 내에 7200개의 숫자가 있다고 판단할 수 있습니다.이 중 첫 번째 4320은 총수의 0.60, 다음 1440은 총수의 0.20, 나머지 1440은 나머지 0.20o를 나타냅니다.f합계하한 값을 다시 추가하면 범위가 제공됩니다.

AABA: [21600, 25920] AABB: [25920, 27360] AAB <EOM>: [27360, 28800]

마지막으로 범위가 [21600, 25920]로 좁혀져 부호화할 기호는 1개뿐입니다.하한과 상한 사이의 범위를 분할하기 위해 이전과 동일한 기법을 사용하여 다음과 같은 세 가지 하위 범위를 찾습니다.

AABAA: [21600, 24192) AABAB: [24192, 25056) AABA <EOM> [25056, 25920]

그리고 <EOM>이 마지막 기호이므로 최종 범위는 [25056, 25920]입니다.「251」로 시작하는 5 자리수의 정수는 모두 최종 범위내에 있기 때문에, 송신할 수 있는3 자리수의 프리픽스 중 하나로, 원래의 메시지를 명확하게 전달할 수 있습니다.(이러한 프레픽스가 실제로는 모두 8개라는 것은 아직 비효율적이라는 것을 의미합니다.Base 2아닌 Base 10을 사용함으로써 도입되었습니다.)

가장 중요한 문제는 부호화해야 하는 기호의 수에 관계없이 항상 0이 아닌 서브 레인지로 분할할 수 있을 만큼 큰 전류 범위를 선택할 수 있다는 것입니다.그러나 실제로는 문제가 되지 않습니다.인코더는 큰 범위에서 시작하여 점차 좁혀지는 것이 아니라 항상 적은 범위의 수치로 동작하기 때문입니다.몇 자리수의 숫자가 부호화되면 맨 왼쪽 자리는 변경되지 않습니다.이 예에서는 3개의 기호만 코딩한 후 최종 결과가 "2"로 시작된다는 것을 이미 알고 있었습니다.왼쪽의 숫자가 전송됨에 따라 더 많은 숫자가 오른쪽으로 이동됩니다.이것은 다음 코드에 나타나 있습니다.

인트 낮다 = 0; 인트 범위 = 100000;  무효 달려.() {  부호화(0, 6, 10); // A  부호화(0, 6, 10); // A  부호화(6, 2, 10); // B  부호화(0, 6, 10); // A  부호화(8, 2, 10); // <EOM>   // 마지막 자릿수를 내보내다 - 아래 참조  하는 동안에 (범위 < > 10000)   송신 번호();   낮다 += 10000;  송신 번호(); }  무효 송신 번호() {  콘솔.기입하다(낮다 / 10000);  낮다 = (낮다 % 10000) * 10;  범위 *= 10; }  무효 부호화(인트 개시하다, 인트 크기, 인트 ) {  // 기호 간격에 따라 범위 조정  범위 /= ;  낮다 += 개시하다 * 범위;  범위 *= 크기;   // 왼쪽 끝 자릿수가 전체 범위에서 동일한지 확인합니다.  하는 동안에 (낮다 / 10000 == (낮다 + 범위) / 10000)   송신 번호();   // 범위 재조정 - 아래에 있는 이유를 참조하십시오.  한다면 (범위 < > 1000)  {   송신 번호();   송신 번호();   범위 = 100000 - 낮다;  } } 

마무리를 위해 몇 자리 숫자를 더 내보내야 할 수도 있습니다.의 첫 번째 자리low아마 너무 작기 때문에 늘려야 할 것 같습니다만, 너무 작게 해서 늘리지 않도록 해야 합니다.low+range그래서 먼저 우리가 확실히 할 필요가 있다.range충분히 큽니다.

// 마지막 자릿수를 내보냅니다. 하는 동안에 (범위 < > 10000)  송신 번호();  낮다 += 10000; 송신 번호(); 

에서 발생할 수 있는1가지 문제Encode위의 함수는 이다range아주 작아질 수도 있지만low그리고.low+range에는 아직 다른 첫 번째 숫자가 있습니다.이로 인해 간격의 정밀도가 알파벳의 모든 기호를 구별할 수 없게 될 수 있습니다.이 경우는, 조금 조작해, 1 자리 어긋나더라도, 처음의 몇 자리수를 출력해, 가능한 한 빈 공간을 확보할 수 있도록 범위를 재조정할 필요가 있습니다.디코더는, 동기 상태를 유지하기 위해서, 같은 순서를 실행하고 있기 때문에, 이것을 실시할 필요가 있는 타이밍을 알 수 있습니다.

// 이것은 위의 Encode()의 종료 직전에 행해집니다. 한다면 (범위 < > 1000) {  송신 번호();  송신 번호();  범위 = 100000 - 낮다; } 

이 예에서는 Base 10이 사용되었지만 실제 구현에서는 네이티브 정수 데이터 유형의 전체 범위를 가진 바이너리만 사용합니다.대신10000그리고.1000다음과 같은 16진수 상수를 사용할 수 있습니다.0x1000000그리고.0x10000. 한 번에 숫자를 내보내는 대신 한 번에 한 바이트를 내보내고 10을 곱하는 대신 바이트 시프트 연산을 사용합니다.

디코딩에서는 전류 추적과 동일한 알고리즘을 사용합니다.code압축기에서 읽은 자릿수로 구성된 값입니다.맨 윗자리를 내보내는 대신low그냥 버리면 되는 건데, 맨 위 자리 숫자도 바꿔서code컴프레서에서 새 숫자를 읽습니다.사용하다AppendDigit대신 아래쪽에EmitDigit.

인트 코드 = 0; 인트 낮다 = 0; 인트 범위 = 1;  무효 InitializeDecoder(디코더 초기화)() {         추가 번호();  // 이 예제 코드에서는 이들 중1개만 실제로 필요합니다.         추가 번호();         추가 번호();         추가 번호();         추가 번호(); }  무효 추가 번호() {  코드 = (코드 % 10000) * 10 + 다음 번호 읽기();  낮다 = (낮다 % 10000) * 10;  범위 *= 10; }  무효 디코드(인트 개시하다, 인트 크기, 인트 )  // 디코드는 ExmitDigit로 인코딩하고 AppendDigit로 바꿉니다. {  // 기호 간격에 따라 범위 조정  범위 /= ;  낮다 += 개시하다 * 범위;  범위 *= 크기;   // 왼쪽 끝 자릿수가 전체 범위에서 동일한지 확인합니다.  하는 동안에 (낮다 / 10000 == (낮다 + 범위) / 10000)   추가 번호();   // 범위 재조정 - 아래에 있는 이유를 참조하십시오.  한다면 (범위 < > 1000)  {   추가 번호();   추가 번호();   범위 = 100000 - 낮다;  } } 

적용할 확률 간격을 결정하기 위해 디코더는 현재 값을 조사할 필요가 있습니다.code[low, low+range] 간격 내에서 이것이 나타내는 기호를 결정합니다.

무효 달려.() {  인트 개시하다 = 0;  인트 크기;  인트  = 10;  InitializeDecoder(디코더 초기화)();          // 범위/합계>0을 취득해야 합니다.  하는 동안에 (개시하다 < > 8)             // EOM 수신 시 정지  {   인트 v = 가치의 취득();  // 코드는 어떤 기호 범위에 있습니까?   전환하다 (v)                // 값을 기호로 변환   {    사례. 0:    사례. 1:    사례. 2:    사례. 3:    사례. 4:    사례. 5: 개시하다=0; 크기=6; 콘솔.기입하다("A"); 브레이크.;    사례. 6:    사례. 7: 개시하다=6; 크기=2; 콘솔.기입하다('B'); 브레이크.;    체납: 개시하다=8; 크기=2; 콘솔.기입선("");   }   디코드(개시하다, 크기, );  } }  인트 가치의 취득(인트 ) {  돌아가다 (코드 - 낮다) / (범위 / ); } 

AABA의 경우 <위의 예에서는 0 ~9 의 값이 반환됩니다.값 0 ~ 5는 A, 6, 7은 B, 8과 9는 <EOM>을 나타냅니다.

산술 부호화와의 관계

산술 부호화는 범위 부호화와 동일하지만 정수를 분수의 분자로 사용합니다.이러한 분수는 모든 분수가 [0,1] 범위에 속하도록 암묵적이고 공통적인 분모를 가진다.따라서 결과 연산 코드는 암묵적인 "0"으로 시작하는 것으로 해석된다.이것들은 단지 같은 부호화 방법에 대한 다른 해석일 뿐이며, 결과적인 산술 코드와 레인지 코드가 동일하기 때문에, 각 산술 코더는 대응하는 레인지 인코더이며, 그 반대의 경우도 마찬가지입니다.즉, 산술 부호화와 범위 부호화는 같은 것을 이해하기 위한 두 가지, 약간 다른 방법입니다.

그러나 실제로는 소위 범위 [1]인코더가 마틴의 논문에서 설명한 대로 구현되는 경향이 있는 반면, 산술적인 코더는 일반적으로 범위 인코더라고 불리지 않는 경향이 있습니다.이러한 범위 인코더에서 자주 볼 수 있는 기능은 (통상 그렇듯이) 한 번에 1비트가 아니라 1바이트씩 재규격화를 실행하는 경향입니다.즉, 범위 인코더는 바이트를 비트가 아닌 코딩 디짓으로 사용하는 경향이 있습니다.이렇게 하면 매우 적은 양으로도 달성할 수 있는 압축량이 줄어들지만 각 비트에 대해 재규격화를 수행할 때보다 속도가 빨라집니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ a b G. Nigel N. Martin, 범위 부호화: 1979년 7월 24~27일 영국 Southampton, Video & Data Recording Conference 디지털 메시지에서 용장성을 제거하기 위한 알고리즘.
  2. ^ "빠른 데이터 압축을 위한 소스 코딩 알고리즘" Richard Clark Pasco, Stanford, CA 1976
  3. ^ "레인지 코더의 오버헤드", 티모시 B.Terriberry, 테크니컬 노트 2008
  4. ^ 미국 특허 4,122,440 - (IBM) 1977년 3월 4일 출원, 1978년 10월 24일 부여(현재 만료)

외부 링크