Back in January of 2012, Russ Cox posted an excellent blog post detailing how Google Code Search had worked, using a trigram index.

By that point, I’d already implemented early versions of my own livegrep source-code search engine, using a different indexing approach that I developed independently, with input from a few friends. This post is my long-overdue writeup of how it works.

Suffix Arrays  🔗︎

A suffix array is a data structure used for full-text search and other applications, primarily these days in the field of bioinformatics.

A suffix array is pretty simple, conceptually: It’s a sorted array of all of the suffixes of a string. So, given the string “hither and thither”, we could construct a suffix array like so:

Note that there is no need for each element of the array to store the entire suffix: We can just store the indexes (the left-hand column), along with the original string, and look up the suffixes as needed. So the above array would be stored just as

[6 10 7 9 16 4 15 3 12 0 13 1 8 17 5 14 2 11]

There exist algorithms to efficiently construct suffix arrays (O(n) time), and in-place (constant additional memory outside of the array itself).

Full-text substring search  🔗︎

Once we have a suffix array, one basic application is full-text search.

If we’re trying to find a substring within a larger corpus, we know that that substring, if present, must be a prefix of some suffix of the larger corpus. That is, given a suffix array, any substring present in the corpus must be the start of some entry in the suffix array. For example, searching for “her” in “hither and thither”, we find that it is present in two places in the string, and it begins two lines of the above suffix array:

But because the suffix array is sorted, we can find those entries efficiently by binary searching in the suffix array. The indexes then give us the location of the search string in the larger text.

Towards Regular Expression Search  🔗︎

We begin with a large corpus of source code we want to do regular expression search over.

During indexing, livegrep reads all of the source and flattens them together into a single enormous buffer (livegrep uses the open-source libdivsufsort library to build the suffix array; old versions of livegrep used a hand-rolled radix sort, which often went quadratic – divsufsort dramatically improved index-building performance). As it does this, it maintains information I call the “file content map”, which is essentially just a sorted table of (start index, end index, file information), which allows us to determine which input file provided which bytes of the buffer.

(This is something of a simplification; livegrep actually uses a number of suffix arrays, instead of a single giant one, and we compress the input by deduplicating identical lines, which makes the file content map more complicated. A future blog post may discuss the specifics in more detail)

But now how do we use that structure to efficiently match regular expressions?

As a first idea, we can find literal substrings of the regular expression, find any occurrences of those strings using the suffix array, and then only search those locations in the corpus.

For example, given /hello.*world/, we can easily see that any matches must contain the string “hello”, and so we could look up “hello”, find all lines containing it, and then check each line against the full regular expression.

More complex searching  🔗︎

But it turns out we can do better. Because of the structure of the suffix array, we can perform at least two basic queries beyond substring search:

• Range search: We can efficiently find all instances of a character range, by binary-searching each end. If we have the range [A-F], we binary-search for the first suffix starting with A, and the last suffix starting with F, and we know that every index in between (in the suffix array) starts with something between A and F.

• Chained searches: If we have a chunk of the suffix array that we know has a common prefix, we can narrow down the search by doing additional searches and looking at the next character, within that range. For example, if we want to find /hi(s|m)/, we can binary-search to find all positions starting with hi, which gives us a contiguous block of the suffix array. But since that block is sorted, we can do another pair of binary searches within that range, looking only at the third character, one looking for s and one for m, which will give us two smaller chunks, once for “his” and one for “him”.

We also have the option of making multiple searches and combining the results; Given /hello|world/, we can search for “hello”, and search for “world”, and then look at both locations.

And we can combine all of these strategies. By way of example, we can search for /[a-f][0-9]/ by:

1. Binary searching to find a-f
2. Splitting that into 6 ranges, one for a, b, c, d, e, and f
3. For each of those ranges, doing a binary search over the second character, looking for the 0-9 range.

type IndexKey struct {
  edges []struct {
    min  byte
    max  byte
    next *IndexKey
  }
}