Autocomplete

Designing and analyzing autocomplete.

1. Autocomplete interface
   1. Reference implementation
2. Design and implement
   1. SequentialSearchAutocomplete
   2. BinarySearchAutocomplete
   3. TernarySearchTreeAutocomplete
3. Analyze and compare
   1. Asymptotic analysis
   2. Experimental analysis
4. Above and beyond
   1. Wordscapes
   2. Count of range sum
   3. Trie implementation
   4. Algorithmic fairness

Autocomplete is a feature that helps a user select valid search results by showing possible inputs as they type. For example, in a map app, autocomplete might allow the user to enter a prefix such as Sea and automatically suggest the city, Seattle.

In addition to autocompleting names, places, or things, autocomplete can also be a useful abstraction for implementing DNA subsequence search. Instead of indexing a list of all the city names or places, a DNA data structure can index all the suffixes of a very long DNA sequence. Autocompleting the DNA suffixes enables efficient search across all the DNA substrings for medical applications, genomics, and forensics.

In this project, we will compare 4 implementations (described later) and 2 applications (city search and DNA search) of autocomplete. By the end of this project, students will be able to:

• Design and implement tree-based and array-based search data structures.
• Analyze and compare runtimes using asymptotic and experimental analysis.

Autocomplete interface

Implementations of Autocomplete must provide the following methods:

void addAll(Collection<? extends CharSequence> terms)

Adds all the terms to the autocompletion dataset. Each term represents a possible autocompletion search result. Behavior is not defined if duplicate terms are added to the dataset.

Collection

The parent interface to lists and sets in Java. Using Collection rather than List lets clients use any list or set or other collection that they’ve already created in their program.

CharSequence

An interface that generalizes the concept of a String of characters. Using CharSequence rather than String lets clients define specialized implementations for long strings like DNA.

Collection<? extends CharSequence>

The type of the parameter, read: a Collection of any type of elements that extend CharSequence. The ? extends lets clients call the method with a Collection<String> or a Collection<SuffixSequence> instead of having to strictly use a Collection<CharSequence>.

List<CharSequence> allMatches(CharSequence prefix)

Returns a list of all terms that begin with the same characters as the given prefix.

Given the terms [alpha, delta, do, cats, dodgy, pilot, dog], allMatches("do") should return [do, dodgy, dog] in any order. Try this example yourself by writing a new test case in the AutocompleteTests class. You can write additional test cases like this to assist in debugging.

@Test
void compareSimple() {
    List<CharSequence> terms = List.of(
        "alpha", "delta", "do", "cats", "dodgy", "pilot", "dog"
    );
    CharSequence prefix = "do";
    List<CharSequence> expected = List.of("do", "dodgy", "dog");

    Autocomplete testing = createAutocomplete();
    testing.addAll(terms);
    List<CharSequence> actual = testing.allMatches(prefix);
    assertEquals(expected.size(), actual.size());
    assertTrue(expected.containsAll(actual));
    assertTrue(actual.containsAll(expected));
}

Reference implementation

The project code includes a fully functional TreeSetAutocomplete implementation that stores all the terms in a TreeSet. The class contains a single field for storing the underlying TreeSet of terms. Rather than declare the field as a Set, we’ve chosen to use the more specialized subtype NavigableSet because it includes helpful methods that can be used to find the first term that matches the prefix.

private final NavigableSet<CharSequence> elements;

The constructor assigns a new TreeSet collection to this field. In Java, TreeSet is implemented using a red-black tree, a type of balanced search tree where access to individual elements are worst-case logarithmic time with respect to the size of the set. CharSequence::compare tells the TreeSet to use the natural dictionary order when comparing any two elements.

public TreeSetAutocomplete() {
    elements = new TreeSet<>(CharSequence::compare);
}

If you’ve ever used a TreeSet<String>, you might be surprised to see the argument CharSequence::compare. This is not necessary for TreeSet<String>, but it is necessary for TreeSet<CharSequence> because CharSequence does not implement Comparable<CharSequence>. You can read more in the Java developers mailing list.

The addAll method calls TreeSet.addAll to add all the terms to the underlying TreeSet.

@Override
public void addAll(Collection<? extends CharSequence> terms) {
    elements.addAll(terms);
}

The allMatches method:

