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

Offline MadMax

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

# Wrzesień 15, 2006, 15:29:19
Witam

Chcialbym jakos upakowac tablice liczb z ktorych kazda miesci sie w przedziale od 0 do 30. tablica moze skladac sie maksymalnie z 27 elementow.

np :

1, 3, 4, 6, 7, 8, 14, 21, 22, 25, 27

lub tablica :

1, 3, 12, 15, 16

liczby moga byc w dowolnej kolejnosci po dekompresji (moge sobie posortowac pozniej). W tablicy nigdy nie ma 2 takich samych liczb, a przedzial od jednej do drogiej jest losowy, wiec nie wiem jaki tu wzorek zastosowac. Nie wiem tez jakiej kompresji zastosowac, a jest ich jak wiadomo duzo - nie mam na tym polu doswiadczenia.

Za wszelka pomoc z gory dziekuje - i prosze pamietac Bog w dzieciach wynagrodzi ;).

Pozdrawiam,
MadMax

Offline Mr. Spam

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

Offline vashpan

  • Użytkownik
    • Strona

# Wrzesień 15, 2006, 15:44:15
A nie lepiej zamiast tracic czas na takie poszukiwania zastosowac jakas biblioteke... np. zlib.

Jak duze te tablice beda ??


nadult

  • Gość
# Wrzesień 15, 2006, 15:53:03
Możesz zastosować następujący schemat:
1. Zapisujesz pierwszy element (i=0)
2. Następny jest różnica pomiędzy (n=i-1 i n=i).
3. Lecisz tak przez całą tablicę.
Masz przygotowaną tablicę z deltami. Jeśli delty nie różnią się wiele, np. dla twojego
1, 3, 4, 6, 7, 8, 14, 21, 22, 25, 27dostajesz
_1_,2,1,2,1,1,6,7,1,3,2Widać, że delty są tylko 1,2,3,6,7 i teraz możesz użyć 3 bitów do zapisu każdej liczby. Czyli  przykładowo 1=000,2=001,3=010,6=011,7=100. Możesz do tego użyć przykładowo kodowania Huffmana.

Offline MadMax

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

# Wrzesień 15, 2006, 15:56:18
A nie lepiej zamiast tracic czas na takie poszukiwania zastosowac jakas biblioteke... np. zlib.


Niestety potrzebuje rozwiazania na wlasna reke, nie korzystajac z innych libow - nie pytaj dlaczego :).

Jak duze te tablice beda ??
Tak jak pisalem liczba elementow tablicy moze wynosic maksymalnie 27 - wtedy kazdy indeks tablicy jest wiekszy o 1 od poprzedniego - [1, 2, 3, 4, 5.... 27]. W tablicach o mniejszej liczbie elementow przechowywane liczby maja rozny uskok (czy jak to nazwac) np. - [1, 3, 4, 7, 15, 20].

Edit:

agent_J: DZIEKI ! dzisiaj to wyproboje.

Pozdrawiam,
MadMax

Offline vashpan

  • Użytkownik
    • Strona

# Wrzesień 15, 2006, 15:58:29
Sorry, doczytalem teraz ze tablica maksymalnie moze sie skladac z 27 elementow...  :-[

Jezeli to sa zwykle liczby, to po co je w ogole kompresowac ?, przy 27 intach taka tablica zajmuje 108 bajtow... ( to nawet nie musza byc pelne 32 bitowe inty bo nawet zwykly char wystarczy do zapisania liczb z tego przedzialu... a wtedy to by bylo tylko 27 bajtow... ) 

No chyba ze takich tablic ma byc tysiace....

Offline MadMax

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

# Wrzesień 15, 2006, 16:12:43
Sorry, doczytalem teraz ze tablica maksymalnie moze sie skladac z 27 elementow... :-[

Jezeli to sa zwykle liczby, to po co je w ogole kompresowac ?, przy 27 intach taka tablica zajmuje 108 bajtow... ( to nawet nie musza byc pelne 32 bitowe inty bo nawet zwykly char wystarczy do zapisania liczb z tego przedzialu... a wtedy to by bylo tylko 27 bajtow... )

No chyba ze takich tablic ma byc tysiace....

Niestety tych tablic ma byc miliony :) dlatego kompresja jest dla mnie tak wazna.

Offline vashpan

  • Użytkownik
    • Strona

# Wrzesień 15, 2006, 16:55:18
No to zmienia postac rzeczy ;)

