Replace words with the shortest root

Why this matters

A root is the short base form that a longer word starts with. The word "cattle" starts with the root "cat". The word "rattled" starts with the root "rat". A tool that shortens words to their roots is useful in search engines, where "cattle" and "cat" should match, and in text compression, where a short root can stand in for a longer word.

The task in this lesson is simple to state. You get a list of root words and a sentence. For each word in the sentence, replace it with the shortest root that is a prefix of that word. If no root is a prefix, keep the word as it is. For example, with the roots "cat", "bat" and "rat", the sentence "the cattle was rattled by the battery" becomes "the cat was rat by the bat".

The word "shortest" is the key. If the roots are "cat" and "catt", the word "cattle" becomes "cat", not "catt". A plain search that returns the first root it finds does not always give the shortest one, and the trie makes the shortest answer easy to find.

Lesson 02 in this module showed how to insert words and search for a prefix. This lesson uses the same trie, with one change to the walk. The walk stops at the first node that has its end flag set.

Terms used in this lesson

A prefix is the first part of a word. "cat" is a prefix of "cattle", and "ca" is also a prefix of "cattle".

An end flag is a True or False value on a trie node. It is True when the path from the root to that node spells a whole word in the dictionary. In this lesson the dictionary is the list of roots.

A sentence is a line of text with words separated by spaces. In this lesson the program splits the sentence into words, works on each word, and joins the results with spaces again.

A split is an operation that cuts a string into pieces at a separator. The method sentence.split(" ") cuts a sentence at each space and returns a list of words.

A join is the opposite. The program puts the pieces back together with a separator between them. The method " ".join(pieces) puts one space between each pair of pieces.

A small worked example

Start with the roots "cat", "bat" and "rat". The trie has three paths from the root. The path "c", "a", "t" ends at a node with its end flag set. The path "b", "a", "t" ends at another such node. The path "r", "a", "t" ends at a third one.

The tree looks like this. The marked nodes are the ends of words.

root
 +-- c
 |    +-- a
 |         +-- t (end)
 +-- b
 |    +-- a
 |         +-- t (end)
 +-- r
      +-- a
           +-- t (end)

Now take the word "cattle". The walk starts at the root and follows the letters of the word one at a time.

1. The letter "c" leads to the node "c". Its end flag is false, because "c" is not a root.
2. The letter "a" leads to the node "ca". Its end flag is false, because "ca" is not a root.
3. The letter "t" leads to the node "cat". Its end flag is true, because "cat" is a root.

The walk stops at step 3. The program returns the first three letters of "cattle", which is "cat". The rest of the word, "tle", is dropped.

Now take the word "dog". The letter "d" has no child under the root, so the walk stops with no match. The program keeps the word "dog" unchanged.

The idea: stop at the first end flag

The walk through the trie for one word is a loop with three possible outcomes.

The first outcome is that the node for the next letter does not exist. The walk cannot go further, so no root is a prefix of the word. The program returns the word unchanged.

The second outcome is that the node has its end flag set. The prefix so far is a root, and it is the shortest one, because the walk has checked every shorter prefix already. The program returns the prefix and stops.

The third outcome is that the walk reaches the end of the word without finding an end flag. No root is a prefix of this word. The program returns the word unchanged.

The second outcome is the rule that makes the answer the shortest root. The walk checks prefixes in order from short to long, so the first end flag it meets is the shortest root that matches.

Your first version

The program below builds the trie from the roots once, then goes through the sentence and replaces each word. It uses two functions. insert adds one root to the trie, using the same code as lesson 02. shortest_root runs the walk for one word.

The program prints:

the cat was rat by the bat
a a bbab cadsfafs
the cat was rat by the bat
a  b
split of double space: ['a', '', 'b']
split() with no argument: ['a', 'b']

The first line is the example from the start of the lesson. "cattle" becomes "cat", "rattled" becomes "rat", and "battery" becomes "bat". The word "the" stays the same, because no root is a prefix of it.

The second line uses the roots "a", "aa" and "aaa". The word "aadsfasf" starts with "a", and "a" is the shortest root, so it becomes "a". The word "absbs" also starts with "a", so it becomes "a". The words "bbab" and "cadsfafs" have no root as a prefix, so they stay the same. The longer roots "aa" and "aaa" never get a chance to win, because the walk stops at "a".

The third line adds the root "catt" to the list. The result is the same as the first line. The walk for "cattle" reaches "cat" first, and it stops there, so "catt" is never used.

The fourth line shows a sentence with two spaces in it. The split(" ") method does not skip the empty piece between the two spaces. It returns the words "a", an empty string, and "b". The join puts a space back between each pair of pieces, so the empty piece keeps the double space in the output.

The last two lines of output compare two ways of splitting. split(" ") with a space as the separator keeps the empty piece. split() with no argument splits on any run of whitespace and drops the empty pieces. The program uses split(" "), because the task says to keep the spacing as it is. If you used split(), the double space would disappear from the output.

A second example with a longer word list

Take the roots "ca" and "cat" and the sentence "cattle catalog cab". Each word starts with "c", so the answer depends on the walk through the second and third letters.

For "cattle", the walk goes from "c" to "ca". The node "ca" has its end flag set, because "ca" is a root. The walk stops at "ca", so the answer is "ca". The word "cat" would also be a match, but the walk never reaches it.

For "catalog", the same thing happens. The walk stops at "ca" and returns "ca".

For "cab", the walk also stops at "ca", so the answer is "ca".

The output is "ca ca ca". This example is easy to get wrong, because a reader might expect the "cat" root to win, since "cat" fits the first three letters of "cattle" and seems more specific. The rule in the task is the shortest root, so "ca" wins.