1. Ensures the prefix is valid. If the prefix is null or empty, returns an empty list.
2. Finds the first matching term by calling TreeSet.ceiling, which returns “the least element in this set greater than or equal to the given element, or null if there is no such element.”
3. Collects the remaining matching terms by iterating over the TreeSet.tailSet, which is “a view of the portion of this set whose elements are greater than or equal to fromElement.”
4. If we reach a term that no longer matches the prefix, returns the list of results.

@Override
public List<CharSequence> allMatches(CharSequence prefix) {
    List<CharSequence> result = new ArrayList<>();
    if (prefix == null || prefix.length() == 0) {
        return result;
    }
    CharSequence start = elements.ceiling(prefix);
    if (start == null) {
        return result;
    }
    for (CharSequence term : elements.tailSet(start)) {
        if (Autocomplete.isPrefixOf(prefix, term)) {
            result.add(term);
        } else {
            return result;
        }
    }
    return result;
}

In Java, a view is a clever way of working with a part of a data structure without making a copy of it. For example, the ArrayList class has a subList method with the following method signature.

public List<E> subList(int fromIndex, int toIndex)

subList returns another List. But instead of constructing a new ArrayList and copying over all the elements from the fromIndex to the toIndex, the Java developers defined a SubList class that provides a slice of the data structure using the following fields (some details omitted).

private static class SubList<E> implements List<E> {
    private final ArrayList<E> root;
    private final int offset;
    private int size;
}

The SubList class keeps track of its ArrayList root, an int offset representing the start of the sublist, and the int size of the sublist. The sublist serves as an intermediary that implements get(index) by checking that the index is in the sublist before returning the offset index.

public E get(int index) {
    if (index < 0 || index >= size) {
        throw new IndexOutOfBoundsException();
    }
    return root.elementData[offset + index];
}

Design and implement

Design and implement 3 implementations of the Autocomplete interface.

All team members must work together and fully understand each implementation. Do not assign each implementation to individual team members. The implementations are described in order of increasing complexity so later implementations will require significantly more work.

SequentialSearchAutocomplete

Terms are added to an ArrayList in any order. Because there elements are not stored in any sorted order, the allMatches method must scan across the entire list and check every term to see if it matches the prefix.

BinarySearchAutocomplete

Terms are added to a sorted ArrayList. When additional terms are added, the entire list is re-sorted using Collections.sort. Since the terms are in a list sorted according to natural dictionary order, all matches must be located in a contiguous sublist. Collections.binarySearch can find the start index for the first match. After the first match is found, we can collect all remaining matching terms by iterating to the right until it no longer matches the prefix.

List<CharSequence> elements = new ArrayList<>();
elements.add("alpha");
elements.add("delta");
elements.add("do");
elements.add("cats");

System.out.println("before: " + elements);
Collections.sort(elements, CharSequence::compare);
System.out.println(" after: " + elements);

CharSequence prefix = "bay";
System.out.println("prefix: " + prefix);
int i = Collections.binarySearch(elements, prefix, CharSequence::compare);
System.out.println("     i: " + i);

This program produces the following output.

before: [alpha, delta, do, cats]
 after: [alpha, cats, delta, do]
prefix: bay
     i: -2

The index i is negative because Collections.binarySearch returns a negative value to report that an exact match for the prefix was not found in the sorted list.

Returns

the index of the search key, if it is contained in the list; otherwise, (-(insertion point) - 1). The insertion point is defined as the point at which the key would be inserted into the list: the index of the first element greater than the key, or list.size() if all elements in the list are less than the specified key. Note that this guarantees that the return value will be >= 0 if and only if the key is found.

Since the prefix often will not exactly match an element in the list, we can use algebra to recover the insertion point. The start value represents the index of the first term that could match the prefix.

int start = i;
if (i < 0) {
    start = -(start + 1);
}

Explain the part of the BinarySearchAutocomplete class that you’re most proud of programming.

TernarySearchTreeAutocomplete

Terms are added to a ternary search tree using the TST class (https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/TST.java) as a reference.

1. Skim the TST class (linked above). What do you notice will work for Autocomplete? What needs to change?
2. Identify methods in the TST class that are most similar to Autocomplete.
3. Adapt the code to implement the Autocomplete interface.

Don’t copy and paste code! Most of the time, we will need to make many changes, and we might introduce subtle bugs when we copy code that we don’t fully understand. Instead, rewrite the code in your own words after making sense of the purpose of each line. We often don’t need all the lines of code, and the code can be rewritten in ways that are more suitable for the problem at hand.

