Hlavní navigace

Vlákno názorů k článku Unixová komprese v praxi: Bzip2 od martin - Kdyz jsem si tak procital clanek, prisel jsem...

  • Článek je starý, nové názory již nelze přidávat.
  • 28. 4. 2003 19:44

    martin (neregistrovaný)

    Kdyz jsem si tak procital clanek, prisel jsem na zajimavou vec. Diky tomu, ze je algoritmus takto staveny by mela ciste teoreticky probihat dekomrimace dele nez komrpimace, alespon me to tak prijde, protoze roztocit to a dat dohromady to dovedu i z hlavy.

    BTW moc mi neprijde logicke vzit konec retezce, to bych spis vzal predek, protoze ten je preci serazeny, ne?

  • 29. 4. 2003 11:43

    KLON (neregistrovaný)

    První je seřazený, ale nedává permutaci.
    Seřazením poslední dostaneš první a naví i permutaci.
    Více viz první vlákno diskuze.

  • 29. 4. 2003 13:53

    Petr Krčmář (neregistrovaný)

    Jasně, o tom jsem se nezmínil, ale je to tak. U drtivé většiny algoritmů je komprese mnohem náročnější, ale tady je to naopak.

    Jinak děkuji všem za pozitivní ohlasy, člověka to potěší.

    Petr

  • 2. 5. 2003 11:46

    Sofronius (neregistrovaný)

    Nevim, jak je to s rychlosti komprese a dekomprese programu bzip2, ale pokud budeme mluvit pouze o Burrowsove-Wheelerove transformaci, pak nesouhlasim s tim, ze dekomprese je narocnejsi nez komprese.

    Jak uz totiz nekdo nekde v prispevcich podotkl, pri zpetne transformaci neni zapotrebi pouzivat zadny komplikovany tridici algoritmus, ktery je casove nejnarocnejsim prvkem Burrowsovy-Wheelerovy transformace.

    Podivam-li se do puvodni zpravy Burrowse a Wheelera, napr.:
    http://gatekeeper.dec.com/pub/DEC/SRC/research-reports/abstracts/src-rr-124.html
    zjistuji, ze autori tam poskytuji zmerene casy pro kombinaci transformace s Move-to-Front encoding a Huffmanovym kodovanim. A ze jejich implementaci algoritmu trva komprese zhruba petkrat dele, nez dekomprese.

    Jste si opravdu jist, ze bzip2 komprimuje rychleji, nez dekomprimuje ??

    Clanek neni tak spatny. Nicmene nechat odvozeni zpetne transformace na ctenare mi prijde trochu nefer, mne to neprijde jednoduche a rozhodne je to vyrazne narocnejsi na mozek nez cely clanek. Prislo by mi vic fer rict,ze "lze efektivne provest zpetnou transformaci, ale jeji vyklad (vedeny dostatecne podrobne, aby byl snadny k pochopeni) by neumerne zvetsil rozsah clanku, takze se mu nebudeme venovat", nebo neco v tom stylu.

  • 15. 6. 2011 14:27

    Majkl (neregistrovaný)

    Řekl bych že s tím poměrem náročnosti kódování a dekódování u BW transformace nemáte pravdu.
    Při kódování musíte třídit jednotlivé rotované kopie originálního bloku a je jich stejně jako znaků v původním bloku.
    Složitost komprese by mohla být O(n x log_2(n) x n/2).
    Naproti tomu v dekódování se použijí dva nevnořené cykly z nichž jeden obsahuje prohledání části permutovaného bloku. Tedy O(n * log_2(n/2) + n).
    Implementoval jsem a vskutku je dekódování řádově rychlejší a je také paměťově méně náročné.

    Majkl