I’ll trie in python

In Koble the auto-completion of thing-names used for wiki-editting, instant-search and adding relations  is getting slower and slower, mainly because I do:

result=[]
things=listAllThings()
for t in things:
   if t.startswith(key): res.append(t)
for t in things:
   if key in t: res.append(t)

Going through the list twice makes sure I get all things that match well first (i.e. the start with the string I complete for), and then things matching less well later (they only contain the string).

Of course the world has made up a far better data-structure for indexing prefix’es of string, namely the trie, or prefix tree. James Tauber had already implemented one in python, and kindly made it available. His version didn’t do everything I needed, so I added a few methods. Here is my updated version:

http://gromgull.net/2009/11/trie.py

Enjoy!

 

Post a comment.