Problem Statement Write a program to implement autocomplete for a given set of N

Question

Problem Statement Write a program to implement autocomplete for a given set of N terms, where a term is a query string and an associated nonnegative weight. That is, given a prefix, find all queries that start with the given prefix, in descending order of weight. Autocomplete is pervasive in modern applications. As the user types, the program predicts the complete query (typically a word or phrase) that the user intends to type. Autocomplete is most effective when there are a limited number of likely queries. For example, the Int Movie Database uses it to display the names of movies as the user types; search engines use it to display suggestions as the user enters web search queries; cell phones use it to speed up text input. ernet a beautif All MDbPro A Beautiful Mind (2001) Russell Crowe, Ed Harris A Beautiful Life (2008) Dana Delany, Debi Mazar A Beautiful Soul (2012) Deitrick Haddon, Lesley-Ann Brandt AMER HUS See all results for "a beauyt NAME Breaking M MACHETE Rad American Hustle Traller #1 Breaking Bad Machete Kills Traller #2 "Say My Name" See featured HD Trallers>

Explanation / Answer

import sys
class Node:
def __init__(self):
self.next = {}  
self.word_marker = False
def add_item(self, string):
if len(string) == 0:
self.word_marker = True
return
key = string[0]
string = string[1:]
if self.next.has_key(key):
self.next[key].add_item(string)
else:
node = Node()
self.next[key] = node
node.add_item(string)
def dfs(self, sofar=None):
if self.next.keys() == []:
print "Match:",sofar
return
if self.word_marker == True:
print "Match:",sofar
for key in self.next.keys():
self.next[key].dfs(sofar+key)
def search(self, string, sofar=""):
if len(string) > 0:
key = string[0]
string = string[1:]
if self.next.has_key(key):
sofar = sofar + key
self.next[key].search(string,sofar)
else:
print "No match"
else:
if self.word_marker == True:
print "Match:",sofar
for key in self.next.keys():
self.next[key].dfs(sofar+key)
def fileparse(filename):
fd = open(filename)
root = Node()  
line = fd.readline().strip(' ') # Remove newline characters
while line !='':
root.add_item(line)
line = fd.readline().strip(' ')
return root
if __name__ == '__main__':
if len(sys.argv) != 2:
print "Usage: ", sys.argv[0], "dictionary_file.txt"
sys.exit(2)
root = fileparse(sys.argv[1])
print "Input:",
input=raw_input()
root.search(input)

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.