Autor Wątek: Kompresja tablicy liczb z przedzialu od 0..27  (Przeczytany 6148 razy)

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Wrzesień 15, 2006, 20:22:37
a od kiedy to bool zajmuje 1 bit?
ale to nie zmienia faktu, że operując na bitach można całość zmieścić w jednej zmiennej typu int.

Tak, to nie jest glupi pomysl. Tylko nie wiem czy autorowi watku odpowiadaja takie zalozenia :)
Czytając opisy, to jest dokłądnie to, o co chodzi autorowi wątku. :)

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline MadMax

  • Użytkownik
    • http://mobiledeveloper.cba.pl/

# Wrzesień 16, 2006, 02:11:14
Witam

Zrobilem cos nowego, co moze znacznie wplynac na kompresje, tylko ktory algos teraz wybrac (jeszcze doczytam te tutki).

Skoro tablica jest uporzadkowana (nastepny element jest wiekszy od poprzedniego) i zaden element sie nie powtarza, to zastosowalem metode do wyrownania niektorych liczb w tablicy:

np. tablice:

[2, 4, 5, 6, 12, 13, 15, 16, 17, 20]

zmienilem w:

[1, 2, 2, 2, 7, 7, 8, 8, 8, 10]

poprzez odejmowanie w petli przez rosnaca (przy kazdym obiegu o 1) wartosc - niestety mozna ten krok zrobic tylko raz, by elementy nie byly ujemne.

nastepnie znajduje delte :

[1, 1, 0, 0, 5, 0, 1, 0, 0, 2]

kod prosty jak ... ale dziala dla kazdej tablicy :), bo z tego co zaobserwowalem debugerem - z 50 do 80 % cyfr sie powtarza po zastosowaniu ponizszego kodu.

int n = 0;
for (i= tableSize-1; i >= 0; i--) {
      table[i] += (++n);
}

n = 0;
delta[0] = table[tablesize-1];
for (i = tablesize-2; i > 0; i--) {
    delta[++n] = table[i-1]- table[i];
}

Z tego co wyczytalem z tutkow (i co zreszta nie wymaga za wiele inteligencji ;) ) mozna ten ciag :

[1, 2, 2, 2, 7, 7, 8, 8, 8, 10]

skompresowac tak:

[1, 2 x 3, 7 x 2, 8 x 3, 10]

jednak moze ma ktos jakas uwage (ciekawa, lub mniej) - co mozna jeszcze z tym zrobic. Hmm moze sie wyrobie w bajcie komresujac ta tablice 30 elementowa haha :).

//edit aha dodatko probowalem tez metode (w sumie lepsza)

mam tablice:

[2, 4, 5, 6, 9, 15, 16, 17, 22, 23]

od kazdego elementu odjmuje 1 (bo zmienilem zalozenia i moge sobie pozwolic by tablica zawsze byla w zakresie 1...27).

[1, 3, 4, 5, 8, 14, 15, 16, 21, 22]

a nastepnie zmienilem w:

[0, 1, 1, 1, 6, 6, 7, 7, 7, 9]

a np. delta

[0, 1, 0, 0, 5, 0, 1, 0, 0, 2]

tym samym zmienilem zakres wartosci, jednak nie zmiejszylem jeszcze zapotrzebowania na bity na liczbe. Odejmowal bym w nieskonczonosc, ale w jaki sposob zapisac ile trzeba odjac od poszczegolnych indeksow, by nie bylo nadmiarowych danych.

Pozdrawiam,
MadMax.
« Ostatnia zmiana: Wrzesień 16, 2006, 03:05:16 wysłana przez MadMax »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Wrzesień 16, 2006, 02:44:13
Cytuj
Hmm moze sie wyrobie w bajcie komresujac ta tablice 30 elementowa haha :).
Nie dasz rady. :) Bajt ma tylko 256 różnych wartości, a twoja tablica może być zbudowana na znacznie więcej, niż 256 sposobów. Pozatym, nie wiem, po co tak kombinujesz, skoro rozwiązanie już masz podane na tacy (zapisać bitami w int, które elementy są, a których nie ma i masz 4 bajty na tablicę). :)

Offline MadMax

  • Użytkownik
    • http://mobiledeveloper.cba.pl/

# Wrzesień 16, 2006, 03:07:53
Krzysiek. K: zawsze warto pokombinowac - moze sie jeszcze uda jakos zmniejszyc, a to by w niczym nie przeszkadzalo :). Zeby sie chociaz o 1 bajt jeszcze dalo "to juz byl bym w domu" :).

