eGospodarka.pl
eGospodarka.pl poleca

eGospodarka.plGrupypl.comp.programmingkompresja danych
Ilość wypowiedzi w tym wątku: 10

  • 1. Data: 2009-10-17 14:08:28
    Temat: Re: kompresja danych
    Od: "Wiktor S." <w...@M...fm>

    > 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


  • 2. Data: 2009-10-17 17:55:10
    Temat: kompresja danych
    Od: Mariusz Marszałkowski <m...@g...com>

    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


  • 3. Data: 2009-10-17 18:34:33
    Temat: Re: kompresja danych
    Od: Wojciech Muła <w...@p...null.onet.pl.invalid>

    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.


  • 4. Data: 2009-10-17 21:09:53
    Temat: Re: kompresja danych
    Od: Mariusz Marszałkowski <m...@g...com>

    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


  • 5. Data: 2009-10-17 21:42:54
    Temat: Re: kompresja danych
    Od: Wojciech Muła <w...@p...null.onet.pl.invalid>

    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.


  • 6. Data: 2009-10-17 22:05:41
    Temat: Re: kompresja danych
    Od: Mariusz Marszałkowski <m...@g...com>

    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.


  • 7. Data: 2009-10-18 00:55:43
    Temat: Re: kompresja danych
    Od: Wojciech Muła <w...@p...null.onet.pl.invalid>

    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.


  • 8. Data: 2009-10-18 07:37:55
    Temat: Re: kompresja danych
    Od: Mariusz Marszałkowski <m...@g...com>

    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.


  • 9. Data: 2009-10-18 17:11:51
    Temat: Re: kompresja danych
    Od: Mariusz Marszałkowski <m...@g...com>

    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ę



  • 10. Data: 2009-10-19 13:36:25
    Temat: Re: kompresja danych
    Od: Daniel Janus <d...@d...pl>

    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]

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: