codificación de Levenshtein

Codificación universal

La codificación Levenshtein es un código universal que codifica los números enteros no negativos desarrollado por Vladimir Levenshtein . ^{[1] [2]}

Codificación

El código de cero es "0"; para codificar un número positivo :

1. Inicialice la variable de recuento de pasos C en 1.
2. Escribe la representación binaria del número sin el "1" inicial al comienzo del código.
3. Sea M el número de bits escritos en el paso 2.
4. Si M no es 0, incremente C , repita desde el paso 2 con M como nuevo número.
5. Escriba C bits "1" y un "0" al comienzo del código.

El código comienza:

Para decodificar un entero codificado en Levenshtein:

1. Cuente el número de bits "1" hasta encontrar un "0".
2. Si el recuento es cero, el valor es cero; de lo contrario
3. Deseche los bits "1" recién contados y el primer "0" encontrado
4. Comience con una variable N , configúrela en un valor de 1 y repita el conteo menos 1 veces:
5. Lea N bits (y elimínelos del número entero codificado), anteponga "1", asigne el valor resultante a N

El código Levenshtein de un número entero positivo es siempre un bit más largo que el código omega Elias de ese número entero. Sin embargo, existe un código de Levenshtein para cero, mientras que la codificación omega de Elias requeriría que los números se desplazaran para que un cero esté representado por el código de uno.

Código de ejemplo

Codificación

void levenshteinEncode ( char * fuente , char * destino ) { IntReader intreader ( fuente ); BitWriter bitwriter ( destino ); mientras ( intreader . hasLeft ()) { int num = intreader . obtenerInt (); si ( num == 0 ) bitwriter . bit de salida ( 0 ); de lo contrario { int c = 0 ; Bits de pila de bits ; 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 (( número >> i ) & 1 ); número = m ; ++ c ; } mientras ( número > 0 ); para ( int i = 0 ; i < c ; ++ i ) bitwriter . bit de salida ( 1 ); escritor de bits . bit de salida ( 0 ); mientras ( bits . longitud () > 0 ) bitwriter . salidaBit ( bits . popBit ()); } } }                                                                                  

Descodificación

void levenshteinDecode ( char * fuente , char * destino ) { BitReader bitreader ( fuente ); IntWriter intwriter ( destino ); mientras ( bitreader . hasLeft ()) { int n = 0 ; while ( bitreader . inputBit ()) // potencialmente peligroso con archivos con formato incorrecto. ++ norte ; número int ; si ( n == 0 ) número = 0 ; más { número = 1 ; for ( int i = 0 ; i < n -1 ; ++ i ) { int val = 1 ; para ( int j = 0 ; j < núm ; ++ j ) val = ( val << 1 ) | lector de bits . bit de entrada (); número = valor ; } } escritor interno . putInt ( núm ); // escribe el valor } bitreader . cerca (); escritor interno . cerca (); }                                                                         

Ver también

• Codificación omega de Elías
• Logaritmo iterado

Referencias

1. "Artículo de 1968 de VI Levenshtein (en ruso)" (PDF) .
2. David Salomón (2007). Códigos de longitud variable para compresión de datos. Saltador. pag. 80.ISBN​ 978-1-84628-958-3.