# Regular Expression Search with Suffix Arrays

DevFeed: [Regular Expression Search with Suffix Arrays](<https://devfeed.tech/articles/regular-expression-search-with-suffix-arrays-21935.md>)

Original publisher: [Read original article](<https://blog.nelhage.com/2015/02/regular-expression-search-with-suffix-arrays/>)

Author: Nelson Elhage

Published: 2015-02-01T15:52:43Z

Content type: tutorial

Language: en

Sources: [Nelson Elhage](<https://devfeed.tech/sources/nelson-elhage.md>)

Topics: [Regular expression](<https://devfeed.tech/topics/regular-expression.md>), [Data structures](<https://devfeed.tech/topics/data-structures.md>), [datasets](<https://devfeed.tech/topics/datasets.md>), [Code](<https://devfeed.tech/topics/code.md>), [Bioinformatics](<https://devfeed.tech/topics/bioinformatics.md>)

Tags: [algorithms](<https://devfeed.tech/tags/algorithms.md>), [arrays](<https://devfeed.tech/tags/arrays.md>), [code-search](<https://devfeed.tech/tags/code-search.md>), [data-structure](<https://devfeed.tech/tags/data-structure.md>), [full-text-search](<https://devfeed.tech/tags/full-text-search.md>), [google](<https://devfeed.tech/tags/google.md>), [library](<https://devfeed.tech/tags/library.md>), [open-source](<https://devfeed.tech/tags/open-source.md>)

## AI overview

This technical writeup explains how livegrep uses suffix arrays for regular-expression search over source code. It introduces suffix arrays, describes substring lookup through binary search, and outlines livegrep's indexing process using a flattened source buffer, a file content map, and libdivsufsort.

## Source excerpt

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.