> Np. jest 30 kolumn i 20mln wierszy. Dane często wyglądają tak,
> jakby sąsiadujące wiersze miały z dużym prawdopodobieństwem
> te sam wartości w kolumnach. Np. w kolumnie 3-ciej od wiersza
> 100 do 200 są same jedynki, w kolumnie 2 od wiersza 50 do 150
> są same zera. Wszystkie dane to mały podzbiór liczb całkowitych,
> powiedzmy o mocy kilkuset elementów.

A gdybyś transponował całą tablicę, otrzymałbyś długie ciągi identycznych
znaków. To mogłoby zwiększyć współczynnik kompresji, zwłaszcza gdy czas nie
gra roli.


--
Azarien

do góry

Witam

Są jakieś specjalne algorytmy do kompresji tabel danych, w których
jest stała długość wiersza, a kolejność wierszy nie ma znaczenia?

Oznacza to, że kompresor może dowolnie zmieniać kolejność
wierszy i podczas dekompresji nie musi odtworzyć pierwotenj
kolejności.

Pozdrawiam

do góry

Mariusz Marszałkowski <m...@g...com> wrote:

> Są jakieś specjalne algorytmy do kompresji tabel danych, w których
> jest stała długość wiersza, a kolejność wierszy nie ma znaczenia?
>
> Oznacza to, że kompresor może dowolnie zmieniać kolejność
> wierszy i podczas dekompresji nie musi odtworzyć pierwotenj
> kolejności.

Nie słyszałem o niczym takim. A co masz w tych wierszach?
Te wiersze się powtarzają?

w.

do góry

On 17 Paź, 20:34, Wojciech Muła
<w...@p...null.onet.pl.invalid> wrote:
> Mariusz Marszałkowski <m...@g...com> wrote:
> > Są jakieś specjalne algorytmy do kompresji tabel danych, w których
> > jest stała długość wiersza, a kolejność wierszy nie ma znaczenia?
>
> > Oznacza to, że kompresor może dowolnie zmieniać kolejność
> > wierszy i podczas dekompresji nie musi odtworzyć pierwotenj
> > kolejności.
>
> Nie słyszałem o niczym takim. A co masz w tych wierszach?
> Te wiersze się powtarzają?

Np. jest 30 kolumn i 20mln wierszy. Dane często wyglądają tak,
jakby sąsiadujące wiersze miały z dużym prawdopodobieństwem
te sam wartości w kolumnach. Np. w kolumnie 3-ciej od wiersza
100 do 200 są same jedynki, w kolumnie 2 od wiersza 50 do 150
są same zera. Wszystkie dane to mały podzbiór liczb całkowitych,
powiedzmy o mocy kilkuset elementów.

Uważam że można do tego podejść na dwa sposoby:
1) Skompresować każdą kolumnę osobno, podejrzewam że prosta
metoda długości serii skompresuje niektóre kolumny 100 krotnie.
2) Jakoś specjalnie posortować wiersze, aby dane powtarzające się
były blisko siebie
3) Można połączyć obie metody, najpierw jakoś posortować wiersze,
a później sortować każdą kolumnę niezależnie.

Kompresja może trwać dowolnie długo, nawet całą dobę, ale dekompresja
musi być bardzo szybka, gdyż skompresowane dane trafią do pamięci
RAM i będą dekompresowane w każdej iteracji algorytmu.

Pozdrawiam serdecznie

do góry

Mariusz Marszałkowski <m...@g...com> wrote:

> > Nie słyszałem o niczym takim. A co masz w tych wierszach?
> > Te wiersze się powtarzają?
>
> Np. jest 30 kolumn i 20mln wierszy. Dane często wyglądają tak,
> jakby sąsiadujące wiersze miały z dużym prawdopodobieństwem
> te sam wartości w kolumnach. Np. w kolumnie 3-ciej od wiersza
> 100 do 200 są same jedynki, w kolumnie 2 od wiersza 50 do 150
> są same zera. Wszystkie dane to mały podzbiór liczb całkowitych,
> powiedzmy o mocy kilkuset elementów.

Jakbyś pokazał przykładowe kilka tysięcy wierszy, to można
by coś konkretnego doradzić. RLE pewnie coś da, tylko nie
wiadomo czy dla wszystkich kolumn tak samo. Może pomogłaby
jakaś transformacja danych na poziomie kolumn albo wierszy.

Pytanie takie: spróbowałeś z istniejącymi bibliotekami
do kompresji, jak gzip, libzip, lzo? Może się sprawdzą.

w.

do góry

On 17 Paź, 23:42, Wojciech Muła
<w...@p...null.onet.pl.invalid> wrote:
> Mariusz Marszałkowski <m...@g...com> wrote:
> > > Nie słyszałem o niczym takim. A co masz w tych wierszach?
> > > Te wiersze się powtarzają?
>
> > Np. jest 30 kolumn i 20mln wierszy. Dane często wyglądają tak,
> > jakby sąsiadujące wiersze miały z dużym prawdopodobieństwem
> > te sam wartości w kolumnach. Np. w kolumnie 3-ciej od wiersza
> > 100 do 200 są same jedynki, w kolumnie 2 od wiersza 50 do 150
> > są same zera. Wszystkie dane to mały podzbiór liczb całkowitych,
> > powiedzmy o mocy kilkuset elementów.
>
> Jakbyś pokazał przykładowe kilka tysięcy wierszy, to można
> by coś konkretnego doradzić.

Coś w tym stylu: http://www.przeklej.pl/plik/nm-stats-out-rar-00044r9
d06jo

> RLE pewnie coś da, tylko nie
> wiadomo czy dla wszystkich kolumn tak samo. Może pomogłaby
> jakaś transformacja danych na poziomie kolumn albo wierszy.
Też takie ogóle przemyślenia mam, ale żadnych konkretów.

