Ahoj všem.
Řeším s kamarádem jeden jeho projekt, jehož součástí je i Burrows-Wheelerova
transformace, která se používá před kompresí dat společně s Move to Front
transformací pro snížení entropie vstupních dat a tím zvýšení efektivity
kompresního algoritmu, kterému tyto dvě transformace předcházejí.
Pochopení transformací není potřeba. U BWT se využívá tzv, buffer, který
obsahuje všechny možné rotace vstupních dat, takže například pro "ema má maso"
vypadá takto:
0 ema ma maso
1 ma ma masoe
2 a ma masoem
3 ma masoema
4 ma masoema
5 a masoema m
6 masoema ma
7 masoema ma
8 asoema ma m
9 soema ma ma
10 oema ma mas
Pro malá data je to dobré, ale pro velká nelze mít celý buffer v paměti,
protože se pro každý vstupní znak navíc rozšíří o řádek i sloupec zároveň.
Napsal jsem tedy pro Buffer samostatnou třídu, kde pomocí __getitem__
vygeneruji potřebný řádek posunem až ve chvíli, kdy je jeho obsah potřeba.
Základní buffer jsem tím vyřešil a ušetřil hromadu paměti. Problém ale je, že v
dalším kroku potřebuji tento buffer lexikograficky seřadit. Abych jej opět
nemusel cpát do paměti, vytvořil jsem pole indexů, kde každý index reprezentuje
jeden řádek bufferu a řadím jen toto pole (čímž získám přeskládané pořadí řádků
původního bufferu), ale jako klíč používám právě obsah řádku pro daný index.
Konkrétně:
class Buffer():
def __init__(self, input):
self.input = input
self.indexes = [x for x in range(len(input))]
def __getitem__(self, index):
return self.input[index:] + self.input[0:index]
def sort(self):
self.indexes.sort(key=lambda x: self[x])
A teď jsme se dostali k jádru problému. I když se obsah jednotlivých řádků
generuje až ve chvíli, kdy jsou potřeba, a řadit by se mělo jen relativně malé
pole indexů, při volání funkce .sort() se jakoby stejně celé to pole nejdříve
vytvoří v paměti, seřadí a pak se seřadí to cílové pole s indexy na základě
obsahu bufferu.
Existuje způsob, jak implementovat takovýto řadící algoritmus pro velký objem
dat, aniž bych je měl v jednu chvíli všechny v paměti?
Předem díky za nakopnutí tím správným směrem.
Lumír
_______________________________________________
Python mailing list
[email protected]
http://www.py.cz/mailman/listinfo/python
Visit: http://www.py.cz
