Jak zakodować liczbę tak, aby mała liczba mieściła się w jednym bajcie a
większe w odpowiednio większej liczbie bajtów.
jednym ze sposobów jest varint:
https://developers.google.com/protocol-buffers/docs/
encoding
mamy ciąg bajtów: bierzemy pierwszy bajt, patrzymy na najstarszy bit,
jeśli=1 oznacza że czeka nas jeszcze jeden bajt, patrzymy na najstarszy
bit itd.
Narzut = 1/8, jeden bit z bajta użyty.Czy są jeszcze bardziej wydajne
sposoby? Kodowanie utf-8 jest podobnie kodem zmiennej długości.
Jak zakodować liczbę ujemną? zygzakiem:
dla ciągu 0,-1,1,-2,2,-3,3,-4,4... przyjmujemy 0,1,2,3,4,5,6...

Czy jest jakieś kodowanie zmiennej długości bitów a nie bajtów?

do góry

W dniu 2014-04-29 21:21, Borneq pisze:
> Jak zakodować liczbę tak, aby mała liczba mieściła się w jednym bajcie a
> większe w odpowiednio większej liczbie bajtów.
> jednym ze sposobów jest varint:
> https://developers.google.com/protocol-buffers/docs/
encoding
> mamy ciąg bajtów: bierzemy pierwszy bajt, patrzymy na najstarszy bit,
> jeśli=1 oznacza że czeka nas jeszcze jeden bajt, patrzymy na najstarszy
> bit itd.
> Narzut = 1/8, jeden bit z bajta użyty.Czy są jeszcze bardziej wydajne
> sposoby? Kodowanie utf-8 jest podobnie kodem zmiennej długości.
> Jak zakodować liczbę ujemną? zygzakiem:
> dla ciągu 0,-1,1,-2,2,-3,3,-4,4... przyjmujemy 0,1,2,3,4,5,6...
>
> Czy jest jakieś kodowanie zmiennej długości bitów a nie bajtów?

Jak je kodować najlepiej zależy od rozkładu długosci tych liczb.
Czysto teoretycznie można by pomyśleć o przyporządkowaniu
kodowania Huffmana każdej liczbie. Wtedy czytając ciąg bitów
wiesz, kiedy nastąpił koniec, a samo kodowanie będzie oszczędne
(poza absurdalnie wielkim słownikiem:)

Inny pomysł niż Twój/unicodu.
Jak zapisujemy liczby na kartce? Cyfra po cyfrze, a jak
chcemy następną, dajemy spację. Łatwo to zastosować tutaj.
Komputer zapisuje liczby np bajt po bajcie, każdy
bajt to liczba 0-255, razem tworzą system pozycyjny
o podstawie 256.
To niech tworzą system pozycyjny o podstawie 255,
a liczba "FF" odpowiada spacji. Dla liczb większych
niż 255^7 = 7e16 jest to sposób oszczędniejszy.
Oczywiście liczbę bitów przeznaczonych na cyfrę
można modyfikować, dobierając do potrzeb.

Można iść dalej, niech mamy alfabet złożony z "cyfr"
'0', '1'...'n-1' oraz znak końca cyfry '_'
Dla wygody odczytu proponuję np n = 256,
albo 10, ze względów historycznych.

Mamy rozkład prawdopodobieństwa wystąpienia kolejnych
liczb (~wykładniczy , poissona, czy jednostajny na jakimś
przedziale). Mamy więc prawdopodobieństwa wystąpienia
cyfr i znaku '_'.

No to rzucamy to we wspomniane już kodowanie Huffmana.
Jeśli liczby są małe, znak końca występuje częściej niż
każda cyfra i dostanie ona krótszy kod. Jeśli liczby
średnio są długie, dostanie kod dłuższy niż cyfra.

To rozwiązanie będzie dość blisko ideału.

cyfry 1-9, średnio liczby 3.33 cyfrowe
http://huffman.ooz.ie/?text=123456789KKK
3 lub 4 bity na liczbę (średnio 3.8 bita)
2 bity na znak końca liczby.
średnia liczba zajumuje więc
3.33 * 3.8 bajta + 2 bajty = 14.654.

W poprzednim kodowaniu, 127/1000 liczb
mieści się w bajcie, 873/1000 w dwóch.
127/1000*8 + 873/1000*16 = 14.984

Nie jest to zabójcza poprawa, ale jest.

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 dużych liczb drzewo kodowań jest "zrównoważone"
i metoda praktycznie nie różni się od proponowanej
wcześniej - ustalonego symbolu końca,
tylko tym razem symbole sa różnej długośći (różnią się o 1)
i nie ejsteśmy ograniczeni do systemów pozycyjnych
o bazie postaci 2^n-1;