> Pytanie takie: spróbowałeś z istniejącymi bibliotekami
> do kompresji, jak gzip, libzip, lzo? Może się sprawdzą.
Na razie tylko się zastanawiam nad tym, próby zacznę za tydzień
lub dwa. Standardowe kompresory kompresują to 20-30 krotnie.

Pewnie najlepiej wypadnie najpierw długość serii + zamiana
wartości na pozycję + jakaś metda LZ. Długość serii dekompresuje
się błyskawicznie, zamiana wartości na pozycję trochę gorzej,
LZ też jest bardzo szybkie.

Więc pozostaje pytanie jaką metodą zmienić kolejność rekordów,
aby jakoś kompresji była jak najlepsza.

Pozdrawiam


>
> w.

do góry

Mariusz Marszałkowski <m...@g...com> wrote:

> Pewnie najlepiej wypadnie najpierw długość serii + zamiana
> wartości na pozycję + jakaś metda LZ. Długość serii dekompresuje
> się błyskawicznie, zamiana wartości na pozycję trochę gorzej,
> LZ też jest bardzo szybkie.
>
> Więc pozostaje pytanie jaką metodą zmienić kolejność rekordów,
> aby jakoś kompresji była jak najlepsza.

Przeanalizowałem pierwszy milion rekordów i moje wnioski
są następujące. Po odrzuceniu niektórych kolumn, liczba
różnych kombinacji wartości w rekordach jest stosunkowo mała.
Odrzuciłem kolumny 0, 21, 22 i 23 - liczba kombinacji
to mniej niż 100 tysięcy. Pewnie jakby odrzucić trochę więcej,
ta liczba spadłaby (jest już późno, nie chce mi się bawić).

Więc można wpierw pogrupować rekordy wg tych kombinacji, np.
wrzucić do hashmapy; od razu znasz wartości 20-kilku kolumn.
Zaś pozostałe kolumny można już kompresować, albo nawet zapisać
wprost, pewnie byś się zmieścił w kilku bajtach na rekord.

dobranoc
w.

do góry

On 18 Paź, 02:55, Wojciech Muła
<w...@p...null.onet.pl.invalid> wrote:
> Mariusz Marszałkowski <m...@g...com> wrote:
> > Pewnie najlepiej wypadnie najpierw długość serii + zamiana
> > wartości na pozycję + jakaś metda LZ. Długość serii dekompresuje
> > się błyskawicznie, zamiana wartości na pozycję trochę gorzej,
> > LZ też jest bardzo szybkie.
>
> > Więc pozostaje pytanie jaką metodą zmienić kolejność rekordów,
> > aby jakoś kompresji była jak najlepsza.
>
> Przeanalizowałem pierwszy milion rekordów i moje wnioski
> są następujące. Po odrzuceniu niektórych kolumn, liczba
> różnych kombinacji wartości w rekordach jest stosunkowo mała.
> Odrzuciłem kolumny 0, 21, 22 i 23 - liczba kombinacji
> to mniej niż 100 tysięcy. Pewnie jakby odrzucić trochę więcej,
> ta liczba spadłaby (jest już późno, nie chce mi się bawić).
>
> Więc można wpierw pogrupować rekordy wg tych kombinacji, np.
> wrzucić do hashmapy; od razu znasz wartości 20-kilku kolumn.
> Zaś pozostałe kolumny można już kompresować, albo nawet zapisać
> wprost, pewnie byś się zmieścił w kilku bajtach na rekord.

Dziękuję serdecznie.

do góry

On 17 Paź, 16:08, "Wiktor S." <w...@M...fm> wrote:
> > Np. jest 30 kolumn i 20mln wierszy. Dane często wyglądają tak,
> > jakby sąsiadujące wiersze miały z dużym prawdopodobieństwem
> > te sam wartości w kolumnach. Np. w kolumnie 3-ciej od wiersza
> > 100 do 200 są same jedynki, w kolumnie 2 od wiersza 50 do 150
> > są same zera. Wszystkie dane to mały podzbiór liczb całkowitych,
> > powiedzmy o mocy kilkuset elementów.
>
> A gdybyś transponował całą tablicę, otrzymałbyś długie ciągi identycznych
> znaków. To mogłoby zwiększyć współczynnik kompresji, zwłaszcza gdy czas nie
> gra roli.

Czas kompresji nie gra roli, czas dekompresji gra rolę. Podczas
dekompresji
będę musiał mieć sekwencyjny dostęp do rekordów, czyli wszystkie
rekordy
będę musiał przeglądać w każdej iteracji, ale kolejność w jakiej je
przejrzę
nie ma znaczenia.

Pozdrawiam i dziękuję

do góry

Dnia 17.10.2009 Mariusz Marszałkowski <m...@g...com> napisał/a:

> Witam
>
> Są jakieś specjalne algorytmy do kompresji tabel danych, w których
> jest stała długość wiersza, a kolejność wierszy nie ma znaczenia?
>
> Oznacza to, że kompresor może dowolnie zmieniać kolejność
> wierszy i podczas dekompresji nie musi odtworzyć pierwotenj
> kolejności.

A jak jest z duplikatami? Bo jeśli można je zignorować, to
posortowanie wierszy leksykograficznie, zrobienie uniq i
zbudowanie z nich DAWG-u mogłoby dać sensowne rezultaty.

Jeśli trzeba pamiętać, ile było duplikatów, to można
to zapamiętywać w liściach DAWG-u.

--
Daniel Janus <d...@d...pl> | http://danieljanus.pl
"Chryste, chcemy czystej.
Boże, coraz drożej.
Panie, chcemy taniej." [JacPo]

do góry