[python] Trie

Pepa Hajek PepaHajek na seznam.cz
Pátek Duben 13 18:14:22 CEST 2007


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.


Další informace o konferenci Python