범위 부호화
Range coding범위 부호화(또는 범위 부호화)는 1979년 [1]G. Nigel N. Martin에 의해 정의된 엔트로피 부호화 방법으로 [2]1976년 리처드 클라크 파스코에 의해 처음 도입된 FIFO 산술 코드를 효과적으로 재발견했습니다.심볼의 스트림과 그 확률이 주어지면 레인지 코더는 이들 심볼을 나타내는 공간 효율적인 비트스트림을 생성하고 스트림과 확률에 따라 레인지 디코더는 프로세스를 반전시킨다.
범위 부호화는 비트가 아닌 임의의 베이스의 디지트로 이루어지기 때문에 압축 [3]효율에서 적은 비용으로 더 큰 베이스(예: 바이트)를 사용할 때 더 빠르다는 점을 제외하면 산술 부호화와 매우 유사합니다.제1회(1978)[4] 산술 부호화 특허가 만료된 후 범위 부호화는 특허 침해로부터 확실히 자유로워 보였다.이것은 특히 오픈 소스 커뮤니티에서 기술에 대한 관심을 불러일으켰다.그 이후로, 잘 알려진 다양한 산술 부호화 기술에 대한 특허도 만료되었다.
범위 코딩의 구조
각 심볼에 비트 패턴을 할당하고 모든 비트 패턴을 연결하는 허프만 코딩과는 달리 범위 코딩은 개념적으로 메시지의 모든 심볼을 하나의 번호로 인코딩합니다.따라서 범위 코딩은 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바이트씩 재규격화를 실행하는 경향입니다.즉, 범위 인코더는 바이트를 비트가 아닌 코딩 디짓으로 사용하는 경향이 있습니다.이렇게 하면 매우 적은 양으로도 달성할 수 있는 압축량이 줄어들지만 각 비트에 대해 재규격화를 수행할 때보다 속도가 빨라집니다.
「 」를 참조해 주세요.
레퍼런스
- ^ a b G. Nigel N. Martin, 범위 부호화: 1979년 7월 24~27일 영국 Southampton, Video & Data Recording Conference 디지털 메시지에서 용장성을 제거하기 위한 알고리즘.
- ^ "빠른 데이터 압축을 위한 소스 코딩 알고리즘" Richard Clark Pasco, Stanford, CA 1976
- ^ "레인지 코더의 오버헤드", 티모시 B.Terriberry, 테크니컬 노트 2008
- ^ 미국 특허 4,122,440 - (IBM) 1977년 3월 4일 출원, 1978년 10월 24일 부여(현재 만료)