Pozdrawiam,
MadMax
« Ostatnia zmiana: Wrzesień 16, 2006, 03:19:47 wysłana przez MadMax »

Offline Krzysiek K.

  • Redaktor
    • DevKK.net

# Wrzesień 16, 2006, 13:24:49
Krzysiek. K: zawsze warto pokombinowac - moze sie jeszcze uda jakos zmniejszyc, a to by w niczym nie przeszkadzalo :). Zeby sie chociaz o 1 bajt jeszcze dalo "to juz byl bym w domu" :).
Przypisz kolejne numery każdej prawidłowej konfiguracji i zapisuj te numery zamiast samych zbiorów, ale wątpię, żebyś tym coś znacząco poprawił (poza tym trochę możesz mieć zabawy z napisaniem kompresora/dekompresora do tego). Lepiej, niż to, się skompresować pojedynczego zbioru nie da, bo ilość poprawnych wyników kompresji musi być taka sama, jak ilość poprawnych tablic do skompresowania.


Przykładowo, różnych 15-elementowych zbiorów liczb z przedziału 0-30 jest ponad 300 milionów (można to wyznaczyć z dwumianu Newtona), czego wynikiem jest fakt, że takich zbiorów nie da się skompresować do mniej niż średnio 28 bitów na jeden zbiór, zakładając, że każdy z tych zbiorów ma jednakowe prawdopodobieństwo pojawienia się na wejściu. Biorąc pod uwagę, że chcesz kompresować wszystkie zbiory o liczności 0-27 elementów, wątpię, żeby matematycznie było możliwe zejście poniżej średniej 30 bitów na zbiór (można to dosyć łatwo policzyć, ale mi się nie chce). :)

Offline Megabyte

  • Użytkownik

# Wrzesień 16, 2006, 13:49:58
a od kiedy to bool zajmuje 1 bit?
OMG, racja. Głupstwo walnąłem  :-[ Oczywiście bool jest zapisywany jako jeden bajt, ....
Teraz też głupstwo walnąłeś.

Offline MadMax

  • Użytkownik
    • http://mobiledeveloper.cba.pl/

# Wrzesień 16, 2006, 15:37:13
Witam

Krzysiek. K: zawsze warto pokombinowac - moze sie jeszcze uda jakos zmniejszyc, a to by w niczym nie przeszkadzalo :). Zeby sie chociaz o 1 bajt jeszcze dalo "to juz byl bym w domu" :).
Przypisz kolejne numery każdej prawidłowej konfiguracji i zapisuj te numery zamiast samych zbiorów, ale wątpię, żebyś tym coś znacząco poprawił (poza tym trochę możesz mieć zabawy z napisaniem kompresora/dekompresora do tego). Lepiej, niż to, się skompresować pojedynczego zbioru nie da, bo ilość poprawnych wyników kompresji musi być taka sama, jak ilość poprawnych tablic do skompresowania.

Przykładowo, różnych 15-elementowych zbiorów liczb z przedziału 0-30 jest ponad 300 milionów (można to wyznaczyć z dwumianu Newtona), czego wynikiem jest fakt, że takich zbiorów nie da się skompresować do mniej niż średnio 28 bitów na jeden zbiór, zakładając, że każdy z tych zbiorów ma jednakowe prawdopodobieństwo pojawienia się na wejściu. Biorąc pod uwagę, że chcesz kompresować wszystkie zbiory o liczności 0-27 elementów, wątpię, żeby matematycznie było możliwe zejście poniżej średniej 30 bitów na zbiór (można to dosyć łatwo policzyć, ale mi się nie chce). :)

Krzysiek K.: teraz to mnie przekonales ostatecznie :). Ok, koncze dalsze ulepszanie kompresji, bo w sumie racja 30 bitow nie jest zle :).

Dziekuje wszystkim za odpowiedzi!.

Pozdrawiam,
MadMax.

Offline orzech

  • Użytkownik
    • homepage

