La codificación de Levenstein , o codificación de Levenshtein , es un código universal que codifica los enteros no negativos desarrollado por Vladimir Levenshtein . [1] [2]
Codificación
El código de cero es "0"; para codificar un número positivo :
- Inicialice la variable de recuento de pasos C a 1.
- Escriba la representación binaria del número sin el "1" al principio del código.
- Sea M el número de bits escritos en el paso 2.
- Si M no es 0, incremente C , repita desde el paso 2 con M como el nuevo número.
- Escriba los bits C "1" y un "0" al principio del código.
El código comienza:
Número | Codificación | Probabilidad implícita | |
---|---|---|---|
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 | |
dieciséis | 11110 0 00 0000 | 1/4096 | |
17 | 11110 0 00 0001 | 1/4096 |
Para decodificar un entero codificado por Levenstein:
- Cuente el número de bits "1" hasta que se encuentre un "0".
- Si el recuento es cero, el valor es cero; de lo contrario
- Comience con una variable N , establézcala en un valor de 1 y repita el conteo menos 1 veces:
- Leer N bits, anteponer "1", asignar el valor resultante a N
El código de Levenstein de un entero positivo es siempre un poco más largo que el código omega de Elias de ese entero. Sin embargo, hay un código de Levenstein para cero, mientras que la codificación omega de Elias requeriría que los números se desplacen para que un cero sea representado por el código de uno en su lugar.
Código de ejemplo
Codificación
void levenshteinEncode ( char * fuente , char * dest ) { IntReader intreader ( fuente ); BitWriter bitwriter ( dest ); while ( intreader . hasLeft ()) { int num = intreader . getInt (); if ( num == 0 ) bitwriter . outputBit ( 0 ); else { int c = 0 ; Bits BitStack ; hacer { int m = 0 ; for ( int temp = num ; temp > 1 ; temp >> = 1 ) // calcular piso (log2 (num)) ++ m ; para ( int i = 0 ; i < m ; ++ i ) bits . pushBit (( num >> i ) & 1 ); num = m ; ++ c ; } while ( num > 0 ); para ( int i = 0 ; i < c ; ++ i ) bitwriter . outputBit ( 1 ); bitwriter . outputBit ( 0 ); while ( bits . longitud () > 0 ) bitwriter . outputBit ( bits . popBit ()); } } }
Descodificación
void levenshteinDecode ( char * fuente , char * dest ) { BitReader bitreader ( fuente ); IntWriter intwriter ( dest ); while ( lector de bits . hasLeft ()) { int n = 0 ; while ( bitreader . inputBit ()) // potencialmente peligroso con archivos mal formados. ++ n ; int num ; si ( n == 0 ) num = 0 ; else { num = 1 ; para ( int i = 0 ; i < n -1 ; ++ i ) { int val = 1 ; para ( int j = 0 ; j < num ; ++ j ) val = ( val << 1 ) | lector de bits . inputBit (); num = val ; } } escritora . putInt ( num ); // escribe el valor } bitreader . cerrar (); intérprete . cerrar (); }
Ver también
Referencias
- ^ "Documento de 1968 de VI Levenshtein (en ruso)" (PDF) .
- ^ David Salomon (2007). Códigos de longitud variable para la compresión de datos . Saltador. pag. 80. ISBN 978-1-84628-958-3.