2015-06-15 22:36 GMT+02:00 Lumír Balhar <[email protected]>:
> 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.
Ahoj,
sort() používá jen operátor "<", takže stačí naimplementovat ten (i
když s functools.total_ordering [0] není problém naimplementovat ty
ostatní).
Jen je potřeba mít objekt pro každý řádek. Když takový objekt obsahuje
jen odkaz na původní řetězec, a číslo řádku, tak se ti snad všechny do
paměti vejdou.
Přikládám nástin toho, jak bych to řešil já (v py3).
(Jestli se vyplatí při porovnávání generovat oba řádky a porovnat ty,
nebo jako já porovnávat jednotlivé znaky v Pythonu, záleží na tom jak
často ty řetězce mají dlouhé shodné prefixy.)
[0] https://docs.python.org/3/library/functools.html#functools.total_ordering
class RotatedString:
__slots__ = ['orig_string', 'n']
def __init__(self, orig_string, n):
self.orig_string = orig_string
self.n = n
def __len__(self):
return len(self.orig_string)
def __str__(self):
return self.orig_string[self.n:] + self.orig_string[:self.n]
def __iter__(self):
yield from self.orig_string[self.n:]
yield from self.orig_string[:self.n]
def __getitem__(self, i):
return self.orig_string[(self.n + i) % len(self.orig_string)]
def __lt__(self, other):
if self.orig_string != other.orig_string:
return self.orig_string < other.orig_string
for c1, c2 in zip(self, other):
if c1 != c2:
return c1 < c2
base = 'ema má maso'
for rs in sorted([RotatedString(base, i) for i, c in enumerate(base)]):
print(rs)
_______________________________________________
Python mailing list
[email protected]
http://www.py.cz/mailman/listinfo/python
Visit: http://www.py.cz
