Suffix Arrays for Phrase Search
This article is still a work in progress and may contain inaccuracies and undeveloped sections! Use it at your own discretion!
Use cases
Imagine you have a very large collection of documents and you want to organize it (or index it) in such a way so that you can easily
- find if the collection contains documents with any phrase, no matter how long the phrase
- compute ngram frequencies for large ngrams.
Suffix arrays are one way to go about it. The approach of suffix arrays works by organizing the words in collection in such a way that a linear scan will reveal the number of times an ngram appears in the collection, no matter how long the ngram.
One quite interesting application related to the two questions above is how to extract cheaply all the phrases in a large collection of text.
What is a suffix array?
Suffix arrays are typically explained on a string of text such as “abracadabra”
Substring search problem
What we want here is given a substring such as “cadab” to find easily if it is a substring of the original “abracadabra” string. (Instead of array of letters one can consider array of words, the substring in this case is replaced by a phrase containing words.)
So the way we can go about this problem it is to take the original string and create the list of all suffixes:
abracadabra
bracadabra
racadabra
acadabra
cadabra
adabra
dabra
abra
bra
ra
a
Then if we search for “cadab” we can see that it will be a prefix of one of the suffixes, namely “cadabra”.
A substring is a prefix of a suffix of the complete string. Therefore, when we search for a substring, we search for a prefix of a suffix. For example, "cadabra" is a suffix, and "cada" is a prefix of length 4 in the suffix "cadabra". If we were searching for "cada", we'd find it to be the prefix of the suffix "cadabra".
Speeding up the search
One method for speeding up the search is to sort the suffixes and then search with binary search.
Reducing storage
When we generate all suffixes of a string of $n$ characters, we need $O(n^2)$ space. This can be avoided if we figure out that we can represent each suffix with a pointer (or offset) in the original string.
Thus, initially the suffixes are represented via the offsets:
0: abracadabra 1: bracadabra 2: racadabra 3: acadabra 4: cadabra 5: adabra 6: dabra 7: abra 8: bra 9: ra 10: a
After sorting we retrieve the suffix string from the offset:
sorted suffixes and the offset in the original string ----------------------------------------------------- start in original array suffix ----------------------------------------------------- 10 "a" 7 "abra" 0 "abracadabra" 3 "acadabra" 5 "adabra" 8 "bra" 1 "bracadabra" 4 "cadabra" 6 "dabra" 9 "ra" 2 "racadabra"
Sorting the suffixes
Even though we reduced the memory from the naive $O(n^2)$ to $O(n)$, if we use the obvious sorting method (say plain quick sort), it might take $O(n^2)$ to sort the suffixes. One idea is that we can use a special version of quick sort that works very well for sorting arrays of strings (this version is called multikey ternary quicksort) or let’s just call it fast string sort
Now all that is needed to adapt the implementation(s) from the above article by providing custom implementations for the following functions of strings:
string.length string.charAt(...)
The idea kind of works but a problem appears in a data that contains a lot of duplicate ngrams. For example:
abc abc abc abc
If we attempt to sort and choose the letter ‘b’ as the first pivot we reach the following state:
let extra = abc group 1 (first letter < 'b') abc extra extra extra abc extra extra abc extra abc -------------------- group 2 (first letter == 'b') bc extra extra extra bc extra extra bc extra bc -------------------- group 3 (first letter > 'b') c extra extra extra c extra extra c extra c
Now as one can see, recursing on the first group, since all suffixes there start with ‘a’, we arrive at a group that looks exactly like the second group. Since those groups of suffixes are handled independently, work will be repeated.
A pathological case is data that contains the same character, for example ‘aaaaaaaaaaaaa….aaaa’
The use of the string sorting algorithm is competitive if not many duplicates appear. But no one can guarantee that.
A clever algorithm: SA-IS
This section is still under construction.
Computing the LCP array
LCP stands for longest common prefix. What LCP means is best explained by an example.
Consider two consecutive suffixes after sorting.
i ind lcp rnk select --------------------------- 0 10 - 0 "a" 1 7 1 1 "abra" 2 0 4 2 "abracadabra" 3 3 1 3 "acadabra" 4 5 1 4 "adabra" 5 8 0 5 "bra" 6 1 3 6 "bracadabra" 7 4 0 7 "cadabra" 8 6 0 8 "dabra" 9 9 0 9 "ra" 10 2 2 10 "racadabra"
For example, in the sorted list, consider the suffix at position $i=6$. This is “bracadabra” Before this suffix, at position $i=5$ we see the suffix “bra”. Since the common prefix of “bra” and “bracadabra” is 3, we write 3 for the LCP of “bracadabra”.
Given the sorted suffixes the LCP array can be computed in linear time. See the implementation in function computeLCP
Uses of the LCP array
The LPC array is useful for
- speeding up substring search
- finding the longest repeated substring
- quickly discovering ngram counts
Computing phrases from Wikipedia
Input: 50000 documents Number of total words in those documents: 88 686 630 Size of input array in MBs: 160 (the array is an array of integer ids, each id represents a word)
The time to sort the suffixes is 50 seconds. The same time was achieved by both the fast string sort algorithm and the SA-IS algorithm with implementation by yuta256. However, the fast string sort algorithm may fail to perform well on certain type of data. So the SA-IS algorithm is preferable.
After the suffix array and the LCP (longest common prefix) array are computed it’s a matter of scanning through the LCP array and keeping track of a few counters. This is the function dumpNgrams
The top bigrams are (the scores below are counts):
united kingdom 13463.0 prime minister 13370.0 war ii 12824.0 median income 12762.0 high school 10932.0 university press 10239.0 civil war 9752.0 every females 8878.0 los angeles 8797.0 soviet union 8602.0 per square 8488.0 air force 8413.0 further reading 8190.0 square mile 8184.0 american actor 8110.0 african american 8069.0 press isbn 8027.0
Some interesting trigrams (the scores below are not counts):
dien bien phu -1357.0843587874344 guru granth sahib -1395.1764721438385 tuatha dã© danann -1419.5544827727674 chen shui bian -1431.465076962982 obi wan kenobi -1444.5153566396255 lee kuan yew -1516.8594907003933 chiang ching kuo -1548.9171440014002 gamal abdel nasser -1550.7136811332614 josip broz tito -1579.5224149565151 ursula le guin -1602.9230687266368 ebook kansas cyclopedia -1630.9021398533328 mutant ninja turtles -1645.7369039407974 castilla la mancha -1669.7628172544435 kuala lumpur malaysia -1700.1293484922126 teenage mutant ninja -1719.8348978683298
Demo
A working demo is available in the suffix-array project.