Na koniec jeszcze dwa drzewka dla krótkich w systemie
szesnastkowym
http://huffman.ooz.ie/?text=0123456789ABCDEFKKK
http://huffman.ooz.ie/?text=0123456789ABCDEFKKKKKKK

A, dla bardzo krótkich liczb koniec linii jest jednym
bitem, np 0, a każda cyfra zaczyna się od 1.
http://huffman.ooz.ie/?text=0123456789ABCDEFKKKKKKKK
KKK
To właściwie idealnie odpowiada opisanej metodzie
'jedynka, jeśli będzie dodatkowy bit', tylko ten
bit jest na końcu, zamiast na początku. Uzasadnia
to też taki wybór, domyślnie w utf-8 większość
znaków jest 7 bitowa.

pzdr
bartekltg

do góry

On Tuesday, April 29, 2014 9:21:55 PM UTC+2, Borneq wrote:
> Narzut = 1/8, jeden bit z bajta użyty.Czy są jeszcze bardziej wydajne
> sposoby? Kodowanie utf-8 jest podobnie kodem zmiennej długości.
> Jak zakodować liczbę ujemną? zygzakiem:
> dla ciągu 0,-1,1,-2,2,-3,3,-4,4... przyjmujemy 0,1,2,3,4,5,6...
>
> Czy jest jakieś kodowanie zmiennej długości bitów a nie bajtów?

Np. kodowania Eliasa, kodowanie Golomba/Rice'a, kodowanie
Tunstalla. Są też inne kody podobne do varint, przegląd
znajdziesz w pracy "Inverted Index Compression and Query
Processing with Optimized Document Ordering" (autorzy:
Hao Yan, Shuai Ding, Torsten Suel).

Problemem w kodowaniu na poziomie bitów jest mała szybkość,
procesory działają jednak na poziomie bajtów. Np. w indeksach
Google liczby 32-bitowe kodowane są w paczkach po 4: w pierwszym
bajcie są długości tych liczb (po 2 bity), za nim zmienna
liczba bajtów - od 4 do 16.

w.

do góry

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 %.

do góry

W dniu 2014-04-29 23:38, Wojciech Muła pisze:
> Np. kodowania Eliasa, kodowanie Golomba/Rice'a, kodowanie
> Tunstalla. Są też inne kody podobne do varint, przegląd

Kod Golomba/Rice'a jest ciekawy, tylko trzeba by dobrać odpowiedni rząd

do góry

W dniu 2014-04-29 23:05, bartekltg pisze:
> To niech tworzą system pozycyjny o podstawie 255,
> a liczba "FF" odpowiada spacji. Dla liczb większych
> niż 255^7 = 7e16 jest to sposób oszczędniejszy.
> Oczywiście liczbę bitów przeznaczonych na cyfrę
> można modyfikować, dobierając do potrzeb.

Może kodowanie arytmetyczne:
strumień bitów, kod końca liczby, kod zmiany znaku (zwykle po sobie mają
ten sam znak) oraz każda liczba (oprócz zera) będzie zaczynała się od
jedynki - można ja pominąć dodatkowo kod rzadko występującego zera.

0 i jedynka - prawdopodobieństwo 114/256
zero - 1/256
zmiana znaku - 4/256
znak końca liczby - 23/256

To by było optymalne zakodowanie: na jedną liczbę przypadało by prawie
równo 16 bitów,
tak więc liczba miała by 9.64 bita ale zakodowana za pomocą 11.25 bita,
do tego dochodziłby narzut w postaci 3.476 bita jako znacznik końca
liczby do każdej liczby, nie mówiąc o znacznikach zmiany znaku
To jest rozwiązanie optymalnie entropicznie, ale nie podoba mi się że
przy każdej liczbie niemal 3.5 bita musi być znacznika końca, w mojej
prostszej wersji liczby leciały bez znacznika bo każda liczba tyle samo
bitów, poza tym 16% narzut na same bity liczby bo prawdopodobieństwo
każdego bitu to 44% a nie 50%
Myślę że metoda entropiczna nie uwzględnia tego że w każdym obiekcie
rozkład długości liczb skupia się między 10 a 15 bitów a nie jest od 0
do nieskończoności.
A tak to optymalne zdaje się że jest gorsze od kodowania po maksymalnej
długości delty w elemencie.

do góry

On Wednesday, April 30, 2014 12:58:48 AM UTC+2, Borneq wrote:
> Kod Golomba/Rice'a jest ciekawy, tylko trzeba by dobrać odpowiedni rząd.

