Codigo levenstein
El código Levenshtein es un código universal que le permite codificar números enteros no negativos . Fue acuñado por Vladimir Levenshtein .
El código cero es "0"; para codificar un número positivo, se utiliza el siguiente algoritmo:
- Inicialice el contador de pasos C = 1, K es el código del número (inicialmente vacío).
- Escriba el código binario del número codificado sin el 1 "más alto" (por ejemplo, escriba el número 1100 como 100; el número 100 como 00).
- Agregue recibido al principio K .
- Sea M el número de bits escritos en el segundo paso. Convertir M a binario.
- Si M no está vacío, entonces C = C + 1, y repita el algoritmo desde el paso 2 para la M resultante . De lo contrario, vaya al paso 6.
- Escriba C piezas de unidades y 0 al comienzo del código K (por ejemplo, si el contador C \u003d 2, K \u003d 0 011, obtenga: 110 0 011), el código Levenshtein.
El código de Levenshtein para los primeros 24 números se vería así:
0 0
1 10
2 110 0
3 110 1
4 1110 0 00
5 1110 0 01
6 1110 0 10
7 1110 0 11
8 1110 1000
9 1110 1001
10 1110 1 010
11 1110 1 011
12 1110 1 100
13 1110 1 101
14 1110 1 110
15 1110 1 111
16 11110 0 00 0000
17 11110 0 00 0001
18 11110 0 00 0010
19 11110 0 00 0011
20 11110 0 00 0100
21 11110 0 00 0101
22 11110 0 00 0110
23 11110 0 00 0111
24 11110 0 00 1000
Sea K un código de Levenshtein. Para descifrar el código Levenshtein, debe:
- Cuente el número desde 1 bit hasta el primer bit cero.
- Si C = 0, entonces el valor codificado es 0 . Si no, vaya al paso 3.
- Descartar de K estas unidades de C y los 0 siguientes . Escriba el nuevo valor de K.
- Configure la variable N = 1. Ingrese el contador de pasos P = C - 1.
- Si P = 0, entonces N es el número deseado. Si no, vaya al paso 6.
- Lea los primeros N bits de K. Escriba un nuevo valor en K sin leer N bits.
- Agregue 1 al comienzo del registro leído (por ejemplo, leído 00, recibido: 100).
- Convierta el valor recibido al sistema decimal (o el original, si se conoce) - el nuevo valor de la variable N .
- P = P - 1. Repita desde el paso 5.
En la codificación Levenshtein, un número positivo siempre es 1 bit más que en la codificación omega Elias . Sin embargo, el código Levenshtein puede codificar el cero, mientras que con la codificación omega de Elias es necesario redesignar todos los dígitos de tal manera que el cero se represente con uno.
Enlaces
Fuente