https://en.wikipedia.org/wiki/External_sorting
Dne pondělí 15. června 2015 22:36:11 UTC+2 Lumír Balhar napsal(a): > 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 python@py.cz http://www.py.cz/mailman/listinfo/python Visit: http://www.py.cz
