Why do pattern matches form an interval?

All suffixes beginning with the same pattern are consecutive in lexicographic order.

Is the original text always stored separately?

Not necessarily. Some compressed suffix-array designs are self-indexes, but the exact extraction capability should be checked.

Does compressed mean constant-time access?

No. Access time depends on the representation and sampling choices, often trading time for space.

AI Glossary / MLOps and deployment / Intermediate

Compressed suffix array

Definition

A compressed suffix array is a space-efficient representation supporting operations associated with a suffix array, such as searching a text for a pattern and retrieving suffix positions. It exploits structure in the text or related transformations instead of storing every suffix-array value as an ordinary full-width integer.

What it means

A suffix array lists the starting positions of all suffixes of a text in lexicographic order. This makes occurrences of a pattern appear in a contiguous interval of the ordered suffixes. A straightforward array can require substantial space because it stores one position for each text location. Compressed suffix-array designs reduce that storage while retaining useful search and access operations. Some also act as self-indexes, representing enough information to recover text as well as search it. The exact operations and costs depend on the design.

How it works

Construction begins from the text and the ordering relationships among its suffixes. A compressed design encodes navigational relationships, differences, runs or other regularity and adds sampled values or support structures. Queries use those components to narrow a pattern's suffix interval and, when needed, recover original positions.
Counting occurrences can be cheaper than locating every occurrence, because location recovery may require extra navigation. Sampling more positions can speed access while using more space. Text extraction is another distinct operation. Static and dynamic variants have different tradeoffs. The total representation should include all required samples and metadata, not just the most compressed core component.

Three practical examples

A sequence-search application finds repeated substrings in a large static collection.
A document index counts exact phrase occurrences while keeping its search representation compact.
A research benchmark compares suffix-array access speed at different sampling densities.

Think of it this way

Think of a dictionary of every ending of a text, arranged alphabetically, with starting positions recorded in shorthand. The order helps find matching prefixes, while the shorthand saves space. The analogy does not imply that all suffix strings are copied and stored; efficient structures represent their relationships through the original text and supporting data.

Worked example

For the text "banana$", with $ ordered before letters, the suffixes begin at positions 6, 5, 3, 1, 0, 4 and 2 in sorted order. They are "$", "a$", "ana$", "anana$", "banana$", "na$" and "nana$".
The pattern "ana" matches the suffixes starting at positions 3 and 1, which occupy one contiguous interval in this ordering. A compressed suffix array aims to support that search and recover those positions without necessarily storing the complete integer list in the naive form. This tiny example demonstrates suffix-array semantics; it does not imply that compression overhead is worthwhile for a seven-character text.

Illustrative case study

In a fictional archive project, a team needs frequent counts of short exact strings and occasional lists of their positions. A compressed suffix-array implementation keeps the index within its memory budget, but locating many occurrences costs more than returning a count. The team chooses sampling parameters based on that query mix and measures construction resources separately. It also checks text-extraction requirements before removing any separate source copy. This case illustrates how supported operations determine whether a compact index suits the application.

Common misconceptions and mistakes

A compressed suffix array is not simply a conventional array placed inside a general-purpose archive. It does not store every suffix as a full copied string. Compression does not guarantee faster queries, and a good counting time does not imply equally fast location reporting. Another mistake is assuming that every structure bearing the name has identical bounds or supports updates. A suffix array also differs from a suffix tree, although compressed versions of the two can share supporting components.

Business use

For text or sequence infrastructure, evaluate total space, build time, peak memory and the actual mix of count, locate and extract queries. Include repetitive and less compressible data. Specify the alphabet, sentinel convention and position indexing so returned locations are interpreted correctly. If the collection changes often, account for update or rebuild costs. The useful comparison is against alternatives under the same workload, rather than one headline compression ratio.

Check your understanding

In the sorted suffixes of "banana$", the pattern "ana" matches starts 3 and 1. Must a search scan every original text position to count those matches?

Answer: A suitable suffix-based index can identify the matching interval and derive its size without a full position-by-position scan.

Related terms

FM-index
Sampling
Suffix array
suffix
lexicographic order
compressed text index
self-index
suffix tree
count query
locate query

Learn next

Learn ordinary suffix arrays and backward or navigational search next. Build the suffix order for a short text, identify pattern intervals, then examine how a compressed design recovers positions from sampled information.

Sources

Navarro and Mäkinen, compressed full-text indexing survey: https://www.cs.helsinki.fi/u/vmakinen/papers/survey.pdf University of Helsinki, compressed data-structure implementations: https://www.cs.helsinki.fi/u/vmakinen/software/index.html Primary author-survey and research-software excerpts consulted; full source and editorial review remain pending.

Previous: Compressed pattern matching Next: Compression artifact