Levenshtein kódování - Levenshtein coding

Levensteinovo kódovánínebo Levenshtein kódování, je univerzální kód kódování nezáporných celých čísel vyvinutých Vladimir Levenshtein.^[1]^[2]

Kódování

Kód nula je „0“; kódovat a kladné číslo:

Inicializujte proměnnou počet kroků C až 1.
Napsat binární reprezentace čísla bez úvodní „1“ na začátek kódu.
Nechat M být počet bitů zapsaných v kroku 2.
Li M není 0, přírůstek C, opakujte od kroku 2 s M jako novým číslem.
Psát si C "1" bity a "0" na začátek kódu.

Kód začíná:

Číslo	Kódování	Implikovaná pravděpodobnost
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

Dekódování levensteinského kódu:

Počítejte počet bitů „1“, dokud nenarazíte na „0“.
Pokud je počet nula, hodnota je nula, jinak
Začněte s proměnnou N, nastavte jej na hodnotu 1 a opakujte počet minus 1 časy:
Číst N bity, předložit „1“, přiřadit výslednou hodnotu N

Levensteinův kód kladného celého čísla je vždy o kousek delší než Elias omega kód toho celého čísla. Existuje však Levensteinův kód pro nulu, zatímco kódování Elias omega by vyžadovalo posunutí čísel tak, aby nulu místo toho představoval kód pro jednu.

Příklad kódu

Kódování

prázdnota levenshteinEncode(char* zdroj, char* dest){    IntReader intreader(zdroj);    BitWriter bitwriter(dest);    zatímco (intreader.opustil())    {        int počet = intreader.dostat();        -li (počet == 0)            bitwriter.outputBit(0);        jiný        {            int C = 0;            BitStack bity;            dělat {                int m = 0;                pro (int tepl = počet; tepl > 1; tepl>>=1)  // výpočet minima (log2 (num))                    ++m;                pro (int i=0; i < m; ++i)                    bity.pushBit((počet >> i) & 1);                počet = m;                ++C;            } zatímco (počet > 0);            pro (int i=0; i < C; ++i)                bitwriter.outputBit(1);            bitwriter.outputBit(0);            zatímco (bity.délka() > 0)                bitwriter.outputBit(bity.popBit());        }    }}

Dekódování

prázdnota levenshteinDecode(char* zdroj, char* dest){    BitReader bitreader(zdroj);    IntWriter intwriter(dest);    zatímco (bitreader.opustil())    {        int n = 0;        zatímco (bitreader.inputBit())     // potenciálně nebezpečné s poškozenými soubory.            ++n;        int počet;        -li (n == 0)            počet = 0;        jiný        {            počet = 1;            pro (int i = 0; i < n-1; ++i)            {                int val = 1;                pro (int j = 0; j < počet; ++j)                    val = (val << 1) | bitreader.inputBit();                počet = val;            }        }        intwriter.putInt(počet);           // vypíše hodnotu    }    bitreader.zavřít();    intwriter.zavřít();}

Viz také

Reference

^ „1968 papír V. I. Levenshteina (v ruštině)“ (PDF).
^ David Salomon (2007). Kódy s proměnnou délkou pro kompresi dat. Springer. p. 80. ISBN 978-1-84628-958-3.

[1] „1968 papír V. I. Levenshteina (v ruštině)“ (PDF).

[2] David Salomon (2007). Kódy s proměnnou délkou pro kompresi dat. Springer. p. 80. ISBN 978-1-84628-958-3.

[1]

[2]