Levenshteinův kód

Levenshteinův kód  je univerzální kód , který vám umožňuje kódovat nezáporná celá čísla . Vytvořil jej Vladimir Levenshtein .

Nulový kód  je "0"; pro zakódování kladného čísla se používá následující algoritmus:

  1. Inicializujte počítadlo kroků C = 1, K  je kód čísla (zpočátku prázdný).
  2. Napište binární kód zakódovaného čísla bez "nejvyšší" 1 (například číslo 1100 napište jako 100; číslo 100 jako 00).
  3. Přidejte přijaté na začátek K .
  4. Nechť M  je počet bitů zapsaných ve druhém kroku. Převeďte M na binární.
  5. Pokud M není prázdné, pak C = C + 1 a opakujte algoritmus z kroku 2 pro výsledné M. V opačném případě přejděte ke kroku 6.
  6. Napište C kusů jednotek a 0 na začátek kódu K (například pokud počítadlo C \u003d 2, K \u003d 0 011, dostanete: 110 0 011) - Levenshteinův kód.

Levenshteinův kód pro prvních 24 čísel by vypadal takto:

0 0 110 2 110 0 3 110 1 4 1110 000 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

Nechť K  je Levenshteinův kód. Chcete-li dešifrovat Levenshteinův kód, musíte:

  1. Počítejte číslo od 1 bitu do prvního nulového bitu.
  2. Pokud C = 0, pak je zakódovaná hodnota 0 . Pokud ne, přejděte ke kroku 3.
  3. Vyřaďte z K tyto jednotky C a následující 0 . Zapište novou hodnotu K.
  4. Nastavte proměnnou N = 1. Zadejte počítadlo kroků P = C  - 1.
  5. Pokud P = 0, pak N  je požadované číslo. Pokud ne, přejděte ke kroku 6.
  6. Přečtěte si prvních N bitů z K. Zapište novou hodnotu do K bez čtení N bitů.
  7. Přidejte 1 na začátek čteného záznamu (například čtení 00, přijato: 100).
  8. Převeďte přijatou hodnotu do desítkové soustavy (nebo původní, pokud je známa) - nová hodnota proměnné N .
  9. P = P  - 1. Opakujte od kroku 5.

V Levenshteinově kódování je kladné číslo vždy o 1 bit vyšší než v kódování omega Elias . Nula však může být zakódována Levenshteinovým kódem, zatímco u Eliasova kódování omega je nutné přeznačit všechny číslice tak, aby nula byla reprezentována jedničkou.


Odkazy

Zdroj