..:: Serious Magazine ::..
wydanie 13

  Wstępniak
  Serious...
  Konkurs - rozwiązanie
  Wspomnienie
  Wiedza
  Koronkowa robota
  Tester EPROM
  Prog. równoległy AT89C2051
  ATMEL - obsługa programu
  EPROM - programator...
  Oporniki, oporniki...
  Blokada komputera
  Archiver
  Wizyta kosmitów...
  Kompresja arytmetyczna
  Analizator stanów logicznych
  ASL - obsługa
  Moja miłość
  Powroty z przeszłości
  Porady
  Pracownia elektronika
  Parowanie tranzystorów
  Pętla induktofoniczna
  Super, extra, cacy cartridge
  Makroassembler ATMAS II

  Wyjście
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:

      0,55 = x/256.
      x = 140,8

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.

Idea podziału odcinka


      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


Następny artykuł Do góry Poprzedni artykuł