Názory k článku Unixová komprese v praxi: Bzip2
-
Článek je starý, nové názory již nelze přidávat.
-
Martin Mareš (neregistrovaný)
Také mi není úplně jasné, jak na to pánové Burrows a Wheeler přišli - inverzní transformace sice na první pohled vypadá triviálně, ale když si uvědomíte, že se jeden znak může v souboru objevit i vícekrát :), začne jít do tuhého. Konec konců právě proto se inverzní BWT objevila jako úloha v letošním ročníku matematické olympiády - vzorové řešení najdete na http://mo.mff.cuni.cz/p/52/reseni-2.html#P-II-3 a jednodušší verzi s jedním výskytem znaku na lynx http://mo.mff.cuni.cz/p/52/reseni-1.html#P-I-3
.
Ale ani provést dopřednou transformaci efektivně není snadné - jde to totiž v čase lineárním s délkou transformovaného textu. -
Yeti (neregistrovaný)
Jak to popisují v PO, to se mi teda nepřijde moc jasný. Já si to nejlíp představím takhle:
1. Řetězce se berou jako cyklické (a tímpádem sloupce i matice), EOB se řeší samostatně (zapamatuji si posici nebo zapíšu EOB jako speciální znak).
2. Mám-li nějaký blok sloupců k, k+1, ..., k+m-1 v té setříděné matici, a setřídím je, dostanu sloupce 1, 2, ..., m. To je hlavní myšlenka, třídění nic nerozháže, ale posune mě na první sloupec.
No, a to je vlastně všechno ;-) Protože to funguje skrz okraj matice, tj. první a poslední sloupec na sebe navazují, tak vezmu už známé sloupce 1, 2, ..., k (lze začít od k=0); dopíšu před ně poslední sloupec, který znám, protože to jsou ta komprimovaná data, setřídím a dostanu sloupce 1, 2, ..., k, k+1. -
KLON (neregistrovaný)
Odvození není jednoduché, protože vyžaduje jistý matematický potenciál.
Dovolím si ukázat zpětný chod bez třízení v O(N).
Projdu vzorek a spočtu výskyty jednotlivých znaků. O(N)
Projdu znovu a přiřadím každé pozici číslo podle vzoce #výskyt_znaku + Suma(#celkem_výskytů_znaku_mensich_nez_tento) O(N)
Tímto získám cyklickou permutaci, kterou projdu od naslédníka zapamatované pozice v setřízení. O(n)
Pameti to zabere pocty výskytů 256 * 4 + pole permutace N * 4. -
Yeti (neregistrovaný)
Odvození podle mě nevyžaduje matematický potenciál ale nápad. No budiž.
Že třídění sekvence prvků z konečné množiny je O(n) a spočívá ve spočítání, kolikrát se který prvek vyskytuje, to nikoho neudiví, a třídění tímpádem provádíte, jen ho tak nenazýváte. Že je ten algoritmus mnohem lepší, protože třídí jen jednou a vypočítá výslednou permutaci rovnou, ne n-násobným tříděním, takže je O(n), to samozřejmě nepopírám. Jestli je názornější na pochopení, to teda nevím, přijde mi, že zatímco na celých maticích je to zřejmé (pokud má člověk ten nápad), tady už bych tvrzení, že je to zřemé, za důkaz nepovažoval ;-) -
Yeti (neregistrovaný)
Asi sloupec, ne řádek, předpokládám, protože řádky obsahují jen cyklické translace toho řetězce.
A ten důvod je jednoduchý: první sloupec neumožňuje zrekonstruovat tu permutaci ;-) Jak chcete z setříděného seznamu říci, jaké bylo původní pořadí prvků? Jestli mi něco neuniklo, tak poslední sloupec je jediný, který umožňuje rekonstrukci sám o sobě. -
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? -
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. -
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
-
Lukas Kunc (neregistrovaný)
Nejak mi neni jasne, proc by v poslednim sloupci mel byt vetsi vyskyt retezcu stejnych pismen nez v puvodnim slove. Dovedete to nekdo zduvodnit ? Taky mi neni jasne - bere se jako vstup pro kompresi vzdycky posledni sloupec, nebo se vybira pokazde jiny ? Jeste jsem nedelal ten domaci ukol, takze se omlouvam za dotaz. Odpoved na nej z nej mozna mela vyplynout ? :-)
ČLÁNKY DO MAILU