Kodowanie Levensteina lub kodowanie Levenshteina to uniwersalny kod kodujący nieujemne liczby całkowite opracowany przez Vladimira Levenshteina .
Kodowanie
Kod zera to „0”; zakodować liczbę dodatnią :
- Zainicjuj zmienną licznika kroków C na 1.
- Zapisz binarną reprezentację liczby bez początkowej „1” na początku kodu.
- Niech M będzie liczbą bitów zapisanych w kroku 2.
- Jeśli M nie wynosi 0, zwiększ C , powtórz od kroku 2 z M jako nową liczbą.
- Napisz bity C „1” i „0” na początku kodu.
Kod zaczyna się:
| Numer |
Kodowanie |
Domniemane prawdopodobieństwo |
| 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 |
Aby zdekodować liczbę całkowitą zakodowaną metodą Levensteina:
- Policz liczbę bitów „1”, aż napotkasz „0”.
- Jeśli liczba wynosi zero, wartość wynosi zero, w przeciwnym razie
- Zacznij od zmiennej N , ustaw ją na wartość 1 i powtórz count minus 1 razy:
- Odczytaj N bitów, dodaj „1”, przypisz wynikową wartość do N
Kod Levensteina dodatniej liczby całkowitej jest zawsze o jeden bit dłuższy niż kod omega Eliasa tej liczby całkowitej. Istnieje jednak kod Levensteina oznaczający zero, podczas gdy kodowanie Elias omega wymagałoby przesunięcia liczb, tak aby zero było reprezentowane przez kod oznaczający jedynkę.
Przykładowy kod
Kodowanie
0
void levenshteinEncode ( char * source , char * dest ) { IntReader intreader ( source ); BitWriter BitWriter ( miejsce docelowe ); while ( intreader . hasLeft ()) { int num = intreader . pobierzInt (); if ( liczba == ) zapis bitowy . 0
0
0
0 bit wyjściowy ( ); else { int c = ; Bity BitStack ; wykonaj { int m = ; for ( int temp = liczba ; temp > 1 ; temp >>= 1 ) // oblicz piętro(log2(liczba)) ++ m ; for ( int i = ; ja < m ;
0
0
++ i ) bity . pushBit (( liczba >> i ) & 1 ); liczba = m ; ++ do ; } while ( liczba > ); for ( int i = ; i < c ; ++ i ) bitwriter . bit wyjściowy ( 1 ); bitwriter . 0
0
bit wyjściowy ( ); while ( bity . długość ( ) > ) bitwriter . outputBit ( bity . popBit ()); } } }
Rozszyfrowanie
0
void levenshteinDecode ( char * source , char * dest ) { BitReader bitreader ( source ); IntWriter intwriter ( dest ); while ( czytnik bitów . hasLeft ()) { int n = ; while ( bitreader . inputBit ()) // potencjalnie niebezpieczne ze zniekształconymi plikami. ++
0
0
0
0 n ; int liczba ; jeśli ( n == ) liczba = ; else { liczba = 1 ; for ( int ja = ; ja < n -1 ; ++ ja ) { int wartość = 1 ; for ( int j = ; j < liczba ; ++ j
) wartość = ( wartość << 1 ) | czytnik bitów . bit wejściowy (); liczba = wartość ; } } autor . putInt ( liczba ); // wypisz wartość } bitreader . zamknij (); autor . zamknij (); }
Zobacz też
