Lab 5: Autocomplete
If you are a current student, please Log In for full access to the web site.
Note that this link will take you to an external site (https://oidc.mit.edu) to authenticate, and then you will be redirected back to this page.
Table of Contents
- 1) Preparation
- 2) Introduction
- 3) Trie class and basic methods
- 4) Autocomplete
- 5) Autocorrect
- 6) Selecting words from a word trie
- 7) Testing your lab
- 8) Code Submission
- 9) Checkoff
This lab assumes you have Python 3.5 or later installed on your machine.
The following file contains code and other resources as a starting point for this lab: lab5.zip
Most of your changes should be made to
lab.py, which you will submit
at the end of this lab. Importantly, you should not add any imports
to the file.
This lab is worth a total of 4 points. Your score for the lab is based on:
- correctly answering the questions on this page (0.5 points)
- passing the test cases from
test.pyunder the time limit (1.5 points), and
- a brief "checkoff" conversation with a staff member to discuss your code (2 points).
For this lab, you will only receive credit for a test case if it runs to completion under the time limit on the server.
The questions on this page (including your code submission) are due at 4pm on Friday, Mar 22. However, you are strongly encouraged to read sections 1-3, and perhaps to get started with trying to implement some of the methods, before lecture on Mar 18.
Type "aren't you" into a search engine and you'll get a handful of search suggestions, ranging from "aren't you clever?" to "aren't you a little short for a stormtrooper?". If you've ever done a web search, you've probably seen an autocompletion — a handy list of words that pops up under your search, guessing at what you were about to type.
Search engines aren't the only place you'll find this mechanism. For example, cell phones use autocomplete/autocorrect to predict/correct words. Some IDEs (integrated development environments — used for coding and software development) use autocomplete to make the process of coding more efficient by offering suggestions for completing long function or variable names.
In this lab, we are going to implement our own version of an autocomplete/autocorrect engine using a tree structure called a trie, as described in this document.
The lab will ask you first to create a class to represent a generic trie data structure. You will then use the trie to write your own autocomplete and autocorrect, as well as a mechanism for searching.
2.1) The Trie Data Structure
A trie1, also known as a prefix tree, is a type of search tree that stores an associative array (a mapping from keys to values). In a trie, the keys are always ordered sequences. The trie stores keys organized by their prefixes (their first characters), with longer prefixes given by successive levels of the trie. Each node optionally contains a value to be associated with that node's prefix.
As an example, consider a trie constructed as follows:
t = Trie() t.set('bat', True) t.set('bar', True) t.set('bark', True)
This trie would look like the following (Fig. 1):
One important thing to notice is that the keys associated with each node are not actually stored in the nodes themselves. Rather, they are stored in the edges connecting the nodes.
We'll start by implementing a class called
Trie to represent tries in Python.
This class will include facilities for adding, deleting, modifying, and
retrieving all key/value pairs. For example, consider:
>>> t = Trie() >>> t.set('bat', True) >>> t.set('bar', True) >>> t.set('bark', True) >>> >>> t.get('bat') True >>> t.get('something') Traceback (most recent call last): ... KeyError >>> >>> t.set('bark', 20) >>> t.get('bark') 20 >>> >>> t.items() [('bat', True), ('bar', True), ('bark', 20)] >>> >>> t.delete('bar') >>> >>> t.items() [('bat', True), ('bark', 20)]
However, we are not limited to using only strings. Your
should (eventually) also support using tuples as keys, for example:
>>> t = Trie() >>> t.set((2, ), 'cat') >>> t.set((1, 0, 0), 'dog') >>> t.set((1, 0, 1), 'ferret') >>> t.set((1, 0, 1, 80), 'tomato') >>> >>> t.get((1, 0)) Traceback (most recent call last): ... KeyError >>> t.get((1, 0, 0)) 'dog' >>> t.items() [((2,), 'cat'), ((1, 0, 0), 'dog'), ((1, 0, 1), 'ferret'), ((1, 0, 1, 80), 'tomato')]
Note that, in terms of functionality, the
Trie class will have
a lot in common with a Python dictionary. However, the representation we're
using "under the hood" has some nice features that make it well-suited for
tasks (like autocompletion) that use prefix-based lookups.
3) Trie class and basic methods
lab.py, you are responsible for implementing the
Trie class, which
should support the following methods.
Hint: you may wish to make sure everything is working for only
first, and then expand to make things work for keys that are
than trying to implement both right from the start.
__init__( self )
selfto be an object with exactly three instance variables:
value, the value associated with the sequence ending at this node. Initial value is
None(we will assume that a value of
Nonemeans that a given key has no value associated with it, not that the value
Noneis associated with it).
children, a dictionary mapping single-element sequences (either length-1 strings or length-1 tuples) to another trie node, i.e., the next level of the trie hierarchy (tries are a recursive data structure). Initial value is an empty dictionary.
type, some way to keep track of the type of the keys (without explicitly storing the entire keys themselves). The exact choice of representation is up to you. This attribute should be set to
Nonewhen the instance is first created, and it should be updated to reflect the type of the keys when the first element is added. You may assume that all keys in a given
Trieinstance are of the same type.
set( self, key, value )
keyto the trie, associating it with the given
value. For the trie node that marks the end of the key, set that node's
valueattribute to be given
valueargument. This method doesn't return a value. If the type of the
keyis not consistent with the key type expected for the trie, a
TypeErrorexception should be raised (see https://docs.python.org/3/reference/simple_stmts.html#raise). Examples (using the trie structure from the picture above):
t = Trie()would create the root node of the example trie above.
t.set('bat', True)adds three nodes (representing the
'bat'prefixes) and associates the value
Truewith the node corresponding to
t.set('bark', True)adds two new nodes for prefixes
'bark'shown on the bottom right of the trie, setting the value of the last node to
t.set('bar', True)doesn't add any nodes and only sets the value of the first node added above when inserting "bark" to
t.set(1, True)raises a
TypeErrorand does not make any change to the trie.
get( self, key )
key. It is expected that the trie node descended from the
selftrie will be located corresponding to
keyand the value associated with that node will be returned, or a
KeyErrorwill be raised if the key cannot be found in the trie. If the type of the key is not consistent with the expected type of keys for this trie, raise a
TypeError. Examples (using the example trie from above):
t.get('apple')should raise a
KeyErrorsince the given key does not exist in the trie.
t.get('ba')should also raise a
KeyErrorsince, even though the key
'ba'is represented in the trie, it has no value associated with it.
t.get(1)should raise a
TypeErrorsince the keys for this trie are expected to be strings, not integers.
delete( self, key )
"bar"from its value in the trie, so that subsequent calls to
contains( self, key )
keyoccurs and has a value other than
Nonein the trie. Hint: At first glance, the code for this method might look very similar to some of the other methods above. Make good use of helper functions to avoid repetitious code! Examples (using the example trie from above):
Falsesince that interior node has no value associated with it.
True(not because the value associated with
True, but because
'bar'has a value associated with it at all).
"barking"can't be found in trie.
items( self )
(key, value)tuples for each key stored in the trie. The pairs can be listed in any order. Hint: You may want to generate this list recursively using the items from child nodes. Examples (using the example trie from above):
t.items()returns a list containing the tuples
('bar', True), and
('bark', True)(in any order).
Now, let's implement our auto-complete engine!
We'll start with implementing autocompletion for words, and then we'll move
to implementing autocompletion for sentences. As a start for either of these,
we'll need a way to build up a
Trie instance from a text document.
textis a string containing a body of text. Return a
Trieinstance mapping words in the text to the frequency with which they occur in the given piece of text.
Note that we have provided a method called
tokenize_sentences which will try
to intelligently split a piece of text into individual sentences. You should use
this function rather than implementing your own. The function takes in a single
string and returns a list of strings, one for each sentence, where punctuation has been
stripped out and the sentence consists only of words. Words within
those sentences are sequences of characters separated by spaces.
textis a string containing a body of text. Return a
Trieinstance mapping sentences (represented as tuples of words) to the frequency with which they occur in the given piece of text.
As a running example, we'll use the following trie (Fig. 2), which could have been
created by calling
make_word_trie("bat bat bark bar"):
Once we have those trie representations, we are ready to go ahead and implement autocompletion! We'll implement autocompletion as a function described below:
autocomplete( trie, prefix, max_count=None )
trieis an instance of
prefixis a string/tuple,
max_countis an integer or
None. Return a list of the
max_countmost-frequently-occurring keys that start with
prefix. In the case of a tie, you may output any of the most-frequently-occurring keys. If there are fewer than
max_countvalid keys available starting with
prefix, return only as many as there are. The returned list may be in any order. If
max_countis not specified, your list should contain all keys that start with
prefixis not in the trie. Raise a
TypeErrorif the given prefix has the wrong type. Examples (using the example trie from above):
autocomplete(t, "ba", 1)returns
autocomplete(t, "ba", 2)might return either
['bat', 'bar'], or
['bar', 'bat']since "bark" and "bar" occur with equal frequency.
autocomplete(t, "be", 1)returns
Your implementation should be agnostic to the type of its inputs (i.e., it should work both on tries/prefixes that are either strings or tuples). Write a few small tests of your own to test this behavior.
You may have noticed that for some words, our autocomplete implementation generates very few or no suggestions. In cases such as these, we may want to guess that the user mistyped something in the original word. We ask you to implement a more sophisticated tool: autocorrect.
In this case, we will only concern ourselves with tries that are made up of words (i.e., we won't concern ourselves with tuples in this case).
autocorrect( trie, prefix, max_count=None )
trieis an instance of
Triewhose keys are strings,
prefixis a string,
max_countis an integer or
None; returns a list of up to
autocomplete, but if fewer than
max_countcompletions are made, suggest additional words by applying one valid edit to the prefix. An edit for a word can be any one of the following:
- A single-character insertion (add any one character in the range "a" to "z" at any place in the word)
- A single-character deletion (remove any one character from the word)
- A single-character replacement (replace any one character in the word with a character in the range a-z)
- A two-character transpose (switch the positions of any two adjacent characters in the word)
edit in trieis True. For example, editing
"the"is valid, but editing
"tze"is not, as "tze" isn't a word. Likewise, editing
"the"is valid, but
"pho"is not because "pho" is not a word in the corpus, although many words beginning with "pho" are. In summary, given a prefix that produces C completions, where C <
max_count, generate up to
max_count- C additional words by considering all valid single edits of that prefix (i.e., corpus words that can be generated by 1 edit of the original prefix) and selecting the most-frequently-occurring edited words. Return a list of suggestions produced by including all C of the completions and up to
max_count- C of the most-frequently-occuring valid edits of the prefix; the list may be in any order. Be careful not to repeat suggested words! If
None(or is unspecified),
autocorrectshould return all autocompletions as well as all valid edits. Example (using the example trie from above):
autocorrect(t, "bar", 3)returns a list containing 'bar', 'bark', and 'bat' since "bar" and "bark" are found by autocomplete and "bat" is valid edit involving a single-character replacement, i.e., "t" is replacing the "r" in "bar".
6) Selecting words from a word trie
It's sometimes useful to select only the words from a trie that match
a pattern. That's the purpose of the
word_filter( trie, pattern )
trieis a trie whose keys are strings, and
patternis a string. Return a list of
(word, freq)tuples for those words whose characters match those of
pattern. The characters in
patternare matched one at a time with the characters in each word stored in the trie. If all the characters in a particular word are matched, the
(word, freq)pair should be included in the list to be returned. The list can be in any order. The characters in
patternare interpreted as follows:
'*'matches a sequence of zero or more of the next unmatched characters in
'?'matches the next unmatched character in
wordno matter what it is. There must be a next unmatched character for
- otherwise the character in the pattern must exactly match the next unmatched character in the word.
"*a*t"matches all words that contain an "a" and end in "t". This would include words like "at", "art", "saint", and "what".
"year*"would match "year," "years," and "yearn," among others (as well as longer words like "yearning").
"year?"would match "years" and "yearn" (but not longer words).
"*ing"matches all words ending in "ing".
"???"would match all 3-letter words.
"?ing"matches all 4-letter words ending in "ing".
"?*ing"matches all words with 4 or more letters that end in "ing".
word_filter(t, "*")returns a list containing the pairs
('bar', 1), and
('bark', 1), i.e., listing all the words in the trie.
word_filter(t, "???")returns a list containing the pairs
('bar', 1), i.e., listing all the 3-letter words in the trie.
word_filter(t, "*r*")returns a list containing the pairs
('bark', 1), i.e., listing all the words containing an "r" in any position.
remodule — you are expected to write your own pattern-matching code. Copying code from StackOverflow is also not appropriate.
7) Testing your lab
As in the previous labs, we provide you with a
test.py script to help you
verify the correctness of your code. We've also included a server you can use
to visualize the outputs of your autocomplete, autocorrect, and word_filter
functions on different corpora. In addition to the test cases for this
week's lab, we'll have you test out your code by running it on an example
of a real public-domain book (courtesy of Project
'resources/corpora' contains text files of public-domain books that
can be used as corpora for generating tries. Feel free to add text files from
Project Gutenberg or elsewhere to this directory for testing. The questions
below will require you to answer them using tries generated from Jane Austen's
Pride and Prejudice.
You can load the text of a corpus file using something like the following code:
with open("filename.txt", encoding="utf-8") as f: text = f.read()
After running this code, the variable
text will be bound to a string
containing the text contained in the
We'll read the contents of these files into Python, use our
make_phrase_trie functions to create the relevant trie structures, and we will
use our autocompletion/autocorrection based on this corpus. You can alternatively
use the server interface to obtain the results of your implemented methods on the
files in the
gre? Enter your answer as a Python list of strings:
'tear'in Pride and Prejudice? Enter your answer as a Python list of strings:
r?c*t? Enter your answer as a Python list of strings:
8) Code Submission
Once you are finished with the code, please come to a tutorial, lab session, or office hour and add yourself to the queue asking for a checkoff. You must be ready to discuss your code and test cases in detail before asking for a checkoff.
You should be prepared to demonstrate your code (which should be well-commented, should avoid repetition, and should make good use of helper functions). In particular, be prepared to discuss:
- How you were able to keep track of the prefix associated with each node without explicitly storing the prefix itself
- The tradeoff between using iteration and recursion when implementing the
- How using your other methods helped in implementing
- How your code for creating edits works.
- How your recursive matching works (without enumerating all words) for the
1Different people have different opinions about whether this data structure's name should be pronounced like "tree" or like "try." It originally comes from the middle syllable of the word "retrieval," which suggests one pronunciation, but some prefer to say it like "try" to avoid confusion with general "tree" structures in programming. Some even say "tree as in try," but that's kind of a mouthful...