CSCI 136 - Spring 2026

Data Structures

Home | Lectures | Labs | Handouts | CS@Williams

Lab 8: Super Lexicon

Virtually all modern word processors contain a feature to check the spelling of words in documents. More advanced word processors also provide suggested corrections for misspelled words. In this lab, you will be taking on the fun and challenging task of implementing a basic spelling corrector. You are to implement a highly-efficient Lexicon class. This lab has optional assignments that implement additional functionality like finding spelling corrections for misspelled words.

The assignment has several purposes:
  • To gain further skill with recursion in managing a recursive tree structure and exploring it efficiently
  • To explore the notion of a layered abstraction where one class (Lexicon) makes use of other classes (e.g., Iterator, ArrayList) as part of its internal representation.

The Lexicon Interface

Your first task is to write a basic class that implements the Lexicon interface. The Lexicon interface describes the functionality necessary to support required operations that include:

• Add a word to the lexicon
• Remove a word from the lexicon
• Determine whether the lexicon contains a given word
• Determine whether the lexicon contains any words with a given prefix
• Read words from a file, adding them to the lexicon
• Provide an iterator for the words in the lexicon

and, if you're keen, the optional operations

• List all words that are "close to" a given word (defined below)
• Find all words that match a given pattern (defined below)

Lexicon.java has extensive comments (not javadoc comments—they're more expository) to help get an idea of what each method should look like. You should add javadoc comments to the corresponding methods in LexiconTrie.java. The comments in Lexicon.java will probably be very helpful for creating these javadoc comments.

Historical Footnote: Back in the ancient times, cell-phones lacked the memory and processsing power necessary to support the elaborate text messaging apps found on modern smartphones. Instead of auto-completing words based on a message's content or correcting a message's grammar mistakes, the "spell-checking" functionality was limited. In this lab, you'll get a chance to build a lexicon yourself to see the kind of specialized and highly-efficient data structures that were used in its implementation.

You should implement the Lexicon interface in a file called LexiconTrie.java. This class will use the LexiconNode class, which you are responsible for designing and implementing. The following methods are in the Lexicon interface.

      public interface Lexicon {
          boolean addWord(String word);
          boolean removeWord(String word);
          boolean containsWord(String word);
          boolean containsPrefix(String prefix);
          int addWordsFromFile(String filename);
          int numWords();
          Iterator<String> iterator();
          Set<String> suggestCorrections(String target, int maxDistance);
          Set<String> matchRegex(String pattern);
      }
    

Most of the method behaviors can be inferred from their names and return types. For more information about the usage and purpose of these methods, refer to the comments in the starter code.

The addWordsFromFile(String filename) method requires reading input in from a file. This can be done with the File class. After setting up a Scanner as follows for a file with name filename, the scanner can be used as normal to obtain the contents of the file (i.e. with sc.hasNextLine() and sc.nextLine()):

       Scanner sc = new Scanner(new File(filename));
    

Note that to make this work, we needed to include the statement import java.io.*;. You should put the above Scanner declaration in a try/catch block (since new File(filename) throws an exception if a file with name filename is not found). The exception you want to catch is a FileNotFoundException.

Implementing the Lexicon as a Trie

There are several different data structures you could use to implement a lexicon: a sorted array, a linked list, a binary search tree, and many others. Each of these offers tradeoffs between the speed of word and prefix lookup, the amount of memory required to store the data structure, the ease of writing and debugging the code, the performance of add/remove, and so on. The implementation we will use is a special kind of tree called a trie (pronounced "try"), designed for just this purpose.

A trie is a letter-tree that efficiently stores strings. A node in a trie represents a letter. A path through the trie traces out a sequence of letters that represent a prefix or word in the lexicon.

Instead of just two children as in a binary tree, each trie node has potentially 26 child references (one for each letter of the alphabet). Whereas searching a binary search tree eliminates a single subtree of words with each left or right turn, a search in a trie follows the child reference for the next letter, which narrows the search to just words starting with that letter. For example, from the root, any words that begin with "n" can be found by following the reference to the "n" child node. From there, following "o" leads to just those words that begin with "no" and so on, recursively. If two words have the same prefix, they share that initial part of their paths. This saves space since there are typically many shared prefixes among words. Each node has a boolean isWord flag which indicates that the path taken from the root to this node represents a complete word. Here's a conceptual picture of a small trie:

The thick border around a node indicates that its isWord flag is true. This trie contains the words: a, are, as, new, no, not, and zen. Strings such as ze or ar are not valid words for this trie because the path for those strings ends at a node where isWord is false. Any path not drawn is assumed to not exist, so strings such as cat or astronaut are not valid because there is no such path in this trie.

Managing Node Children

For each node in the trie, you need a list of children nodes. In the sample trie drawn above, the root node has three children, one each for the letters A, N, and Z. One possibility for storing the children is a statically-sized 26-member array of nodes, where array[0] is the child for A, array[1] refers to B, ... and array[25] refers to Z. When there is no child for a given letter, (such as from Z to X) the array entry would be null. This arrangement makes it trivial to find the child for a given letter:you simply access the correct element in the array by letter index.

However, for most nodes within the trie, very few of the 26 references are needed, so using a largely null 26-member array is much too memory-intensive (i.e., it wastes a lot of space). Better alternatives would be a dynamically-sized array which can grow and shrink as needed (i.e., an ArrayList), or a linked list of children nodes. We leave the final choice of a space-efficient design up to you, but you should justify the choice you make (briefly) in your program comments. Two things you may want to consider:

• there are at most 26 children, so even a O(N) List operation to find a particular child is O(1), and
• trie operations such as iteration require traversing the words in alphabetical order, so keeping the list of children nodes sorted by letter will be advantageous.

Developing an Implementation Strategy

Begin implementing your trie by constructing a LexiconNode class. LexiconNodes should be comparable, so make sure to implement the Comparable interface. Be sure to incrementally compile and test this code.

Create a constructor in LexiconTrie that creates an empty LexiconTrie to represent an empty word list. Test your constructor using Main.java.

Provided in the starter repository is a class called Main.java, which provides a command-line based user interface. You can use this class to test your LexiconTrie as you incrementally develop it. A suggested order of implementation is reflected below. The file README.md contains instructions on how to use Main.java.

Adding Words

Adding a new word into the trie with addWord is a matter of tracing out its path starting from the root, as if searching. If any part of the path does not exist, the missing nodes must be added to the trie. Lastly, the isWord flag is turned on for the final node. In some situations, adding a new word will necessitate adding a new node for each letter, for example, adding the word dot to our sample trie will add three new nodes, one for each letter. On the other hand, adding the word news would only require adding an s child to the end of existing path for new. Adding the word do after dot has been added doesn't require any new nodes at all; it just sets the isWord flag on an existing node to true. Here is the sample trie after those three words have been added:

Suggestion:At this point, you might consider whether it would be helpful to be able to print out some kind of representation of your LexiconTrie to ensure that it has the contents and structure you intend it to have!

Searching for Words and Prefixes

Searching the trie for words and prefixes using containsWord and containsPrefix is a matter of tracing out the path letter by letter. Let's consider a few examples on the sample trie shown previously. To determine if the string new is a word, start at the root node and examine its children to find one pointing to n. Once found, recurse on matching the remainder string ew. Find e among its children, follow its reference, and recurse again to match w. Once we arrive at the w node, there are no more letters remaining in the input, so this is the last node. The isWord field of this node is true, indicating that the path to this node is a word contained in the lexicon.

Alternatively, search for ar. The path exists and we can trace our way through all letters, but the isWord field on the last node is false, which indicates that this path is not a word. (It is, however, a prefix of other words in the trie). Searching for nap follows n away from the root, but finds no a child leading from there, so the path for this string does not exist in the trie and it is neither a word nor a prefix in this trie (containsWord and containsPrefix both return false).

All paths through the trie eventually lead to a valid node (a LexiconNode where isWord has value true). Therefore determining whether a string is a prefix of at least one word in the trie is simply a matter of verifying that the path for the prefix exists.

Removing Words

The first step to removing a word with removeWord is tracing out its path and turning off the isWord flag on the final node. However, your work is not yet done because you should remove any node along that path that no longer leads to a word. The removal of such nodes is left as an optional extension, described in the next paragraph. For this lab, you only need to update the isWord flag for full credit.

Optional extension (Extra Credit). All paths in the trie must eventually lead to a word. If the word being removed was the only valid word along this path, the nodes along that path should be deleted from the trie along with the word. For example, if you removed the words zen and not from the trie shown previously, you should have the result below.

Deleting unneeded nodes requires care because of the recursive nature of the trie. Think about how we removed the last element of a SinglyLinkedList. We had to maintain a reference to the second to last element to update the references appropriately. The situation is similar here.

As a general observation, there should never be a leaf node whose isWord field is false. If a node has no children and does not represent a valid word (i.e., isWord is false), then this node is not part of any path to a valid word in the trie and such nodes should be deleted when removing a word. In some cases, removing a word from the trie may not require removing any nodes. For example, if we were to remove the word new from the above trie, it turns off isWord but all nodes along that path are still in use for other words.

Important note: when removing a word from the trie, the only nodes that may require removal are nodes on the path to the word that was removed. It would be extremely inefficient to check additional nodes that are not on the path.

Other Required Trie Operations

There are a few remaining odds and ends to the trie implementation:

• You need to keep track of the total number of words stored in the trie.
• You should add support for reading words from a file using a Scanner (see the section on The Lexicon Interface above).
• Creating an iterator to traverse the trie involves a recursive exploration of all paths through the trie to find all of the contained words. Remember that it is only words (not prefixes) that you want to operate on and that the iterator needs to dispense the words in alphabetical order. We suggest the following approach—it's easy, although a little space inefficient. First, use one of the data structures we've seen in the course; add all of the words in the trie to this data structure one by one. Then, return an iterator for this data structure.

Optional Extensions (Extra Credit)

Once you have a working lexicon and iterator method, you're ready to implement snazzy spelling correction features. In addition to the previously mentioned removal of nodes that are no longer parts of words, there are two additional extensions that you could attempt to implement. These extensions are "just for fun" and do not affect your lab grade. They are the two Lexicon member functions for suggesting simple corrections and for regular expressions matching:

• Set<String> suggestCorrections(String target, int maxDistance);
• Set<String> matchRegex(String pattern);

Sets are basically just fancy List data structures that do not allow duplicates. Check out the javadocs on Set (an interface requiring Set operations), and HashSet (a specific data structure implementing the Set operations—you do not need to know how it works, or what a Hash is) for more information.

Suggesting Corrections:

First consider the member function suggestCorrections. Given a (potentially misspelled) target string and a maximum distance, this function gathers the set of words from the lexicon that have a distance to the target string less than or equal to the given maxDistance. We define the distance between two equal-length strings to be the total number of character positions in which the strings differ. For example, "place" and "peace" have distance 1, "place" and "plank" have distance 2. The returned set contains all words in the lexicon that are the same length as the target string and are within the maximum distance.

For example, consider the original sample trie containing the words a, are, as, new, no, not, and zen. If we were to call suggestCorrections with the following target string and maximum distance, here are the suggested corrections:

For a more rigorous test, we also provide the word file ospd2.txt, which lists all of the words in the second edition of the Official Scrabble Player's Dictionary. Here are a few examples of suggestCorrections run on a lexicon containing all the words in ospd2.txt:

Finding appropriate spelling corrections will require a recursive traversal through the trie gathering those "neighbors" that are close to the target path. You should not find suggestions by examining each word in the lexicon and seeing if it is close enough. Instead, think about how you can generate candidate suggestions by traversing the path of the target string taking small "detours" to the neighbors that are within the maximum distance.

Matching Regular Expressions:

The second optional extension is to use recursion to match regular expressions. The matchRegex method takes a regular expression (as defined below) as input and gathers the set of lexicon words that match that regular expression.

If you have not encountered them before, a regular expression describes a string-matching pattern. Ordinary alphabetic letters within the pattern indicate where a candidate word must exactly match. The pattern may also contain "wildcard" characters, which specify how and where the candidate word is allowed to vary. For now, we will consider a subset of wildcard characters that have the following meanings:

• The '*' wildcard character matches any sequence of zero or more characters.
• The '?' wildcard character matches either zero or one character.

For example, consider the original sample trie containing the words a, are, as, new, no, not, and zen. Here are the matches for some sample regular expressions:

Finding the words that match a regular expression will require applying your finest recursive skills. You should not find suggestions by examining each word in the lexicon and seeing if it is a match. Instead, think about how to generate matches by traversing the path of the pattern. For non-wildcard characters, it proceeds just as for traversing ordinary words. On wildcard characters, "fan out" the search to include all possibilities for that wildcard.

Suggestions

• Lexicon operations are case-insensitive. Searching for words, suggesting corrections, matching regular expressions, and other operations should have the same behavior for both for upper and lowercase inputs. Be sure to take that into consideration when designing your data structure and algorithms.
• Build and test incrementally. Develop your trie one function at a time and continually test as you go. We have provided a handy client program that exercises the lexicon and allows you to drive the testing interactively from the console. It is supplied in source code form (Main.java) and you are encouraged to modify and extend it as needed for your purposes.
• Use stubs as placeholders. The testing code we provide makes calls to all of the public member functions on the Lexicon. In order for the program to compile, you must have implementations for all the functions. However, this doesn't suggest that you need to write all the code first and then attempt to debug it all at once. You can implement methods with placeholder "stubs" to start. If your lexicon doesn't yet remove words, implement the remove operation to ignore its argument or raise an error. Before you have implemented regular expression match, just return an empty set from the function and so on. (We've given you stubs in the starter code.)
• Test on smaller data first. There are small.txt and small2.txt data files with just a few words that are especially helpful for testing in the early stages. You can also create word data files of your own that test specific trie configurations. The ospd2.txt word file is very large. It will be useful for stress-testing once you have the basics in place, but it can be overwhelming to try to debug using that version.

Completing the Lab

We provide basic starter code for this assignment. The lexicon directory contains the following files:

• Lexicon.java: The interface that you need to implement (Do not edit.)
• Main.java: Sample code that you can use to test your LexiconTrie (No need to edit.)
• LexiconTrie.java: skeleton for a LexiconTrie implementation (Must edit.)
• LexiconNode.java: skeleton for the class that represents Trie nodes (Must edit.)
• small.txt, small2.txt, ospd2.txt: Data files containing sets of words for you to test with (Do not edit.)

Submit

Make sure that you have accomplished all tasks required above, including javadoc comments for public methods in LexiconTrie.java and LexiconNode.java. Then, submit your code to Gradescope (Lab 08) and ensure it passes all autograder tests. You should upload LexiconTrie.java and LexiconNode.java

It's time to add, commit, and push your code files. Enter each of the following commands into your terminal.

git add LexiconTrie.java LexiconNode.java
git commit -m "finished with lab 8"
git push

After you commit, log into evolene.cs.williams.edu. Click on your repo, then Lab08, then each code file, and make sure that you can see the modifications you made. If you can see the changes, you're all set!