Incomputer science, acompressed suffix array^[1][2][3] is acompressed data structure forpattern matching. Compressed suffix arrays are a general class ofdata structure that improve on thesuffix array.^[1][2] These data structures enable quick search for an arbitrarystring with a comparatively small index.

Given a textT ofn characters from an alphabet Σ, a compressed suffix array supports searching for arbitrary patterns inT. For an input patternP ofm characters, the search time is typically O(m) or O(m + log(n)). The space used is typically${\displaystyle O(n{H}_k(T))+o(n)}$, where${\displaystyle H_k(T)}$ is thek-th order empirical entropy of the textT. The time and space to construct a compressed suffix array are normally⁠${\displaystyle O(n)}$⁠.

The original presentation of a compressed suffix array^[1] solved a long-standing open problem by showing that fast pattern matching was possible using only a linear-space data structure, namely, one proportional to the size of the textT, which takes${\displaystyle O(n\log |\mathrm{\Sigma }|)}$ bits. The conventional suffix array and suffix tree use${\displaystyle \mathrm{\Omega }(n\log n)}$ bits, which is substantially larger. The basis for the data structure is a recursive decomposition using the "neighbor function," which allows a suffix array to be represented by one of half its length. The construction is repeated multiple times until the resulting suffix array uses a linear number of bits. Following work showed that the actual storage space was related to the${\displaystyle 0^{th}}$-order entropy and that the index supports self-indexing.^[4] The space bound was further improved achieving the ultimate goal of higher-order entropy; the compression is obtained by partitioning the neighbor function by high-order contexts, and compressing each partition with awavelet tree.^[3] The space usage is extremely competitive in practice with other state-of-the-art compressors,^[5] and it also supports fastin-situ pattern matching.

The memory accesses made by compressed suffix arrays and other compressed data structures for pattern matching are typically not localized, and thus these data structures have been notoriously hard to design efficiently for use inexternal memory. Recent progress using geometric duality takes advantage of the block access provided by disks to speed up the I/O time significantly^[6] In addition, potentially practical search performance for a compressed suffix array in external-memory has been demonstrated.^[7]

There are several open source implementations of compressed suffix arrays available (seeExternal Links below). Bowtie and Bowtie2 are open-source compressed suffix array implementations ofread alignment for use inbioinformatics. The Succinct Data Structure Library (SDSL) is a library containing a variety of compressed data structures including compressed suffix arrays. FEMTO is an implementation of compressed suffix arrays for external memory. In addition, a variety of implementations, including the originalFM-index implementations, are available from the Pizza & Chili Website (see external links).

• FM-index
• Suffix Array

Implementations:

• Bowtie andBowtie2
• Succinct Data Structure Library (SDSL)
• FEMTO
• Pizza&Chili website.

• String data structures
• Database index techniques
• Substring indices
• Data compression

• Articles with short description
• Short description matches Wikidata