W dniu 2014-04-29 23:05, bartekltg pisze:
> Liczby średnio dwucyfrowe
> http://huffman.ooz.ie/?text=0123456789KKKKK
> (na każde dwie liczby przypada jeden konec linii)
> mamy 5.8 bita, kontra 8 we wcześniejszej metodzie.
> http://www.wolframalpha.com/input/?i=%284*8%2B2*3%29
%2F10%2B2

Dla zer i jedynek jest
http://huffman.ooz.ie/?text=101010100K0110010K010101
0100K
K ma dwa bity, ale i jedynka, której jest połowa ilości ma dwa bity.
Można by rozpatrywać kodowanie arytmetyczne, ale jeszcze bardziej
komplikuje, są działania na wielkich liczbach.
Do czego to ma być użyte: w pliku binarnym są przechowywane współrzędne
linii łamanych w ten sposób, że pierwszy punkt jest przechowywany
normalnie (ewentualnie później optymalizacje), następne punkty
przechowywane są w postaci różnic, dzięki czemu liczba, która
przechowywana jest z dokładnością 32 bitową, ma różnice rzędu
najczęściej 300-2000. Liczby mogą być ujemne, więc stosuję metodę
zygzakową ustawiając kolejno: 0,-1,1,-2,2,-3,3...
Liczby mieszczą się najczęściej w dwóch bajtach, mając ilość bitów
10-15, najczęściej 11-12.
Można to zrobić tak (już przed laty stosowałem ten sposób), że mając
osobno (choć niekoniecznie) dla współrzędnej X i Y patrzę na deltę,
która wymaga najwięcej bitów np. 14, zapisuję tę liczbę i wszystkie
pozostałe delty zapisuję na takiej samej ilości bitów. To ma wadę, bo
wiele wartości może mieć np. 11 bitów a jedna 15 to wszystkie będą
wymagały 15-tu.

Można by trochę pokombinować: Niektóre delty są <= średnia długość a
niektóre większe. Większe zapisywać z maksymalną długością, mniejsze z
maksymalną długością małych. Niestety, trzeba by rozróżnić które są
mniejsze a które większe czyli dla każdej delty jeden bit, co powoduje
że ten sposób nie jest wiele lepszy niż z użyciem maksymalnej wartości.
Tylko trochę mi się nie podoba - mogą wszystkie delty być malutkie a
jedna ogromna i to psuje kodowanie, na szczęście takie nie występują
zbyt często i strata jest średnio dla przykładu 2.6 bita dla średnio
11.5 bitowej liczby czyli 22.6 %.