A mozna wiedziec dlaczego nie mozesz uzyc darmowej biblioteki typu zlib ? :)
***

Tak mi przyszlo na mysl... Nie wiem moze sie nie znam, ale moze prostym rozwiazaniem byloby zastosowanie pol bitowych, dla maksymalnej wartosci 30, 5 bitow by wystarczylo... Mimo ze nie daloby takiego stopnia kompresji jak rozwiazanie agenta_J ( gorsze o ~2 bity na liczbie, zaleznie od przypadku i czy tablice bylyby posortowane przed kompresja... ( zakladam ze tak ) ) Nie wymagaloby to jednak procesu kompresji i dekompresji co byc moze pozwoliloby zaoszczedzic czas ( choc slyszalem ze stosowanie pol bitowych jest nieco wolniejsze niz normalnych liczb ).

Z gory uprzedzam ze nie upieram sie przy takim rzowiazaniu ;) Sam najpewniej wzialbym zliba...

Offline MadMax

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

# Wrzesień 15, 2006, 17:23:03
A mozna wiedziec dlaczego nie mozesz uzyc darmowej biblioteki typu zlib ? :)

Z 3 powodow :
1. trywialny: szkoda mi troche czasu na research o zlibie, dodatkowo patrz pt. 3.
2. powod jest wazniejszy: zlib mi tego raczej nie skompresuje tak jak jest mi potrzebne.
3: chce by kodzik dzialal nie tylko na pecetach, ale tez na telefonach komorkowych dlatego jest pewne ograniczenie rozmiaru.

Cytuj
Tak mi przyszlo na mysl... Nie wiem moze sie nie znam, ale moze prostym rozwiazaniem byloby zastosowanie pol bitowych, dla maksymalnej wartosci 30, 5 bitow by wystarczylo... Mimo ze nie daloby takiego stopnia kompresji jak rozwiazanie agenta_J ( gorsze o ~2 bity na liczbie, zaleznie od przypadku i czy tablice bylyby posortowane przed kompresja... ( zakladam ze tak ) ) Nie wymagaloby to jednak procesu kompresji i dekompresji co byc moze pozwoliloby zaoszczedzic czas ( choc slyszalem ze stosowanie pol bitowych jest nieco wolniejsze niz normalnych liczb ).

Nic nie mowilem, ale to wlasnie juz probowalem - niestety potrzeba wiekszej kompresji. Nic wspomnialem o tym, bo chcialem by kazdy zaiteresowany tematem mogl podac swoj wlasny tok mysli bez narzucen moich (niestety jak narazie jeszcze marnych) sposobow kompresji :).

Mysle ze algorytm Huffmana, ktory podal agent_J sporo pomoze, bo liczba bitow na delte bedzie malala wraz ze wzrostem elementow w tablicy (jednak w przypadku zmiennej liczby bitow potrzebna jest dodatkowa informacja o liczbie bitow dla delty danej tablicy), w kazdym razie mysle jeszcze jak by to inaczej skompresowac (lub nie koniecznie inaczej, a np. polepszyc rozwiazanie huffmana :) - moze jakis trybik mi zaskoczy).

Offline vashpan

  • Użytkownik
    • Strona

# Wrzesień 15, 2006, 17:48:43
Zebysmy sie rozumieli - piszesz w javie czy C++ pod Symbianem ???? :)


Jezeli C++ to na dobra sprawe zlib mozna skompilowac samodzielnie ( z tego co wiem wymaga jedynie biblioteki standardowej C ) A jesli w javie to chyba tez jest odpowiednia wersja zlib ;)

Nie skompresuje tak jak trzeba, tzn. ?

Wpadlem tez na inny pomysl... Moze po prostu laczyc te tablice i pozniej kompresowac...  Nastepnie po prostu podzial giga-tablicy na czesci 27 elementowe.

Offline Silther

  • Użytkownik

