I have an autocomplete implementation in Python, and it passed all of the unit tests that I have included at the bottom.
#!python
import random
import time
def get_words(filename):
with open(filename, 'r') as f:
words_list = f.read().split()
return words_list
print(words_list)
def binarysearch(list_, item, left=None, right=None):
if left is None and right is None:
left = 0
right = len(list_) - 1
middle = (right + left) // 2
item_length = len(item)
middle_item = list_[middle]
if middle_item[:item_length].lower() == item.lower():
return find_all_words(list_, item, middle)
elif middle_item[:item_length].lower() < item.lower():
return binarysearch(list_, item, middle + 1, right)
elif middle_item[:item_length].lower() > item.lower():
return binarysearch(list_, item, left, middle - 1)
elif left > right:
return None
def find_all_words(list_, item, middle):
predicted_words = [list_[middle]]
item_length = len(item)
left_match = True
right_match = False
left_index = middle
right_index = middle
while left_match:
left_index -= 1
if left_index < 0:
left_match = False
else:
word = list_[left_index]
if word[:item_length] == item:
predicted_words.append(word)
else:
left_match = False
while right_match:
right_index += 1
if right_index >= len(list_):
right_match = False
else:
word = list_[right_index]
if word[:item_length] == item:
predicted_words.append(word)
else:
right_match = False
return predicted_words
def autocomplete(prefix=""):
filename = "/usr/share/dict/words"
words_list = get_words(filename)
predicted_words = binarysearch(words_list, prefix)
return predicted_words
def benchmark(all_prefixes):
t1 = time.time()
for prefix in all_prefixes:
autocomplete(prefix)
t2 = time.time()
return t2 - t1
def main():
all_words = get_words('/usr/share/dict/words')
all_prefixes = set([word[:len(word)//2] for word in all_words])
time = benchmark(all_prefixes)
print('Took {} seconds to benchmark {} prefixes on {} words'.format(time, len(all_prefixes), len(all_words)))
# import sys
# prefix = sys.argv[1]
# words = autocomplete(prefix)
# print(words)
if __name__ == '__main__':
main()
# autocomplete_test.py
#!python
from autocomplete import insert_word
from tries import Trie
import unittest
class TrieTest(unittest.TestCase):
def test_init(self):
trie = Trie()
data, is_word = trie.root.data
assert data == ""
assert is_word is False
assert trie.root.next == {}
def test_insert_with_3_items(self):
trie = Trie()
assert trie.root.data == ('', False)
assert trie.root.next == {}
trie.insert("a")
assert trie.root.next['a'] is not None
assert len(trie.root.next) == 1
node = trie.root.next['a']
assert node.data == ('a', True)
assert node.next == {}
trie.insert("a")
assert trie.root.next['a'] is not None
assert len(trie.root.next) == 1
node = trie.root.next['a']
assert node.data == ('a', True)
assert node.next == {}
trie.insert("b")
assert trie.root.next['b'] is not None
assert len(trie.root.next) == 2
node = trie.root.next['b']
assert node.data == ('b', True)
assert node.next == {}
trie.insert("c")
assert trie.root.next['c'] is not None
assert len(trie.root.next) == 3
node = trie.root.next['c']
assert node.data == ('c', True)
assert node.next == {}
def test_inset_with_7_items(self):
trie = Trie()
words_list = ['a', 'app', 'apple', 'be', 'bee', 'beat', 'c']
for word in words_list:
trie.insert(word)
assert trie.root.data == ('', False)
assert len(trie.root.next) == 3
assert trie.root.next['a'] is not None
node = trie.root.next['a']
assert node.data == ('a', True)
assert len(node.next) == 1
assert node.next['p'] is not None
node = node.next['p']
assert node.data == ('ap', False)
assert len(node.next) == 1
assert node.next['p'] is not None
node = node.next['p']
assert node.data == ('app', True)
assert len(node.next) == 1
assert node.next['l'] is not None
node = node.next['l']
assert node.data == ('appl', False)
assert len(node.next) == 1
assert node.next['e'] is not None
node = node.next['e']
assert node.data == ('apple', True)
assert len(node.next) == 0
assert trie.root.next['b'] is not None
node = trie.root.next['b']
assert node.data == ('b', False)
assert len(node.next) == 1
assert node.next['e'] is not None
node = node.next['e']
assert node.data == ('be', True)
assert len(node.next) == 2
assert node.next['e'] is not None
node1 = node.next['e']
assert node1.data == ('bee', True)
assert len(node1.next) == 0
assert node.next['a'] is not None
node2 = node.next['a']
assert node2.data == ('bea', False)
assert len(node2.next) == 1
assert node2.next['t'] is not None
node = node2.next['t']
assert node.data == ('beat', True)
assert len(node.next) == 0
assert trie.root.next['c'] is not None
node = trie.root.next['c']
assert node.data == ('c', True)
assert len(node.next) == 0
class AutocompleteTest(unittest.TestCase):
def test_insert_word():