[python] Trie

[filyph]

Ahoj,
presne o niečo podobné som sa zaujímal. Mohol by ti pomôcť modul pytst
http://www.python.org/pypi/pytst/1.14, v ktorom sa dá vyrobiť v pamäti
štruktúra trie a navonok sa javí skoro ako pythonovský dict, ale dajú
sa z neho napríklad vyberať podstromy ak som dobre čítal, lebo som ho
v praxi ešte nepoužil.
Riešenie cez triedy, vnorené zoznamy (list, dict, tuple) je veľmi
neefektívne. A už vôbec neuvažuj, že by si taký strom uložil cez
pickle. Aj XML je v tomto prípade výhodnejšie.
Ďalšie riešenie môže byť pomocou modulu ctypes, kde si vytvoríš
vlastnú štruktúry pre uzly ako v C.
Alebo iná možnosť by bola vytvoriť triu do stringu chápaného len ako
lineárnu pamäť a naprogramovať si nízkoúrovňové funkcie na prístup ku
nim. Teda niečo ako vlastnú správu pamäte.

Ak potrebuješ iba zisťovať prítomnosť slov v slovníku hodí s na to typ
set alebo frozenset, ktoré sú v pythone 2.5 optimalizovanejšie (v
predchádzajúcich verziách boli nadstavbou slovníka dict) asi takto:

mnozina = set()
for slovo in file('milionyslov.txt','r').xreadlines():
   mnozina.add(slovo[:-1]) # bez znaku konca riadku

# alebo jednoriadkovo
mnozina = frozenset(map(lambda x:x[:-1], file('milionyslov.txt')))

# potom uz len zistujes pritomnost slova v mnozine slov
if 'ahoj' in mnozina:
   print 'ahoj je v slovniku'

Pepa Hajek napsal:
> 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:
> 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?