# Wrzesień 15, 2006, 17:54:27
Nie znam się zbytnio na kompresji, ale skoro każda liczba może występować tylko raz, to chyba najlepiej zrobić prostą 31-elementową tablicę boolów, w której zapisujemy, czy dana liczba wystąpiła, czy nie np.
if (tablica [5])
//wystąpiła liczba 5
W ten sposób zapamiętanie wszystkich liczb zawsze będzie zajmowało 31 bitów, czyli niecały rozmiar inta (przy ograniczeniu do 27 elementów możesz zamiast tablicy bool'ów stosować operacje na bitach jakiegoś inta).
Sposób jest bardzo prosty i nie wymaga (prawie) dekompresji.

Offline SirMike

  • Użytkownik
    • SirMike's Techblog

# Wrzesień 15, 2006, 18:17:39
Nie znam się zbytnio na kompresji, ale skoro każda liczba może występować tylko raz, to chyba najlepiej zrobić prostą 31-elementową tablicę boolów, w której zapisujemy, czy dana liczba wystąpiła, czy nie np.

a od kiedy to bool zajmuje 1 bit?

Offline Silther

  • Użytkownik

# Wrzesień 15, 2006, 18:35:28
a od kiedy to bool zajmuje 1 bit?
OMG, racja. Głupstwo walnąłem  :-[ Oczywiście bool jest zapisywany jako jeden bajt, ale to nie zmienia faktu, że operując na bitach można całość zmieścić w jednej zmiennej typu int.

nadult

  • Gość
# Wrzesień 15, 2006, 18:54:50
Mysle ze algorytm Huffmana, ktory podal agent_J sporo pomoze, bo liczba bitow na delte bedzie malala wraz ze wzrostem elementow w tablicy (jednak w przypadku zmiennej liczby bitow potrzebna jest dodatkowa informacja o liczbie bitow dla delty danej tablicy), w kazdym razie mysle jeszcze jak by to inaczej skompresowac (lub nie koniecznie inaczej, a np. polepszyc rozwiazanie huffmana :) - moze jakis trybik mi zaskoczy).
Jeśli już kodujesz Huffmanem, to przydało by się jakoś te liczby wcześniej przekształcić żeby się jescze lepiej kompresowały. Zamiast delt proponuje algorytm MTF, powinien dać lepsze efekty (i jest też bardzo łatwy w implementacji):

http://www.arturocampos.com/ac_mtf.html

Offline MadMax

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

# Wrzesień 15, 2006, 19:29:22
nadult: dzieki! zaraz pocztam. Moze sie nie da bardziej skompresowac, ale zawsze warto pokombinowac i wybrac najlepszy wariant :).

Zebysmy sie rozumieli - piszesz w javie czy C++ pod Symbianem ???? :)

W javie i w c++ na pc. Tak jak pisalem - chce by algos byl nie tylko na fony (sybian, czy j2me), ale i pc itp.

Jezeli C++ to na dobra sprawe zlib mozna skompilowac samodzielnie ( z tego co wiem wymaga jedynie biblioteki standardowej C ) A jesli w javie to chyba tez jest odpowiednia wersja zlib ;)

Nie skompresuje tak jak trzeba, tzn. ?

Nie skompresuje, no chyba ze podal bym zlibowi caly plik ;). Na fony zlib odpada np. tel z ograniczeniem 64 kb na gre - sam kod zliba by pewnie z 40 % zajmowal :).

Wpadlem tez na inny pomysl... Moze po prostu laczyc te tablice i pozniej kompresowac...  Nastepnie po prostu podzial giga-tablicy na czesci 27 elementowe.

W sumie tak mozna - sie zobaczy.

Cytat: Silther
Nie znam się zbytnio na kompresji, ale skoro każda liczba może występować tylko raz, to chyba najlepiej zrobić prostą 31-elementową tablicę boolów, w której zapisujemy, czy dana liczba wystąpiła, czy nie np.

Kod:
if (tablica [5])
//wystąpiła liczba 5W ten sposób zapamiętanie wszystkich liczb zawsze będzie zajmowało 31 bitów, czyli niecały rozmiar inta (przy ograniczeniu do 27 elementów możesz zamiast tablicy bool'ów stosować operacje na bitach jakiegoś inta).
Sposób jest bardzo prosty i nie wymaga (prawie) dekompresji.

Tak tez robilem i co prawda maska ma 32 bity, ale tablica jest generowana z mniejszych danych, dlatego chcialbym by kompresja zmniejszyla tablice przynajmniej do rozmiaru rownego danym wejsciowym.

dodam tylko, ze liczby w tablicy sa posortowane, ale wcale nie musza. Moze jest jakis algos, co straci kolejnosc liczb, ale je dobrze skompresuje. Tak czy siak lece czytac arty.

Pozdrawiam,
MadMax

Offline SirMike

  • Użytkownik
    • SirMike's Techblog

# Wrzesień 15, 2006, 19:57:11
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 :)