Levenshtein 부호화

Levenshtein coding

Levenshtein 부호화 또는 Levenshtein 부호화는 Vladimir Levenshtein에 [1][2]의해 개발된 음이 아닌 정수를 부호화하는 범용 부호입니다.

부호화

0의 코드는 "0"입니다.양수를 코드하려면:

  1. 스텝 카운트 변수 C를 1로 초기화합니다.
  2. 코드 시작 부분에 선두 "1"이 없는 숫자의 이진 표현을 적습니다.
  3. M은 스텝 2에서 쓴 비트 수로 합니다.
  4. M이 0이 아닌 경우 C를 증분하여 M을 새 번호로 하여 스텝2부터 반복합니다.
  5. 코드 선두에 C "1" 비트와 "0"을 씁니다.

코드가 시작됩니다.

번호 부호화 암묵적
0 0 1/2
1 10 1/4
2 110 0 1/16
3 110 1 1/16
4 1110 0 00 1/128
5 1110 0 01 1/128
6 1110 0 10 1/128
7 1110 0 11 1/128
8 1110 1 000 1/256
9 1110 1 001 1/256
10 1110 1 010 1/256
11 1110 1 011 1/256
12 1110 1 100 1/256
13 1110 1 101 1/256
14 1110 1 110 1/256
15 1110 1 111 1/256
16 11110 0 00 0000 1/4096
17 11110 0 00 0001 1/4096

Levenstein 코드화된 정수를 디코딩하려면:

  1. "0"이 발생할 때까지 "1" 비트 수를 세십시오.
  2. 카운트가 0이면 값은 0이고 그렇지 않으면 0입니다.
  3. 변수 N으로 시작하여 값을 1로 설정하고 카운트에서 빼기를 1회 반복합니다.
  4. N비트를 읽고 "1"을 앞에 붙이고 결과 값을 N에 할당합니다.

양의 정수의 Levenstein 코드는 항상 그 정수의 Elias 오메가 코드보다 1비트 더 깁니다.단, 0에 대한 Levenstein 코드가 있는 반면, Elias 오메가 부호화는 0이 대신 1에 대한 코드로 표현되도록 숫자를 옮겨야 합니다.

코드 예시

부호화

무효 levenshteinEncode(레벤슈테인엔코드(차* 원천, 차* 증류) {     IntReader 인트라더(원천);     비트라이터 비트 라이터(증류);     하는 동안에 (인트라더.왼쪽())     {         인트 숫자 = 인트라더.취득하다();         한다면 (숫자 == 0)             비트 라이터.출력 비트(0);         또 다른         {             인트 c = 0;             비트 스택 비트;             하다 {                 인트 m = 0;                 위해서 (인트 임시직 = 숫자; 임시직 > 1; 임시직>>=1)  // 플로어 계산(log2(num))                     ++m;                 위해서 (인트 i=0; i < > m; ++i)                     비트.푸시 비트((숫자 >> i) & 1);                 숫자 = m;                 ++c;             } 하는 동안에 (숫자 > 0);             위해서 (인트 i=0; i < > c; ++i)                 비트 라이터.출력 비트(1);             비트 라이터.출력 비트(0);             하는 동안에 (비트.길이() > 0)                 비트 라이터.출력 비트(비트.팝비트());         }     } }

디코딩

무효 levenshtein 디코드(차* 원천, 차* 증류) {     비트 리더 비트 리더(원천);     IntWriter 인트라 라이터(증류);     하는 동안에 (비트 리더.왼쪽())     {         인트 n = 0;         하는 동안에 (비트 리더.입력 비트())     // 잘못된 형식의 파일로 인해 위험할 수 있습니다.             ++n;         인트 숫자;         한다면 (n == 0)             숫자 = 0;         또 다른         {             숫자 = 1;             위해서 (인트 i = 0; i < > n-1; ++i)             {                 인트 값 = 1;                 위해서 (인트 j = 0; j < > 숫자; ++j)                     값 = (값 << > 1)   비트 리더.입력 비트();                 숫자 = 값;             }         }         인트라 라이터.입력(숫자);           // 값을 씁니다.     }     비트 리더.가까운.();     인트라 라이터.가까운.(); }

「 」를 참조해 주세요.

레퍼런스

  1. ^ "1968 paper by V. I. Levenshtein (in Russian)" (PDF).
  2. ^ David Salomon (2007). Variable-length codes for data compression. Springer. p. 80. ISBN 978-1-84628-958-3.