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:
- Alusta askellaskuri C = 1, K on numeron koodi (alku tyhjä).
- Kirjoita koodatun luvun binäärikoodi ilman "korkeinta" 1:tä (kirjoita esimerkiksi numero 1100 100:ksi; numero 100 00:ksi).
- Lisää vastaanotettu alkuun K .
- Olkoon M toisessa vaiheessa kirjoitettujen bittien lukumäärä. Muunna M binääriksi.
- Jos M ei ole tyhjä, niin C = C + 1 ja toista algoritmi vaiheesta 2 saadulle M :lle. Muussa tapauksessa siirry vaiheeseen 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:
- Laske numero 1 bitistä ensimmäiseen nollabittiin.
- Jos C = 0, niin koodattu arvo on 0 . Jos ei, siirry vaiheeseen 3.
- Hävitä K :stä nämä C -yksiköt ja seuraavat 0 . Kirjoita K :n uusi arvo ylös .
- Aseta muuttuja N = 1. Syötä askellaskuri P = C - 1.
- Jos P = 0, niin N on haluttu luku. Jos ei, siirry vaiheeseen 6.
- Lue ensimmäiset N bittiä K :stä . Kirjoita K: lle uusi arvo lukematta N bittiä.
- Lisää lukutietueen alkuun 1 (esimerkiksi lue 00, vastaanotettu: 100).
- Muunna vastaanotettu arvo desimaalijärjestelmäksi (tai alkuperäiseksi, jos tiedossa) - muuttujan N uusi arvo .
- 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