W formacie FLAC jest dobierany adaptywnie.

w.

do góry

W dniu wtorek, 29 kwietnia 2014 21:21:55 UTC+2 użytkownik Borneq napisał:

> Jak zakodować liczbę tak, aby mała liczba mieściła się w jednym bajcie a
> większe w odpowiednio większej liczbie bajtów.
>
> jednym ze sposobów jest varint:
>
> https://developers.google.com/protocol-buffers/docs/
encoding

Inny przykład do podejrzenia:

https://github.com/msgpack/msgpack/blob/master/spec.
md#formats-int

> Czy jest jakieś kodowanie zmiennej długości bitów a nie bajtów?

Tak, ale będą trudniejsze w obsłudze. Praktyczną jednostką dostępu i transmisji jest
bajt a nie bit.

--
Maciej Sobczak * http://www.msobczak.com * http://www.inspirel.com

do góry

On 30.04.2014 08:30, Borneq wrote:
> W dniu 2014-04-29 23:05, bartekltg pisze:
>> To niech tworzą system pozycyjny o podstawie 255,
>> a liczba "FF" odpowiada spacji. Dla liczb większych
>> niż 255^7 = 7e16 jest to sposób oszczędniejszy.
>> Oczywiście liczbę bitów przeznaczonych na cyfrę
>> można modyfikować, dobierając do potrzeb.
>
> Może kodowanie arytmetyczne:
> strumień bitów, kod końca liczby, kod zmiany znaku (zwykle po sobie mają
> ten sam znak) oraz każda liczba (oprócz zera) będzie zaczynała się od
> jedynki - można ja pominąć dodatkowo kod rzadko występującego zera.


> 0 i jedynka - prawdopodobieństwo 114/256
> zero - 1/256
> zmiana znaku - 4/256
> znak końca liczby - 23/256

Wzięcie 0 i 1 to dość głupi pomysł. W zasobożernym kodowaniu
arytmetycznym ujdzie, ale przy huffmanie dostaniesz
jednobitowy kod zera i dwubitowy kod jedynki. I dla długiuch
liczb leżymy.
Weź większe paczki za symbol.

Znak zera jest niepotrzebny. Zero to koniec '0''K'
albo nawet sam znak końca. Jeśli wystąpią dwa po kolei, to znaczy,
że było tam zero.

> To by było optymalne zakodowanie: na jedną liczbę przypadało by prawie
> równo 16 bitów,
> tak więc liczba miała by 9.64 bita ale zakodowana za pomocą 11.25 bita,
> do tego dochodziłby narzut w postaci 3.476 bita jako znacznik końca
> liczby do każdej liczby, nie mówiąc o znacznikach zmiany znaku
> To jest rozwiązanie optymalnie entropicznie, ale nie podoba mi się że
> przy każdej liczbie niemal 3.5 bita musi być znacznika końca, w mojej
> prostszej wersji liczby leciały bez znacznika bo każda liczba tyle samo
> bitów, poza tym 16% narzut na same bity liczby bo prawdopodobieństwo
> każdego bitu to 44% a nie 50%
> Myślę że metoda entropiczna nie uwzględnia tego że w każdym obiekcie
> rozkład długości liczb skupia się między 10 a 15 bitów a nie jest od 0
> do nieskończoności.

Każda metoda uwzględnia to, co jej powiesz.

Teraz trzeba wziąć symbole '0'-'n' i sprawdzić, dla jakiego n będziesz
miał najlepszy wynik.
ponieważ liczby są krótkie, znak końca linii pewnie wyjdzie jednobitowy,
czyli, jak rozmawialiśmy wcześniej, praktycznie dostaniesz to
amo co używając jednego bitu za znacznik 'jeszcze jedna cyfra'
w kodowaniu 8 lub 16 bitowym.
Jeśli rzeczywiśćei skupiają się do 15 bitów, a mniej niż 9 prawie
nigdy nie mają, zastanowiłbym się nad użyciem 15+1 bitów,
wtedy prawie na pewno użyjesz 16, a używając 7+1 prawie nic
nie oszczędzasz, bo jednocyfrowe (7 bitopwa cyfra) zdarzają
się rzadko.


> A tak to optymalne zdaje się że jest gorsze od kodowania po maksymalnej
> długości delty w elemencie.

Nie wiem, co do dlugość delty. Odnosisz się do jakeijś poważniejszej
metody podanej w tym watku, czy do interpretacji tych danych (której
nie znamy;p)

pzdr
bartekltg

do góry