eduKate Sengkang

Small Group Tutorials

Here to help students catch up, keep up, and move ahead. Book a consultation here.

Chat on WhatsApp

How to Learn SA-IS Suffix Array Construction: L/S Types, LMS Substrings, Induced Sorting and Linear-Time Text Indexing

Quick Read. SA-IS constructs a suffix array in linear time by classifying suffixes into L- and S-types, identifying LMS positions, partially sorting those LMS suffixes, inducing the remaining suffix order from them, reducing repeated LMS substrings to a smaller naming problem and recursing only when necessary. The beginner should first understand suffix arrays and lexicographic order. The intermediate learner should trace L/S classification and bucket heads/tails. The advanced learner should understand induced sorting and recursive naming. The professional should understand sentinel handling, integer alphabets, memory layout, cache behaviour, BWT/LCP integration and validation against mature libraries.

One-sentence answer

SA-IS builds a suffix array by sorting only a carefully chosen subset of suffixes explicitly, then using bucket order and neighbouring suffix information to induce the order of all remaining suffixes in linear total work.

Why this algorithm exists

A suffix array stores the starting positions of all suffixes of a text in lexicographic order. Once built, it supports efficient pattern search and underlies compressed text indexes, Burrows–Wheeler-transform pipelines, bioinformatics tools and string-processing systems. The naïve construction method sorts n suffix strings directly, which can be expensive because comparing two suffixes may inspect many characters.

There are simpler O(n log n) suffix-array algorithms based on prefix doubling, and these are often the right first implementation. SA-IS matters because it shows how much more structure can be exploited: the full suffix order can be induced from a smaller set of boundary suffixes, giving linear time and space in the standard integer-alphabet model.

Level 1 — Beginner: what is a suffix array?

Take the string banana$, where $ is a unique sentinel smaller than every other character. Its suffixes are:

0 banana$
1 anana$
2 nana$
3 ana$
4 na$
5 a$
6 $

Sorted lexicographically, the starting positions are:

6 5 3 1 0 4 2

That integer array is the suffix array. SA-IS must produce exactly this ordering without repeatedly comparing whole suffix strings.

Classify positions as S-type and L-type

SA-IS compares each suffix conceptually with the suffix one position to its right.

  • Position i is S-type if suffix i is lexicographically smaller than suffix i+1.
  • Position i is L-type if suffix i is lexicographically larger than suffix i+1.
  • The sentinel position is S-type.

You do not compare whole suffixes. Scan from right to left:

if s[i] < s[i+1]: type[i] = S
if s[i] > s[i+1]: type[i] = L
if s[i] == s[i+1]: type[i] = type[i+1]

This single pass is the first elegant step: a global suffix comparison property can be assigned using only the next character and next type.

LMS positions: the boundaries that matter

An LMS position is an S-type position whose predecessor is L-type. LMS means “leftmost S-type.” These transition points divide the text into LMS substrings. There can be at most about n/2 LMS positions, so they form a naturally smaller subproblem.

Do not think of LMS suffixes as arbitrary samples. They are exactly the boundary suffixes from which the order of other suffixes can be induced efficiently.

Level 2 — Intermediate: buckets

All suffixes beginning with the same character occupy one contiguous bucket in the final suffix array. Within a character bucket, L-type suffixes come before S-type suffixes. SA-IS exploits this ordering with bucket heads and bucket tails.

  • Bucket head: next free slot from the left for inducing L-type suffixes.
  • Bucket tail: next free slot from the right for placing LMS or inducing S-type suffixes.

Count character frequencies once, compute each bucket’s boundaries, and reuse those boundaries during induced-sorting passes.

The core move: induced sorting

Suppose suffix i is already placed in the suffix array. Then suffix i−1 is just one character prepended to suffix i. If we know the first character s[i−1] and whether position i−1 is L or S, the bucket structure can place i−1 in the correct relative region.

Induce L-type suffixes

Scan the suffix array from left to right. Whenever it contains position i > 0 and i−1 is L-type, insert i−1 at the current head of the bucket for character s[i−1], then advance that bucket head.

Induce S-type suffixes

Scan the suffix array from right to left. Whenever it contains position i > 0 and i−1 is S-type, insert i−1 at the current tail of the appropriate bucket, then move that tail left.

place LMS suffixes at bucket tails

scan SA left to right:
    if SA[k] = i and i-1 is L-type:
        place i-1 at head of bucket s[i-1]

scan SA right to left:
    if SA[k] = i and i-1 is S-type:
        place i-1 at tail of bucket s[i-1]

This pair of passes is called induced sorting because the known order of placed suffixes causes the order of their predecessors to emerge without direct suffix comparison.

But where does the correct LMS order come from?

The first induced-sorting round starts from LMS positions placed by bucket. After the induced passes, read the LMS suffixes back out in their resulting order. Now compare adjacent LMS substrings and assign integer names: identical LMS substrings receive the same name; different ones receive increasing names.

If every LMS substring receives a unique name, their order is already determined. If names repeat, form a reduced string consisting of those names in original LMS order and recursively build its suffix array.

Level 3 — Advanced: why recursion remains linear

