News for hackers. Stuff that matters.
Re:The Trie: A Neglected Data Structure by tmoertel on Friday September 13, 2013 @12:41PM (#6381556)
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.

There are no comments on this comment yet.