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