Tries

Tries and Patricia Tries

Motivation: The autocomplete feature in a text editor.

We have a dictionary of words, and we want to find all the words that start with a given prefix.

The data structure we use to store the dictionary is called a trie.

• Each edge is labeled with a character.
• Some nodes are marked as terminal nodes.
• By convention, children of a node are ordered alphabetically.
• A preordering traversal of the trie yields the words in the dictionary in alphabetical order.

The total length of our text strings is m and the length of our pattern string is n.

Time to build the trie: O(m)

Time to search for a pattern: O(n)

How long does it take to find all the words that start with a given prefix?

The $ symbol is called the sentinel or marker, add this to the end of each word. It is used to mark the end of a word, it precedes all other characters in the alphabet.

Nodes now fall into two categories: Leaf nodes and internal nodes.

Leaf nodes correspond to words in the dictionary, internal nodes correspond to routing structures.

A node is a silly node if it has only one child, A Patricia trie is a trie where silly nodes are merged into their parents.

Observation 1: Every internal node has at least two children.

Observation 2: Every leaf node has exactly one child.

Theorem: The number of nodes in a Patricia trie is at most twice the number of words in the dictionary.

Claim: If each leaf in a Patricia trie is annotated with the index of the word it comes from, the indices of strings starting with a given prefix can be found in time O(n+z), where n is the length of the prefix and z is the number of strings starting with the prefix.

Proof: We start at the root and follow the path corresponding to the prefix. This takes time O(n). We then do a preordering traversal of the subtree rooted at the last node on the path. This takes time O(z). (a subtree with z leaves has O(z) total nodes)

<O(m),O(n+z)> solution to prefix matching.

Suffix Trees

Cancers often have repeated copies the same gene. Given a cancer genome (length ~3,000,000,000), find the longest repeated DNA sequence.

A Fundamental Theorem

Theorem: A string S is a substring of T if and only if S is a prefix of a suffix of T.

To find all matches of w in x, we just need to find all suffixes of x that start with w.

A suffix tree for a string x is a trie for all suffixes of x.

Each leaf is labeled with the starting index of that suffix.

• It’s possible to build a suffix tree from a string of length m in time O(m).
• It’s possible to store a suffix tree for a string of length m using O(m) words of memory.

The Anatomy of a Suffix Tree

• Each edge is labeled with a substring of x.

• A branching word in T$ is a string ω such that there are characters a ≠ b where ωa and ωb are substrings of T$.

• The suffix tree for a string T has an internal node for a string S if and only if S is a branching word in T$.

• The leaves of a suffix tree for T correspond to suffixes of T$, and the internal nodes of a suffix tree for T correspond to branching words of T$.

• Theorem: The longest repeated substring of a string T must be a branching word in T$.

• To find the longest repeated substring of T, we just need to find the longest branching word in T$.

• Time to build a suffix tree: O(m)

• Time to find the longest repeated substring: O(m)

Some other applications of suffix trees:

• Generalized suffix trees: Solve many string problems on multiple strings simultaneously.

• Approximate string matching: Find all occurrences of a pattern that differs from a substring of T by at most k characters.

• Fast matrix multiplication: Find the longest common substring of two strings.

Representing a Suffix Tree

• O(m) space for all the nodes.

• O(m) space for a copy of the original string.

• O(m) space for the edges.

• O(m) space for the suffix tree.

Suffix Tree Space Usage

Suffix tree edges take up a lot of space.

• Two machine words per edge to store the start and end indices of the substring.
• One machine word per edge to store the pointer itself.
• Number of edges ranges from m to 2m-1.

Key Question: Can we reduce the space usage of a suffix tree?

The efficiency in a suffix tree is largely due to

1. Keeping the suffixes in sorted order.
2. exposing the branching words.

The suffix array stores information about the ordering of the suffixes of a string. TheLCP array stores information about the branching words of a string.

Suffix Arrays

A suffix array for a string T is a sorted array of the suffixes of the string T$.

Suffix arrays distill out just the first component of the suffix tree: The ordering of the suffixes.

We reduced the space usage, store the starting positionso of the suffixes.

Space: O(m), and with only one machine word per suffix.

Using Suffix Arrays

find all instances of a pattern P with length n in a string T with length m.

Claim: With a suffix array, we can determine whether a pattern P of length n occurs in a string T of length m in time O(nlog m)

• Binary search has O(log m) rounds.
• Each round takes O(n) time to compare the pattern to a suffix.

Claim: With a suffix array, we can find all occurrences of a pattern P of length n in a string T of length m in time O(n logm + z), where z is the number of occurrences of P in T.

This is a <O(m),O(n log m + z)> solution to the pattern matching problem.

what else can we do with a suffix array?

Branching words

• Branching words. By sorting the suffixes, we've made it easy to find the branching words.
• Specifically, the branching words are the longest common prefixes (or LCP) of adjacent suffixes in the suffix array.

Theorem: A string s is a branching word in T$ if and only if s is a longest common prefix of two adjacent suffixes in the suffix array for T.

Longest Repeated Substring

We can list all branching words from a suffix array in time $O(m^2)$.

• O(m) pairs; each pair takes O(m) time to compare.

For suffix trees, we can find the longest branching word in time O(m).

can we do better than O(m^2)?

Observation: We don't need to know what all the branching words are to find the longest one, we just need to know the length of them.

LCP Arrays

The LCP array, often denoted H, is an array where H[i] is the length of the longest common prefix of the suffixes starting at positions SA[i] and SA[i+1] in the suffix array.

Key intuition: The suffix array gives the leaves of the suffix tree, the LCP array gives the internal nodes of the suffix tree.

If you already have a suffix array, you can compute the LCP array in time O(m).

The Question is: How fast can we compute the LCP array?

Claim: Look at the second sufix in the pair. Its LCP with the suffix before it is at least the previous LCP minus one.

Kasai's Algorithm

For each suffix of the original string, except the last one:

• Find the suffix in the suffix array.
• Look atthe suffix that comes before it.
• Find the longest common prefix of the two suffixes.
• Write the length of the longest common prefix in the LCP array.

From stackoverflow:

Algorithn GetLCP:
inpit: A text S and its suffix array pos
output: LCP array H

for i = 0 to n-1 do
    rank[pos[i]] = i
od

h = 0

for i = 0 to n-1 do
    if rank[i] > 0 then
        k = pos[rank[i]-1]
        while S[i+h] = S[k+h] do
            h = h + 1
        od
        H[rank[i]] = h
        if h > 0 then
            h = h - 1
        fi
    fi
od

return H

Total running time: O(m)

How to build a suffix tree.

Ukkonen's algorithm

• O(m) time to build a suffix tree.

Algorithm Ukkonen:
input: A string T of length m
output: A suffix tree for T

T$ = T + "$"
n = length(T$)
root = new node

for i = 0 to n-1 do
    current = root
    for j = i to n-1 do
        if there is an edge from current labeled T$[j] then
            current = the node at the end of that edge
        else
            create a new node new
            create a new edge from current to new labeled T$[j]
            current = new
        fi
    od
od

return root