CFI 2013 Jan 22 - Tries and a system to recommend completions for words Prefix tries don't seem to come up much for me, but its nice to play with them. The biggest advantage I see to tries is the structural sharing aspect - you can represent a set of string-like data without having to repeat the shared pieces, so if your data plays nicely and ha…

gistfile1.txt

class Node:
  def __init__(self):
        	self.terminal = False
		self.suffixes = {}

def update(node, suffix):
	for c in suffix:
		if c not in node.suffixes:
			node.suffixes[c] = Node()
		node = node.suffixes[c]
	node.terminal = True

def find(node, prefix):
	for c in prefix:
		if c not in node.suffixes:
			return None
		node = node.suffixes[c]
	return node

def collect(res, prefix, node):
	if node.terminal:
		res.append(prefix)
	for c, n in node.suffixes.items():
		collect(res, prefix + c, n)

def completions(node, prefix):
	res = []
	node = find(node, prefix)
	if node:
		collect(res, prefix, node)
	return res

root = Node()

for word in file('/usr/share/dict/words'):
	update(root, word.strip())

while True:
	word = raw_input("enter prefix> ")
	if not word:
		break
	print completions(root, word)