Dotaz: Trie v pythonu

[Pepa]

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:

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

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? Jenom doplnim ze s pythonem vice mene zacinam, ale s timto problemem jsem stravil uz mnoho drahoceneho casu, tak mne to nedalo abych se nezeptal.

Dekuji za odpoved

Pepa H.

Odpovědi

[Pavel Stárek]

Možná by bylo vhodnější ten soubor naimportovat do nějaké databáze - například sqlite. Popisky a návody například http://www.devshed.com/c/a/Python/Using-SQLite-in-Python/ a o samotné sqlite http://www.root.cz/clanky/sqlite-ultra-lehke-sql/ .

[8an]

Obávám se že režie Pythonu na objekt a seznamy v něm bude mnohem větší než kolik tím můžeš ušetřit. Trie má smysl pro rychlejší vyhledávání (i když i to je sporné), ne pro úsporu paměti. Pro tohle by se asi hodil indexsekvenční soubor (bloky např. po 4kB, a pamatuješ si interval slov v každém bloku), ale kolik to má jako normální Pythonovský slovník? 100MB paměti dneska nic není...

[Tom.š Ze.le.in]

AFAIK trie smysl pro zkompaktnění dat má - viz TAOCP, třetí díl a TeX the Program od par. 919.

Prostorově efektivní implementaci jsem dělal (v jiném jazyce, nevím zda to jde v Pythonu) tak, že jsem alokoval dostatečně velké pole znakú, a s ním pak pracoval přímo pomocí indexu. Tím by se měl minimalizovat overhead jazyka. Po kompaktifikaci lze pole zmenšit na potřebné minimum.

Doporučuji se podívat na ten zdroják TeXu - je to myslím stáhnutelné (tex.web) a docela dokumentované. Tvorba trie tabulky je od par. 942.