# Wrzesień 16, 2006, 15:53:20
a od kiedy to bool zajmuje 1 bit?
OMG, racja. Głupstwo walnąłem  :-[ Oczywiście bool jest zapisywany jako jeden bajt, ....
Teraz też głupstwo walnąłeś.
Czy możesz rozwinąć swoją wypowiedź? Jeśli chodzi o C++ i o Jave (o których tutaj rozmawiamy podejrzewam), to wielkość zmiennej typu bool (w przypadku C++) i boolean (w Javie) mają dokładnie wielkość 1 bajta.

Pozdrawiam!

Offline Megabyte

  • Użytkownik

# Wrzesień 16, 2006, 16:19:32
Czy możesz rozwinąć swoją wypowiedź? Jeśli chodzi o C++ i o Jave (o których tutaj rozmawiamy podejrzewam), to wielkość zmiennej typu bool (w przypadku C++) i boolean (w Javie) mają dokładnie wielkość 1 bajta.

Pozdrawiam!
Punkt 5.3.3 standardu C++ (ISO-IEC-14882:2003) mówi

Cytuj
The sizeof operator yields the number of bytes in the object representation of its operand. The operand
is either an expression, which is not evaluated, or a parenthesized type-id. The sizeof operator shall not
be applied to an expression that has function or incomplete type, or to an enumeration type before all its
enumerators have been declared, or to the parenthesized name of such types, or to an lvalue that designates
a bit-field. sizeof(char), sizeof(signed char) and sizeof(unsigned char) are 1; the
result of sizeof applied to any other fundamental type (3.9.1) is implementation-defined. [Note: in particular,
sizeof(bool) and sizeof(wchar_t) are implementation-defined.69) ] [Note: See 1.7 for
the definition of byte and 3.9 for the definition of object representation. ]

Mówiąc po polsku, typ bool może zajmować dowolną ilość bajtów (i rzeczywiście zdarza się że ma on rózną wielkość w róznych kompilatorach, co więcej nawet przy różnych ustawieniach może mieć różną wartość). Należy zwracać na to uwage przy zapisie zmiennych typu bool do pliku binarnego. Najlepiej jest go zrzutować np na char.

Offline orzech

  • Użytkownik
    • homepage

# Wrzesień 16, 2006, 16:59:34
Punkt 5.3.3 standardu C++ (ISO-IEC-14882:2003) mówi
Ok, sprawdziłem, masz rację w takim razie. ;)

Offline vashpan

  • Użytkownik
    • Strona

# Wrzesień 16, 2006, 22:21:50
z tego co sie orientuje zlib niekoniecznie operuje na plikach, po prostu na buforach... ktore mozna ale nie trzeba zapisac do pliku. No dobra ale jezeli nie to nie ;)

Bitmaska to rzeczywiscie dobry pomysl, sprowadzi 27 bajtowa tablice to bajtow 4 czyli 32 bitow ( prawie te 30 bitow mininalne ( jak ktos tam zdazyl policzyc ) ). Czyli jakies 7 razy mniej, na dodatek byloby to o wiele szybsze, a wszelkiego rodzaju kompresje dla kilkomegabajtowego kodu jakim na pewno bylyby te "miliony" tych tablic naprawde spowolnilaby dzialanie takiego programu, nawet na komputerze a co dopiero na telefonie i w javie :|

Co do standardu jezyka... nie wiem po co ktos mialby w swoim kompilatorze implementowac bool'a jako cos wiekszego niz 1 bajt...

Koniecznosc kompresowania tych danych nadal jednak jest dla nas zagadka :)

agent_J

  • Gość
# Wrzesień 17, 2006, 09:22:38
A ja ci zaproponuję jeszcze algorytm (de)kompresji LZO.

http://www.oberhumer.com/opensource/lzo/

Sama dekompresja jest bardzo szybka i nie wymaga dodatkowych buforów. Masz nawet port dla Javy :)


Offline MadMax

  • Użytkownik
    • http://mobiledeveloper.cba.pl/

# Wrzesień 17, 2006, 11:34:50
Witam

agent_J: dzieki. Hmm fakt faktem, ze przeciez moze jeszcze uda sie ta 32 bitowa maske skompresowac - jak by sie udalo, to kolejny zysk bitow :). Popatrze jutro, bo dzis musze jechac.

Pozdrawiam,
MadMax

Offline Gorion

  • Użytkownik
    • Strona domowa

# Wrzesień 22, 2006, 10:52:06
MadMax: piszesz Sudoku czy mi sie tylko wydaje? 8)

Offline MadMax

  • Użytkownik
    • http://mobiledeveloper.cba.pl/

# Wrzesień 22, 2006, 16:32:30
Wtam

Gorion: nic z tych rzeczy hehe :), tylko mialem algosa, ktory generowal liczby z przedzialu 0..27 do 32.

Pozdrawiam,
MadMax