2 ms·
The original article uses Java, which makes it harder to see how simple it can be to make and use prefix trees. For comparison, here's the Python code to create
by tmoertel 13y ago
The original article uses Java, which makes it harder to see how simple it can be to make and use prefix trees. For comparison, here's the Python code to create a prefix tree from a set of words:
def prefix_tree(words):
d = dict()
for word in words:
root = d
for c in word:
root = root.setdefault(c, {})
root['$$'] = {} # mark end of word with '$$' token
return d
For example:
>>> prefix_tree('foo bar baz'.split())
{'b': {'a': {'r': {'$$': {}},
'z': {'$$': {}}}},
'f': {'o': {'o': {'$$': {}}}}}
To query whether a word is present in a tree you basically compute
reduce(dict.__getitem__, word, tree)
and test whether the result (a forest) has an end-of-word '$$' tree.