[python] Paměťově náročné řazení

[Lumír Balhar]

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