It’s okay if your TernarySearchTreeAutocomplete throws a StackOverflowError when running the DNASearch class. This is caused by Java’s built-in limit on recursive depth. There are different ways to work around this limit, but it’s not relevant to this project.

Explain the part of the TernarySearchTreeAutocomplete class that you’re most proud of programming.

Run all the tests in IntelliJ and show a summary of the results. If the implementations pass all the test cases, explain an interesting bug that you addressed during your programming process. If the implementations do not pass all the test cases, explain what you think could be causing the problem.

Analyze and compare

Asymptotic analysis

Give a big-theta bound for the worst-case runtime of the addAll and allMatches methods for each implementation, including TreeSetAutocomplete, with respect to N, the total number of terms already stored in the data structure. Explain the runtime of each implementation in a couple sentences while referencing the code.

As you perform your asymptotic analysis, make sure to carefully read through and keep in mind the assumptions and hints given below.

What does the underlying data structure look like in the worst case? How are terms organized? Based on that worst case, analyze the runtime of operations performed on that data structure.

addAll

Assume a constant number of terms are added to a dataset that already contains N terms.

Assume that arrays can accommodate all the new terms without resizing.

Collections.sort uses Timsort, an optimized version of merge sort with runtime in O(N log N) where N is the size or length of the collection or array.

allMatches

Consider the relationship between the added terms and the prefix. How many matches will we have if all the terms in the dataset begin with A and the prefix is A? How many matches will we have if all the terms in the data set begin with B and the prefix is A?

Assume all strings have a constant length. TreeSet is implemented using a red-black tree, which has the same asymptotic runtime as a left-leaning red-black tree or a 2-3 tree.

Experimental analysis

Compare the runtimes across all 4 implementations, including TreeSetAutocomplete. Are certain algorithms faster than others? Are there any disagreements between the runtimes you hypothesized in asymptotic analysis and the runtimes you observed in your experimental graphs? Describe how differences between the theoretical assumptions made for asymptotic analysis and the actual settings in RuntimeExperiments might explain those disagreements. For allMatches, describe how the default prefix affects the experimental analysis.

To enable RuntimeExperiments, go to test > autocomplete > AutocompleteTests.java, scroll down to the RuntimeExperiments class around line 96, and comment out the @Disabled tag above the class header.

Run the provided RuntimeExperiments in AutocompleteTests to compare the real-world runtime of each implementation. For each implementation, RuntimeExperiments constructs an empty instance and records the number of seconds to add N terms to the dataset and then compute all matches for the prefix (such as Sea).

• The first column denotes N, the total number of terms.
• The second column denotes the average runtime for addAll in seconds.
• The third column denotes the average runtime for allMatches in seconds.

Copy-paste the text into plotting software such as Desmos. Plot the runtimes of all 4 implementations on addAll and allMatches.

Above and beyond

Optionally, apply what you’ve learned by working on these project ideas.

Wordscapes

Wordscapes is an app that has multiple levels where you try to fill out a crossword puzzle using only the letters provided. Although a set of words can create several valid words, only a select few are considered to fill out the puzzle (perfect place to use isTerm). You can choose an implementation that you feel is most appropriate for the game and also create your own list of words to use for the crosswords you create.

Count of range sum

LeetCode 327. Count of Range Sum

Given an integer array nums and two integers lower and upper, return the number of range sums that lie in [lower, upper] inclusive. Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j inclusive, where i <= j.

In order to build a solution for this LeetCode problem, it is essential to understand a data structure called a Segment Tree: a tree data structure for efficiently querying of values within intervals aka segments. Watch the video below in order to get a comprehensive understanding and overview of the segment tree data structure. The video covers everything you will need in order to come up with a Segment Tree approach solution for the LeetCode problem discussed above.

Trie implementation

During class, we compared the ternary search tree data structure to the trie data structure. Like a TST, a trie can also be used to implement the Autocomplete interface! Using this example TrieST class, identify and adapt relevant portions of the code to implement the Autocomplete interface. Most of the code in the TrieST class is not needed for implementing Autocomplete. Use the Trie Visualization to see what you expect your tree to look like!

Algorithmic fairness

In your project, you may have wondered how search engines display their results, and which sources they chose to display first. In this talk, Chirag Shah expands on these ideas, explores how ranking of search results impact users, and presents some algorithms and statistical methods that can be used to increase fairness and diversity in search result rankings.