simple-sentence-parse.py

#!/usr/bin/python

import os
import sys

class Node(object):

    def __init__(self):
        self.is_word = False
        self.children = {}

class Trie(object):

    def __init__(self, words):
        self.root = Node()
        for word in words:
            self.add_word(word)

    def add_word(self, word):
        cur_node = self.root
        for c in word:
            if not c in cur_node.children:
                new_node = Node()
                cur_node.children[c] = new_node
            cur_node = cur_node.children[c]
        cur_node.is_word = True

    def is_word(self, word):
        cur_node = self.root
        for c in word:
            if c not in cur_node.children:
                return False
            cur_node = cur_node.children[c]
        return cur_node.is_word

def parse(sentence, dictionary):
    cur_node = dictionary.root
    cur_word = ""
    possible_words = []
    parses = []

    if sentence == "":
        return [""]

    # Generate a list of all possible words starting at 'sentence'
    for i, c in enumerate(sentence):
        if c not in cur_node.children:
            break
        cur_word += c
        cur_node = cur_node.children[c]
        if cur_node.is_word:
            possible_words.append((i, cur_word))

    # For each parse, try it out
    for i, word in possible_words:
        lookaheads = parse(sentence[i+1:], dictionary)
        if lookaheads:
            parses.extend([word + " " + lookahead for lookahead in lookaheads])

    return parses

if __name__ == "__main__":
    sys.setrecursionlimit(100000)

    sentence = sys.argv[1]
    with open("/usr/share/dict/words") as fin:
        words = [word.strip().lower() for word in fin.readlines()]
    dictionary = Trie(words)
    parses = parse(sentence, dictionary)

    for parse in parses:
        print parse