Levenshtein koodi

Levenshtein-koodi  on yleinen koodi , jonka avulla voit koodata ei-negatiivisia kokonaislukuja . Sen loi Vladimir Levenshtein .

Nollakoodi on  "0"; positiivisen luvun koodaamiseen käytetään seuraavaa algoritmia:

  1. Alusta askellaskuri C = 1, K  on numeron koodi (alku tyhjä).
  2. Kirjoita koodatun luvun binäärikoodi ilman "korkeinta" 1:tä (kirjoita esimerkiksi numero 1100 100:ksi; numero 100 00:ksi).
  3. Lisää vastaanotettu alkuun K .
  4. Olkoon M  toisessa vaiheessa kirjoitettujen bittien lukumäärä. Muunna M binääriksi.
  5. Jos M ei ole tyhjä, niin C = C + 1 ja toista algoritmi vaiheesta 2 saadulle M :lle. Muussa tapauksessa siirry vaiheeseen 6.
  6. Kirjoita C -yksikköä ja 0 K - koodin alkuun (esimerkiksi jos laskuri C \u003d 2, K \u003d 0 011, saat: 110 0 011) - Levenshtein-koodi.

Levenshtein-koodi ensimmäisille 24 numerolle näyttäisi tältä:

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

Olkoon K  Levenshtein-koodi. Levenshtein-koodin salauksen purkamiseksi sinun on:

  1. Laske numero 1 bitistä ensimmäiseen nollabittiin.
  2. Jos C = 0, niin koodattu arvo on 0 . Jos ei, siirry vaiheeseen 3.
  3. Hävitä K :stä nämä C -yksiköt ja seuraavat 0 . Kirjoita K :n uusi arvo ylös .
  4. Aseta muuttuja N = 1. Syötä askellaskuri P = C  - 1.
  5. Jos P = 0, niin N  on haluttu luku. Jos ei, siirry vaiheeseen 6.
  6. Lue ensimmäiset N bittiä K :stä . Kirjoita K: lle uusi arvo lukematta N bittiä.
  7. Lisää lukutietueen alkuun 1 (esimerkiksi lue 00, vastaanotettu: 100).
  8. Muunna vastaanotettu arvo desimaalijärjestelmäksi (tai alkuperäiseksi, jos tiedossa) - muuttujan N uusi arvo .
  9. P = P  - 1. Toista vaiheesta 5.

Levenshtein-koodauksessa positiivinen luku on aina 1 bitin suurempi kuin omega Elias -koodauksessa . Nolla voidaan kuitenkin koodata Levenshtein-koodilla, kun taas Elias omega -koodauksella on välttämätöntä määrittää kaikki numerot uudelleen siten, että nolla on yksi.


Linkit

Lähde