eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingLiczby całkowite zmiennej długości
Ilość wypowiedzi w tym wątku: 9

  • 1. Data: 2014-04-29 21:21:55
    Temat: Liczby całkowite zmiennej długości
    Od: Borneq <b...@a...hidden.pl>

    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?


  • 2. Data: 2014-04-29 23:05:01
    Temat: Re: Liczby całkowite zmiennej długości
    Od: bartekltg <b...@g...com>

    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




  • 3. Data: 2014-04-29 23:38:34
    Temat: Re: Liczby całkowite zmiennej długości
    Od: Wojciech Muła <w...@g...com>

    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.


  • 4. Data: 2014-04-30 00:47:56
    Temat: Re: Liczby całkowite zmiennej długości
    Od: Borneq <b...@a...hidden.pl>

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




  • 5. Data: 2014-04-30 00:58:48
    Temat: Re: Liczby całkowite zmiennej długości
    Od: Borneq <b...@a...hidden.pl>

    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


  • 6. Data: 2014-04-30 08:30:58
    Temat: Re: Liczby całkowite zmiennej długości
    Od: Borneq <b...@a...hidden.pl>

    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.


  • 7. Data: 2014-04-30 08:37:23
    Temat: Re: Liczby całkowite zmiennej długości
    Od: Wojciech Muła <w...@g...com>

    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.


  • 8. Data: 2014-04-30 09:32:27
    Temat: Re: Liczby całkowite zmiennej długości
    Od: Maciej Sobczak <s...@g...com>

    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


  • 9. Data: 2014-04-30 13:22:14
    Temat: Re: Liczby całkowite zmiennej długości
    Od: bartekltg <b...@g...com>

    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


strony : [ 1 ]


Szukaj w grupach

Szukaj w grupach

Eksperci egospodarka.pl

1 1 1

Wpisz nazwę miasta, dla którego chcesz znaleźć jednostkę ZUS.

Wzory dokumentów

Bezpłatne wzory dokumentów i formularzy.
Wyszukaj i pobierz za darmo: