Zas taková sranda to teda není. Teprve až jsem si přečetl, jak se to rekonstruuje, dokázal jsem si odvodit, proč to se to tímto způsobem zrekonstruuje. Nakonec je to jednoduchý, ale nechápu, jak to mohlo někoho napadnout.
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.
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.
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.
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 ;-)