A third example shows what happens with roots that are not prefixes. Take the roots "dog" and "cat" with the sentence "catalog dogs". The word "catalog" starts with "cat", so it becomes "cat". The word "dogs" starts with "dog", so it becomes "dog". The output is "cat dog". The trie holds both roots, and each word takes its own path through the trie.

The program above also handles a word that has no root at all. The word "the" in the first example stays unchanged. The walk for "the" looks for a child "t" under the root. The root has none, so the walk returns the original word.

Tracing one sentence word by word

The first line of output in the program above comes from the sentence "the cattle was rattled by the battery" and the roots "cat", "bat" and "rat". Each word is one walk through the same trie, and each walk starts again at the root. The table shows what each walk does.

The word "by" shows a walk that starts well and then fails. The first letter "b" is a child of the root, because "bat" starts with "b". The second letter "y" is not a child of "b", so the walk stops and the word comes back unchanged. A walk can fail at any step, and each failure has the same result: the word is kept.

The program never checks the whole list of roots for each word. It checks the letters of the word, one by one, and each letter is one step in the trie. A plain loop would test every root against every word, which makes about as many prefix checks as there are roots. The walk makes at most as many steps as the word has letters, no matter how many roots are in the list. That is the reason to use a trie for this task, and it matters most when the list has many roots.

Common mistakes

The most common mistake is returning the longest root instead of the shortest. The next program keeps walking after it finds a root, and it remembers the last root it saw. It returns the last one at the end.

The output is:

catt

The answer should be "cat", because "cat" is the shortest root that is a prefix of "cattle". The program returns "catt" because it did not stop at the first end flag. The fix is to return as soon as node.is_end is true, as the real code does.

The second mistake is a missing None check. When the walk reaches a letter with no child, the next node is None. A program that reads the end flag of that None fails with an exception. The next program has no None check, and it runs on the word "dog", which has no root.

class Node:
    def __init__(self):
        self.children = [None] * 26
        self.is_end = False
 
 
def insert(root, word):
    node = root
    for ch in word:
        i = ord(ch) - ord("a")
        if node.children[i] is None:
            node.children[i] = Node()
        node = node.children[i]
    node.is_end = True
 
 
# Bug: no None check after moving to the child
def shortest_root(root, word):
    node = root
    for i, ch in enumerate(word):
        node = node.children[ord(ch) - ord("a")]
        if node.is_end:
            return word[: i + 1]
    return word
 
 
root = Node()
for r in ["cat", "bat", "rat"]:
    insert(root, r)
print(shortest_root(root, "cattle"))
print(shortest_root(root, "dog"))

The output is:

cat
Traceback (most recent call last):
  File "main.py", line 31, in <module>
    print(shortest_root(root, "dog"))
          ~~~~~~~~~~~~~^^^^^^^^^^^^^
  File "main.py", line 22, in shortest_root
    if node.is_end:
       ^^^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'is_end'

The first call works, because "cattle" has a root. The second call fails, because the root has no child "d", so node is None when the program reads node.is_end. The fix is the if node is None check in the real code. The message names NoneType, which is the type of None, and the attribute that could not be read.

The third mistake is forgetting to set the end flag when inserting. Without the flag, the walk never sees a root, so every word comes back unchanged. The program runs without an error and prints a wrong answer, so the bug is easy to miss. The output of the next program shows the effect.

The output is:

cattle

The word "cattle" should become "cat", but it comes back whole. The fix is the line node.is_end = True at the end of insert.

The fourth mistake is building the trie inside the loop over the words. The result is still correct, but the program builds the same trie again for every word. In a sentence with a thousand words and a list of a thousand roots, that is a thousand rebuilds. The fix is to build the trie once, before the loop, as the real code does.

Practice

Exercise 1

The roots are "ca" and "cat". What does the sentence "cattle" become? Explain which node the walk stops at.

Show the answer: It becomes "ca". The walk goes from the root to "c", then to "ca". The node "ca" has its end flag set, so the walk stops there and never reaches "cat".

Exercise 2

The roots are "dog" and "cat". What does the sentence "catalog dogs" become?

Show the answer: It becomes "cat dog". The word "catalog" starts with "cat", and the word "dogs" starts with "dog". The walk for each word stops at the first end flag it meets.

Exercise 3

The roots are "e" and "ab". Predict the output of replace_words for the sentence "a b". The sentence has two spaces between the words.

Show the answer: The output is "a b", with both spaces kept. The split(" ") method returns three pieces, "a", an empty string and "b". The join puts a space between each pair, so the output has two spaces. Neither "a" nor "b" starts with a root, so both words stay the same. If the code used split() with no argument, the empty piece would be dropped, and the output would have one space.

Exercise 4

Change shortest_root so that it returns the longest root instead of the shortest. Describe the change in one or two sentences.

Show the answer: Remove the early return. Keep a variable that holds the last prefix that had its end flag set, and update it each time the walk finds an end flag. At the end of the loop, return that variable. This is the same logic as the longest_root program, where the output for "cattle" is "catt".

Exercise 5

Why does replace_words build the trie once, before it loops over the words in the sentence? Give a reason with numbers.

Show the answer: Building the trie costs time that grows with the total length of the roots. If the sentence has 1000 words and the program builds the trie inside the loop, it does the building work 1000 times. Building it once means the work is done one time, and each word only costs a walk through the trie, which is at most as long as the word.

Summary

• A root is the short base form that a longer word starts with, and the task is to replace each word with its shortest root.
• The trie walk for one word stops at the first node whose end flag is set, because that is the shortest root.
• A walk that reaches a missing child returns the original word unchanged.
• Build the trie once, before the loop over the words.
• Check for None before reading a field of a child, because a word with no root reaches a missing node.