[python] Trie

[Jan Jakubuv]

dobry den,

pokud jde ciste o redukovani prostoru muzete soubor jednoduse zkomprimovat.

pokud si ovsem chcete zachovat moznost rychleho vyhledavani a pristupu
k souboru zkuste nejprve analyzovat behem vypoctu strukturu trie,
abyste jste zjistil co je pricinou velkych pametovych pozadavku.
problem muze byt v implementaci nebo napr. v tom, ze vstupni data
nemusi byt vhodna pro pouziti trie (prilis malo spolecnych predpon,
prilis mnoho dlouhych rozdilnych pripon, ...). v tom pripade muzete
zkusit jinou datovou strukturu napr. komprimovane trie (compressed
trie) (nebo jestli pomuze napr. toto
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/) .
zkuste se take poohlednout po nejake vhodne implementaci v Pythonu.
podtrzeno secteno bych Vam doporucil komprimovane trie.

obecne pokud ma vstupni soubor 80MB tak se nedivte ze se pouzita pamet
splha ke 100MB. pokud vsechny pristupy selzou poridte si vetsi
vypocetni kapacitu ;-) muj odhad je ze na zpracovani 80MB souboru bude
potrebovat mnohem vic pameti nez je 80MB..

s pozdravem,
  honza.


2007/4/13, Pepa Hajek <PepaHajek na seznam.cz>:
> DD,
> snazim se ulozit slovnik ze souboru (cca 6milionu slov - soubor ma asi 80MB, kazde zvlast na kazdem radku), do struktury Trie (co pismeno, to uzel - spolecne prefixy slov). Cilem je redukovat pametovy prostor zabrany vlastnim slovnikem.
> At se vsak problem snazim vyresit jakkoli, stale narazim na nedostatek pameti. Zkousel jsem jiz vnorene seznamy, slovniky a naposledy strukturu, neco ve smyslu:
> <pre>
> class TNode:
>         term, subNodes, data = None, (), None
>
>         def __init__(self, data):
>                 self.data=data          #vlastni pismeno
>                 self.subNodes=()        #ntice poduzli
>                 self.term=None          #ukoncovaci terminal
>
> class tri:
>         #############################
>         def __init__(self):
>                 """
>                 Inicializace
>                 """
>                 self.root=self.addNode('#')
>
>         ############################
>         def add(self, word):
>                 """
>                 Prida slovo do slovniku
>                 """
>                 curNode=self.root
>                 for letter in word:
>                         notInTree=True
>                         for i in curNode.subNodes:
>                                 if i.data==letter:
>                                         notInTree=False
>                                         index=i
>                                         break
>                         if notInTree:
>                                 temp=list(curNode.subNodes)
>                                 temp.append(self.addNode(letter))
>                                 curNode.subNodes=tuple(temp)
>                                 index=curNode.subNodes[-1]
>                         curNode=index
> </pre>
>
> Ovsem i pri pouziti teto struktury, nactu-li vice nez 350 000 slov tak se pamet zabrana programem vysplha na nejakych cca 100MB.
>
> Napadlo by nejake vhodne efektivni reseni?
>
> Dekuji za odpoved
>
> P. H.
> _______________________________________________
> Python mailing list
> Python na py.cz
> http://www.py.cz/mailman/listinfo/python
>
>