엘리아스 오메가 부호화
Elias omega coding엘리아스 Ω 부호화 또는 엘리아스 오메가 부호화는 피터 엘리아스가 개발한 양의 정수를 부호화하는 유니버설 코드다.엘리아스 감마 코딩이나 엘리아스 델타 코딩처럼, 범용 코드로 그 크기의 순서를 나타내는 정수에 접두사를 붙이는 방식으로 작용한다.그러나 다른 두 코드와는 달리 엘리아스 오메가는 그 접두사를 재귀적으로 부호화하므로, 그것들은 때때로 재귀 엘리아스 코드로 알려져 있다.
오메가 코딩은 가장 큰 인코딩 값을 미리 알 수 없는 어플리케이션이나, 작은 값이 큰 값보다 훨씬 빈번한 데이터를 압축하는 데 사용된다.
숫자 N을 코드화하려면:
- 코드 끝에 "0"을 놓으십시오.
- N = 1이면 중지, 인코딩 완료.
- N의 이진 표현을 코드의 시작 부분까지 앞지르십시오.이것은 적어도 두 개의 비트가 될 것이며, 그 중 첫 번째 비트는 1이다.
- N은 방금 앞에 있는 비트 수에서 1을 뺀 값과 같게 한다.
- 새 N의 인코딩을 완료하려면 2단계로 돌아가십시오.
Elias 오메가 코드 정수를 디코딩하려면:
- 변수 N으로 시작하여 값 1로 설정하십시오.
- 다음 비트가 "0"이면 중지하십시오.디코딩된 숫자는 N이다.
- 다음 비트가 "1"인 경우 해당 비트에 N비트를 더하여 읽고, 해당 이진수를 N의 새 값으로 사용하십시오. 2단계로 돌아가십시오.
예
오메가 코드는 다수의 "그룹"으로 생각할 수 있다.그룹은 코드를 종료하는 단일 0 비트 또는 1로 시작하는 두 개 이상의 비트 중 하나이며, 그 다음에 다른 그룹이 나타난다.
처음 몇 개의 코드는 아래와 같다.이 코딩이 최소 크기 코드를 산출하는 값의 분포를 설명하는 소위 암묵적 분포가 포함되어 있다. 자세한 내용은 범용 코드와 실제 압축의 관계를 참조하십시오.
| 가치 | 코드 | 잠재 확률 |
|---|---|---|
| 1 | 0 | 1/2 |
| 2 | 10 0 | 1/8 |
| 3 | 11 0 | 1/8 |
| 4 | 10 100 0 | 1/64 |
| 5 | 10 101 0 | 1/64 |
| 6 | 10 110 0 | 1/64 |
| 7 | 10 111 0 | 1/64 |
| 8 | 11 1000 0 | 1/128 |
| 9 | 11 1001 0 | 1/128 |
| 10 | 11 1010 0 | 1/128 |
| 11 | 11 1011 0 | 1/128 |
| 12 | 11 1100 0 | 1/128 |
| 13 | 11 1101 0 | 1/128 |
| 14 | 11 1110 0 | 1/128 |
| 15 | 11 1111 0 | 1/128 |
| 16 | 10 100 10000 0 | 1/2048 |
| 17 | 10 100 10001 0 | 1/2048 |
| ... | ||
| 100 | 10 110 1100100 0 | 1/8192 |
| 1000 | 11 1001 1111101000 0 | 1/131,072 |
| 10,000 | 11 1101 10011100010000 0 | 1/2,097,152 |
| 100,000 | 10 100 10000 11000011010100000 0 | 1/268,435,456 |
| 1,000,000 | 10 100 10011 11110100001001000000 0 | 1/2,147,483,648 |
1구골, 10100의 인코딩은 111000101001100(길이 헤더의 15비트)를333-bit을 이진 배열로 마샬링 하기 전 1구골은 10010 01001001 10101101 00100101 10010100 11000011 01111100 11101011 00001011 00100111 10000100 11000100 11001110 00001011 11110011 10001010 11001110 01000000 10001110 00100001 00011010 01111100 10101.01010110010 01000011 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000, 후행 0을 총 349비트.
100번째 전력(1010000)에 이르는 구골은 33220비트 이진수다.오메가 인코딩은 길이 33,243비트: 11 1111 1000000111000100(22비트)이며, 그 다음은 값 33,220비트, 후행 0이다.Elias 델타 부호화에서 동일한 숫자는 33,250비트 길이: 0000000000000 1000000111000100(31비트)에 이어 값 33,219비트가 된다.로그2(1010000) = 33219.28이므로 이 경우 오메가 코딩과 델타 코딩은 각각 최적보다 0.07%, 0.09% 길기만 하다.
예시 코드
인코딩
공허하게 하다 엘리아스오메가엔코드(마를 뜨다* 출처, 마를 뜨다* 증류) { 인트리더 내독자(출처); 비트라이터 비트라이터(증류); 하는 동안에 (내독자.hasleft()) { 인트로 숫자 = 내독자.getInt(); 비트스택 조각들; 하는 동안에 (숫자 > 1) { 인트로 렌 = 0; 을 위해 (인트로 임시 변통하다 = 숫자; 임시 변통하다 > 0; 임시 변통하다 >>= 1) // 1+바닥(log2(숫자) 계산 렌++; 을 위해 (인트로 i = 0; i < 렌; i++) 조각들.푸시비트((숫자 >> i) & 1); 숫자 = 렌 - 1; } 하는 동안에 (조각들.길이() > 0) 비트라이터.퍼트비트(조각들.팝비트()); 비트라이터.퍼트비트(거짓의); // 1 0을 쓴다. } 비트라이터.가까운.(); 내독자.가까운.(); } 디코딩
공허하게 하다 엘리아스오메가데코드(마를 뜨다* 출처, 마를 뜨다* 증류) { 비트리더 비트레더(출처); 인트라이터 인트라이터(증류); 하는 동안에 (비트레더.hasleft()) { 인트로 숫자 = 1; 하는 동안에 (비트레더.입력비트()) // 잘못된 형식의 파일로 인해 잠재적으로 위험할 수 있음. { 인트로 렌 = 숫자; 숫자 = 1; 을 위해 (인트로 i = 0; i < 렌; ++i) { 숫자 <<= 1; 만일 (비트레더.입력비트()) 숫자 = 1; } } 인트라이터.퍼팅(숫자); // 값을 기입한다. } 비트레더.가까운.(); 인트라이터.가까운.(); } 일반화
엘리아스 오메가 코딩은 0이나 음의 정수를 코드화하지 않는다.모든 비 음의 정수를 코딩하는 한 가지 방법은 코딩하기 전에 1을 더하고 디코딩 후 1을 빼는 것이다.모든 정수를 코드화하는 한 가지 방법은 코딩하기 전에 모든 정수(0, 1, 1, -1, 2, 2, -2, 3, -3, ...)를 엄격히 양의 정수(1, 2, 3, 4, 5, 6, 7, ...)에 매핑하는 편차를 설정하는 것이다.
참고 항목
참조
추가 읽기
- Elias, Peter (March 1975). "Universal codeword sets and representations of the integers". IEEE Transactions on Information Theory. 21 (2): 194–203. doi:10.1109/tit.1975.1055349.
- Fenwick, Peter (2003). "Universal Codes". In Sayood, Khalid (ed.). Lossless Compression Handbook. New York, NY, USA: Academic Press. pp. 55–78. doi:10.1016/B978-012620861-0/50004-8. ISBN 978-0123907547.
