Wizyta kosmitów i co z tego wynikło
123456789.987654321 ??? Co to?
Jakiś czas temu usłyszałem taką historyjkę (odemnie - Zenon/DIAL). Przybysze z innej
planety chcąc zabrać ze sobą jak najwięcej informacji, do jej zapisu, zastosowali taką metodę: każdej literze
wykorzystywanego alfabetu przypisali pewną liczbę, a następnie kolejne litery do zakodowania zamieniali na liczby i
zapisywali na koolejnych miejscach po przecinku. Tekst "TEST" zostałby zakodowany jako liczba: 0,20051920 (20-T; 5-E;
19-S). W ten sposób otrzymali dość długą liczbę. Na pręcie o określonej długości zaznaczyli miejsce, które określała ta
liczba. Sposób wydaje się genialny.
Możliwość zapisania nieograniczonej ilości danych w skończonym obszarze. Ale czy aby
na pewno? Załóżmy, że pręt ma długość metra. Liczbę jakiego rzędu jesteśmy w stanie zapisać? Jedna cyfra po przecinku to
operowanie decymetrami, 2 - cyframi, 3 to milimetry itd. W pewnym momencie może być trudno biorąc pod uwagę, że średnica
atomu wynosi 10^-10 metra. Już przy 11 cyfrze stracilibyśmy informację. Do tego dochodzi rozszerzalność cieplna. Sposób
z pozoru genialny okazał się kiepski. Dziesięć cyfr na metrowej długości pręcie to żadne osiągnięcie. Oczywiście sposób
zapisu informacji nie jest optymalny i można byłoby to poprawić nawet kilkukrotnie, ale to nie zmienia faktu, że metoda
jest kiepska. Więc dlaczego się rozpisuję, skoro nie jest to nic specjalnego?
Koncepcja jest na tyle oryginalna, że można się jej bliżej przyjrzeć. Po pierwsze zrezygnujmy z pręta (jak to podłączyć
do Atari ? ;-) ). Operujmy na liczbach. Przyjmijmy, że naszym alfabetem są wszystkie możliwe wartości jakie może przyjąć
bajt, a więc <0;255>. Nie zapisujmy tego jak w opowieści czyli:
0, 123 123 ...
ponieważ otrzymujemy liczbę, która po zakodowaniu jest dłuższa niż oryginał. Wykorzystajmy pozostałe 744 (1000-256)
wartości z każdych trzycyfrowych grup cyfr. Oznaczmy liczbę wynikową jako W. Teraz tak: pobieramy bajt, mnożymy go przez
1/256 i dodajemy do W. Pobieramy kolejny, mnożymy przez 1/(256^2) i dodajemy do W itd. I co otrzymujemy? Bardzo
skomplikowany sposób zapisu bajtów, który w żaden sposób nie wpływa na zmniejszenie objętości danych. Nie tędy droga.
Właściwie to dlaczego każdemu symbolowi przypisywać 1/256 część liczby? Może uzależnić to od prawdopodobieństwa
wystąpienia? Spróbujmy. Suma prawdopodobieństw wystąpienia wszystkich symboli wynosi 1. Dla naszego tekstu "TEST"
prawdopodobieństwo wystąpienia każdego z symboli wynosi:
T = 2/4 = 0,5
E = 1/4 = 0,25
S = 1/4 = 0,25
Oznaczmy to na odcinku (według numerów bajtów):
E S T
|--------+--------+----------------|
0 0,25 0,5 1
Symbolom odpowiadają następujące przedziały:
| E = <0 | ;0,25) |
| S = <0,25 | ;0,5) |
| T = <0,5 | ;1) |
Liczba 0,5 jak również 0,99 oznacza, że wystąpiło T. Jeżeli teraz odcinek reprezentujący T podzielimy znowu w ten sam
sposób jak początkowy odcinek <0;1), możemy zapisywać kolejne symbole. Wystąpiło "T" więc rozpatrujemy odcinek
<0,5; 1). Dzielimy go jak poprzednio:
E S T
|--------+--------+----------------|
0,5 0,625 0,75 1
Stąd widać, że liczba z przedziału <0,5; 0,625) oznacza, że wystąpiły symbole "TE". Kontynuując otrzymamy:
E S T
|--------+--------+----------------|
0,5 0,53125 0,5625 0,625
Kodujemy "S" czyli otrzymujemy: <0,53125; 0,5625). I dalej:
E S T
|--------+--------+----------------|
0,53125 | 0,546875 0,5625
0,5390625
I kodujemy "T", więc ostatecznie nasz przedział to: <0,546875; 0,5625). Liczba z tego przedziału to nasz zakodowany
tekst "TEST". Możemy wybrać dowolną, którą najłatwiej będzie zakodować. Spróbujmy liczbę 0,55 (wyglada na krótką ;-) ).
Wykorzystajmy zapis, który omówiliśmy wcześniej:
L1 L2 Li
W = ------ + ------ + ... + ------
256^1 256^2 256^i
Oznaczmy ten wzór numerem 1. Spróbujmy zapisać tę liczbę na jednym bajcie:
Niestety nie udało się. Ale czy to znaczy, że nie można tego zapisać na jednym bajcie? Tego jeszcze nie wiemy. Spróbujmy
z inną liczbą z przedziału reprezentującego nasz tekst. Jeśli nasze x w poprzedniej próbie wyszło 140,8 to sprawdzamy
czy dla 141 otrzymamy liczbę mieszczącą się w przedziale.
141/256 = 0,55078125.
Liczba w przedziale się mieści, więc akceptujemy. Jak widać liczba, którą jest łatwiej kodować w zapisie dwójkowym, nie
musi "wyglądać krótko" w zapisie dziesiętnym. Przedstawiony tu sposób znalezienia "najlepszej" liczby z przedziału (to
znaczy kodowanej na najmniejszej liczbie bitów) jest dość pokrętny, ale to tylko przykład, można to zrobić lepiej. Poza
tym operujemy na liczbach zmiennoprzecinkowych, co utrudnia oprogramowanie tego. Liczby muszą być bardzo dużej
dokładności (zalecana jest dokładność dążąca do nieskończoności przy bardzo długich danych, o ile zależy nam na
poprawnym zdekodowaniu danych ;-) ). Więc czy warto? Chyba tak, skoro cztery bajty udało nam się zakodować w jednym.
Oczywiście trzeba tu wspomnieć, że musimy zakodować również dane o prawdopodobieństwach dla kodowanych symboli (jeśli ma
to być dekodowalne ;-) ). W tym przypadku dane te spowodują zwiększenie danych wynikowych na tyle, że kompresja straci
sens, ale dla większej ilości danych jest jak najbardziej opłacalna (o ile prawdopodobieństwa wystąpień nie są jednakowe
(czyli nie mamy do czynienia z szumem)). Możliwe, że zastanawia Cię jeszcze jedna kwestia. Dlaczego częściej występujące
symbole zajmują większy odcinek? Ma to związek ze sposobem reprezentacji wyniku. Bardzo małe przedziały muszą być
przedstawiane za pomocą bardziej precyzyjnych liczb, a co za tym idzie większa ilość danych jest potrzebna do zapisu
takiej liczby. I jeszcze może słówko o dekompresji. Wiemy, że mamy następujące symbole z następującymi przedziałami
prawdopodobieństw:
| E = <0 | ;0,25) |
| S = <0,25 | ;0,5) |
| T = <0,5 | ;1) |
oraz, że zakodowane dane to bajt 141. Co dalej? Zmieniamy format zapisu według wzoru 1
W = 141/256 = 0,55078125.
Sprawdzamy, w którym z przedziałów mieści się liczba. Jest to <0,5; 1), który reprezentuje bajt "T". Teraz ten
przedział dzielimy na podprzedziały:
E S T
|--------+--------+----------------|
0,5 0,625 0,75 1
I znowu sprawdzamy w którym z przedziałów mieści się liczba. Jest to <0,5; 0,625), a on reprezentuje symbol "E".
Kontynuujemy w ten sam sposób, aż do... No właśnie, dokąd? Jedna liczba może reprezentować dużą ilość zakodowanych
bajtów. Dlatego w kodowanym ciągu dobrze jest zawrzeć informację o tym, jaka jest długość danych wynikowych.
Rysunek poniżej obrazuje idee podziału odcinka na podstawie kodowanego symbolu.
Kto się podejmie napisania kompresora w oparciu o te informacje? Ja rezygnuję.
Lepiej zamienić liczby zmiennoprzecinkowe na całkowite, ale o tym w następnym artykule.
Glonisz/Quasimodos
|
