Parsing a list of words into a tree

Question

I have a list of words. For example:

reel
road
root
curd

I would like to store this data in a manner that reflects the following structure:

Start -> r -> e -> reel
           -> o -> a -> road
                   o -> root
         c -> curd

It is apparent to me that I need to implement a tree. From this tree, I must be able to easily obtain statistics such as the height of a node, the number of descendants of a node, searching for a node and so on. Adding a node should 'automatically' add it to the correct position in the tree, since this position is unique.

It would also like to be able to visualize the data in the form of an actual graphical tree. Since the tree is going to be huge, I would need zoom / pan controls on the visualization. And of course, a pretty visualization is always better than an ugly one.

Does anyone know of a Python package which would allow me to achieve all this simply? Writing the code myself will take quite a while. Do you think http://packages.python.org/ete2/ would be appropriate for this task?

I'm on Python 2.x, btw.

---

I discovered that NLTK has a trie class - nltk.containers.trie. This is convenient for me, since I already use NLTK. Does anyone know how to use this class? I can't find any examples anywhere! For example, how do I add words to the trie?

Answer 1

I think the following example does pretty much what you want, using the ETE toolkit.

from ete2 import Tree

words = [ "reel", "road", "root", "curd", "curl", "whatever","whenever", "wherever"]

#Creates a empty tree
tree = Tree()
tree.name = ""
# Lets keep tree structure indexed
name2node = {}
# Make sure there are no duplicates
words = set(words)
# Populate tree
for wd in words:
    # If no similar words exist, add it to the base of tree
    target = tree

    # Find relatives in the tree
    for pos in xrange(len(wd), -1, -1):
        root = wd[:pos]
        if root in name2node:
            target = name2node[root]
            break

    # Add new nodes as necessary
    fullname = root 
    for letter in wd[pos:]:
        fullname += letter 
        new_node = target.add_child(name=letter, dist=1.0)
        name2node[fullname] = new_node

        target = new_node

# Print structure
print tree.get_ascii()
# You can also use all the visualization machinery from ETE
# (http://packages.python.org/ete2/tutorial/tutorial_drawing.html)
# tree.show()

# You can find, isolate and operate with a specific node using the index
wh_node = name2node["whe"]
print wh_node.get_ascii()

# You can rebuild words under a given node
def recontruct_fullname(node):
    name = []
    while node.up:
        name.append(node.name)
        node = node.up
    name = ''.join(reversed(name))
    return name

for leaf in wh_node.iter_leaves():
    print recontruct_fullname(leaf)


                    /n-- /e-- /v-- /e-- /-r
               /e--|
     /w-- /h--|     \r-- /e-- /v-- /e-- /-r
    |         |
    |          \a-- /t-- /e-- /v-- /e-- /-r
    |
    |     /e-- /e-- /-l
----|-r--|
    |    |     /o-- /-t
    |     \o--|
    |          \a-- /-d
    |
    |               /-d
     \c-- /u-- /r--|
                    \-l

Answer 2

ETE2 is an environment for tree exploration, in principle made for browsing, building and exploring phylogenetic trees, and i've used it long time ago for these purposes. But its possible that if you set your data properly, you could get it done.

You just have to place paretheses wherever you need to split your tree and create a branch. See the following example, taken from ETE doc. If you change these "(A,B,(C,D));" for your words/letters it should be done.

from ete2 import Tree
unrooted_tree = Tree( "(A,B,(C,D));" )
print unrooted_tree

output:

     /-A
    |
----|--B
    |
    |     /-C
     \---|
          \-D

...and this package will let u do most of the operations you want, giving u the chance to select every branch individually, and operating with it in an easy way. I recommend u to give a look to the tutorial anyway, not pretty difficult :)