The reduced string has one symbol per LMS substring. Because LMS positions are separated by at least one non-LMS position, the reduced problem contains at most roughly n/2 symbols. Each recursion level performs linear scans plus one recursive call on a problem at most half as large:

T(n) ≤ T(n/2) + O(n) = O(n)

Once the reduced suffix array gives the exact LMS order, clear the working suffix array, place LMS suffixes at bucket tails in that order, induce L-types again, induce S-types again, and the complete suffix array is finished.

How to compare LMS substrings correctly

This detail causes many bugs. Two LMS substrings are equal only when their characters and type boundaries match up to and including the next LMS position. Stopping one character too early or treating repeated characters without their type information can assign incorrect names and corrupt the recursion.

For learning, write a slow, explicit LMS-substring comparison first. Optimise only after tests prove the naming stage correct.

Correctness: what should you prove?

  • The right-to-left type classification matches lexicographic comparison with the next suffix.
  • All suffixes beginning with one character belong to one bucket, with L-types before S-types inside that bucket.
  • If suffix i is already in correct relative order, scanning left-to-right can place an L-type predecessor i−1 in correct order at its bucket head.
  • The symmetric right-to-left pass correctly induces S-type predecessors at bucket tails.
  • The first induced sort gives enough information to lexicographically name LMS substrings.
  • Sorting the reduced string sorts LMS suffixes because the names preserve LMS-substring lexicographic order.
  • With LMS suffixes in correct order, the final two induced passes place every suffix correctly.

Learn these as separate lemmas. SA-IS is difficult when presented as one giant trick and much easier when presented as a chain of local invariants.

Sentinel and alphabet rules

The sentinel must be unique and lexicographically smaller than every genuine symbol. In integer implementations, a common strategy is to remap the input alphabet to positive integers and reserve 0 for the sentinel. If the input already uses arbitrary integers, coordinate compression or an alphabet-normalisation pass can provide the required range.

Do not silently assume byte strings if the public API claims to support general integer alphabets. Alphabet size affects bucket storage, validation and memory use.

Professional engineering

  • Reference implementation first: validate a clear version before applying in-place storage reuse.
  • Bucket reuse: heads and tails can often share frequency-derived arrays, but restore them correctly before each pass.
  • Type storage: one byte per type is simple; packed bits save memory but may reduce speed.
  • Memory bandwidth: mature SA-IS implementations are often limited by memory traffic rather than arithmetic.
  • Branch behaviour: classification and induced scans are good targets for branch reduction, but only after correctness.
  • Large inputs: 32-bit suffix positions cap input length; production libraries may provide separate 64-bit APIs.
  • Parallelism: suffix-array construction can benefit from multicore work, but scaling is often bounded by memory bandwidth.
  • BWT integration: SA-IS naturally connects to Burrows–Wheeler-transform construction; some implementations produce BWT-related outputs directly.
  • LCP construction: the longest-common-prefix array is a separate structure. Do not assume SA-IS automatically gives LCP unless the implementation explicitly computes it.

Testing ladder

  • Start with $, a$, aa$, ab$, banana$ and mississippi$.
  • For random short strings, construct suffixes explicitly, sort them with the language’s trusted comparator and compare the position array.
  • Test all-equal strings, alternating patterns, periodic strings and alphabets containing only two symbols.
  • Verify every suffix-array output is a permutation of 0..n−1.
  • Verify adjacent suffixes are in lexicographic order independently of the SA-IS code.
  • Stress sentinel remapping and maximum alphabet values.
  • Compare production-scale output against a mature external implementation such as libsais.

Common misconceptions

  • “L means the character is large and S means small.” The types describe suffix order relative to the suffix one position to the right.
  • “LMS suffixes are simply every second suffix.” They are specific L-to-S transition positions.
  • “The first LMS placement already sorts them exactly.” The first induced pass reveals LMS-substring order; repeated substrings may still require recursive naming.
  • “Induced sorting compares suffix strings.” Its power comes from avoiding those repeated comparisons.
  • “Linear time means SA-IS is always the best choice.” Simpler O(n log n) algorithms may be easier to maintain and can be fast enough for moderate inputs.

A learning route from beginner to professional

  • Beginner: build suffix arrays by explicitly sorting suffix strings.
  • Intermediate: implement prefix-doubling first, then learn L/S classification and bucket boundaries.
  • Advanced: hand-trace SA-IS on banana$, including LMS naming and the final induced passes.
  • Algorithm engineer: implement a readable SA-IS reference version and validate it exhaustively on short strings.
  • Professional: optimise memory reuse and cache behaviour, support integer alphabets and large indices, compare throughput against current libraries, and integrate only the BWT/LCP features the application actually needs.

For teaching, tracing is essential. Learners should predict every type label, every bucket placement and every induced predecessor before running code. Worked examples and gradual fading are especially useful because SA-IS combines several individually simple ideas whose interaction can overload a novice if introduced all at once.

Authoritative sources and further reading

Closing idea. SA-IS is not mainly a story about clever suffix notation. It is a story about using partial order to create more order. A small set of LMS boundaries is enough to organise the text; once those anchors are correct, bucket structure and predecessor relationships induce the rest. That is the transferable algorithmic lesson worth carrying beyond suffix arrays.