I am creating a spellchecker where I will accept an input word and then produce a list of words with an edit distance of 1 while checking if these words can be found in the ternary tree I will create. This tree will be made using a list of valid words. Only the functions with ### TODO: YOUR CODE HERE ### can be revised in this code.
valid_words = ['the', 'of', 'and', 'to', 'a', 'in', 'for', 'is', 'on', 'that']
class Node:
def __init__(self, value):
self.left_child = None
self.middle_child = None
self.right_child = None
self.value = value
self.is_end = False
class TernarySearchTree:
def __init__(self):
self.root_node = None
def insert(self, word, node=None):
### TODO: YOUR CODE HERE ###
if len(word) == 0:
return node
head = word[0]
tail = word[1:]
if node is None:
node = Node(head)
if head < node.value:
node.left_child = self.insert(word, node.left_child)
elif head > node.value:
node.right_child = self.insert(word, node.right_child)
else:
if len(tail) == 0:
node.is_end = True
else:
node.middle_child = self.insert(tail, node.middle_child)
return node
def contains(self, word, node=None):
### TODO: YOUR CODE HERE ###
if node is None or len(word) == 0:
return False
head = word[0]
tail = word[1:]
if (head < node.value) :
return self.contains(word, node.left_child)
elif (head > node.value) :
return self.contains(word, node.right_child)
else:
if len(tail) == 0 and node.is_end:
return True
return self.contains(tail, node.middle_child)
class Spellchecker:
def __init__(self, valid_words):
### TODO: YOUR CODE HERE ###
tree = TernarySearchTree()
for word in valid_words:
tree.root_node = tree.insert(word, tree.root_node)
def getNearbyStrings(self, word):
letters = 'abcdefghijklmnopqrstuvwxyz'
splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
deletes = [L + R[1:] for L, R in splits if R]
transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]
replaces = [L + c + R[1:] for L, R in splits if R for c in letters]
inserts = [L + c + R for L, R in splits for c in letters]
return list(set(deletes + transposes + replaces + inserts))
def make_suggestions(self, word):
### TODO: YOUR CODE HERE ###
nearby_strings_list = self.getNearbyStrings(word)
edit_distance1_list = []
tree = TernarySearchTree()
for i in nearby_strings_list:
if (tree.contains(i, tree.root_node)):
edit_distance1_list.append(i)
return edit_distance1_list
spellchecker = Spellchecker(valid_words)
output = spellchecker.make_suggestions(input())
output.sort()
for word in output:
print(word)
My problem concerns the make_suggestions function. I was able to create a tree using spellchecker = Spellchecker(valid_words), but how can I assign the contents of this to an object belonging to the class TernarySearchTree, so that I can call the contains function from that class? make_suggestions checks if a word is in the tree and will append it to a list that it will return.
class Spellchecker: def __init__(self, valid_words): # […] tree = TernarySearchTree() for word in valid_words: tree.root_node = tree.insert(word, tree.root_node) # […] def make_suggestions(self, word): # […] nearby_strings_list = self.getNearbyStrings(word) edit_distance1_list = [] tree = TernarySearchTree() for i in nearby_strings_list: if (tree.contains(i, tree.root_node)): edit_distance1_list.append(i) return edit_distance1_list
In make_suggestions, you shouldn't create another TernarySearchTree. You have already created one in __init__ and it already contains the valid words.
In __init__ you should assign this tree as an instance variable so that you can then use it from make_suggestions.
Something like:
class Spellchecker:
def __init__(self, valid_words):
# […]
tree = TernarySearchTree()
for word in valid_words:
tree.root_node = tree.insert(word, tree.root_node)
self.tree = tree # add this
# […]
def make_suggestions(self, word):
# […]
nearby_strings_list = self.getNearbyStrings(word)
edit_distance1_list = []
tree = self.tree # use this instead of creating a new one
for i in nearby_strings_list:
if (tree.contains(i, tree.root_node)):
edit_distance1_list.append(i)
return edit_distance1_list