Модуль 20 ⏱ ~26 мин чтения 📐 1 Mermaid диаграмм

6. Suffix array

Введение: Пространство против Времени

В предыдущей статье мы подробно разобрали 5. Trie для строк — структуру, непревзойденную для префиксных запросов и URL-маршрутизации. Но у Trie есть фундаментальный недостаток: он хранит разветвленную паутину указателей на узлы, что при обработке больших текстов или бинарных дампов приводит к колоссальному оверхеду оперативной памяти.

Классическое Суффиксное дерево (Suffix Tree) позволяет решать задачи поиска любых подстрок за линейное время, однако его реализация чрезвычайно сложна (алгоритм Укконена), а потребление памяти в 10–20 раз превосходит объем самого исходного текста!

Suffix Array (Массив Суффиксов) — это признанный шедевр алгоритмического минимализма (предложен Уди Манбером и Джином Майерсом в 1990 году). Это не дерево и не граф. Это просто отсортированный массив индексов, указывающих на позиции начал всех суффиксов строки.

Вместо сложной сети указателей мы получаем компактный плоский срез []int, который идеально укладывается в процессорный кэш, элементарно сериализуется на диск и позволяет решать сложнейшие задачи строкового анализа: моментальный поиск подстрок, нахождение самого длинного повторяющегося фрагмента, вычисление LCP (Longest Common Prefix) и сжатие данных с помощью преобразования Барроуза-Уиллера (BWT).

Математическое определение и инвариант

Для строки S длины n массив суффиксов SA — это перестановка чисел от 0 до n-1, такая что суффиксы S[SA[0]..n-1], S[SA[1]..n-1], ..., S[SA[n-1]..n-1] отсортированы в строгом лексикографическом порядке.

Рассмотрим канонический пример для строки banana$ (где символ $ — специальный терминальный символ, лексикографически меньший любого другого байта):

Суффиксы строки:

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

Отсортированные суффиксы:

  1. $ (индекс 6)
  2. a$ (индекс 5)
  3. ana$ (индекс 3)
  4. anana$ (индекс 1)
  5. banana$ (индекс 0)
  6. na$ (индекс 4)
  7. nana$ (индекс 2)

Итоговый массив SA: [6, 5, 3, 1, 0, 4, 2] (или [6, 5, 3, 1, 4, 2] для a$, ana$, anana$, banana$, na$, nana$).

flowchart LR
    S["Строка banana<br>Длина N=6"] --> Gen["Генерация индексов<br>0 1 2 3 4 5"]
    Gen --> Sort["Сортировка по суффиксам<br>лексикографически"]
    Sort --> SA["Результат SA массив<br>5 4 3 1 0 2"]
    SA --> Use["Использование<br>Бинарный поиск LCP"]

    classDef default fill:#131d33,stroke:#38bdf8,stroke-width:1.5px,color:#f8fafc;
    classDef saNode fill:#065f46,stroke:#34d399,stroke-width:2px,color:#ffffff;
    class SA saNode;

Ключевой инвариант: SA содержит исключительно 32-битные или 64-битные целые числа. Никаких структур, никаких указателей в кучу. Это монолитный массив плотных данных.

Построение: От наивного к O(N log N)

Наивный подход

Создать слайс всех суффиксов как подстрок и вызвать стандартную сортировку.
Создание n строк занимает O(N²) памяти (даже с учётом sharing, Go создаёт заголовки строк). Сравнение двух строк может занять O(N). Итог: O(N² log N). Неприемлемо для N > 10⁴.

Алгоритм удвоения Doubling Algorithm

Идея: сортируем суффиксы по префиксам длины 1, 2, 4, 8, ..., пока длина не превысит n.
На шаге k у нас уже есть ранги всех подстрок длины 2^k. Чтобы отсортировать по длине 2^{k+1}, каждая подстрока представляется как пара (rank[i], rank[i + 2^k]). Сортируем эти пары. Поскольку ранги лежат в диапазоне [0, n], сортировку можно выполнить за O(N) (radix sort) или O(N log N) (стандартная сортировка).

Общая сложность: O(N log² N) при использовании sort.Slice или O(N log N) с Radix Sort.

Production-реализация на Go 1.21+

Ниже представлена надежная реализация построения Suffix Array и вычисления LCP-массива (Longest Common Prefix).

Go 
package suffix

import (
    "sort"
)

// SuffixArray строит массив суффиксов для строки s.
// Сложность O N log^2 N, Память O N.
// Использует терминальный символ, меньший любого байта в s.
func SuffixArray(s string) []int {
    n := len(s)
    if n == 0 {
        return nil
    }

    // rank хранит ранг подстроки, начинающейся в i, длиной 2^k
    // tmp используется для сортировки пар
    sa := make([]int, n)
    rank := make([]int, n)
    tmp := make([]int, n)

    for i := 0; i < n; i++ {
        sa[i] = i
        rank[i] = int(s[i])
    }

    for k := 1; k < n; k <<= 1 {
        // Сортируем по парам (rank[i], rank[i+k])
        // Вместо создания структур используем сравнение на лету
        sort.Slice(sa, func(i, j int) bool {
            r1, r2 := rank[sa[i]], rank[sa[j]]
            if r1 != r2 {
                return r1 < r2
            }
            r1 = -1
            if sa[i]+k < n {
                r1 = rank[sa[i]+k]
            }
            r2 = -1
            if sa[j]+k < n {
                r2 = rank[sa[j]+k]
            }
            return r1 < r2
        })

        // Пересчитываем ранги
        tmp[sa[0]] = 0
        for i := 1; i < n; i++ {
            // Сравниваем пары текущих элементов sa
            same := rank[sa[i]] == rank[sa[i-1]]
            if same {
                r1 := -1
                if sa[i]+k < n { r1 = rank[sa[i]+k] }
                r2 := -1
                if sa[i-1]+k < n { r2 = rank[sa[i-1]+k] }
                same = r1 == r2
            }
            if same {
                tmp[sa[i]] = tmp[sa[i-1]]
            } else {
                tmp[sa[i]] = tmp[sa[i-1]] + 1
            }
        }
        copy(rank, tmp)
        if rank[sa[n-1]] >= n-1 {
            break // Все ранги уникальны
        }
    }

    return sa
}

// LCPArray вычисляет массив наибольших общих префиксов за O N.
// Использует алгоритм Касая. Требует инвертированный массив SA для O 1 доступа.
func LCPArray(s string, sa []int) []int {
    n := len(s)
    if n == 0 {
        return nil
    }

    lcp := make([]int, n)
    rank := make([]int, n)
    for i := 0; i < n; i++ {
        rank[sa[i]] = i
    }

    k := 0
    for i := 0; i < n; i++ {
        if rank[i] > 0 {
            j := sa[rank[i]-1] // Предыдущий суффикс в отсортированном порядке
            for i+k < n && j+k < n && s[i+k] == s[j+k] {
                k++
            }
            lcp[rank[i]] = k
            if k > 0 {
                k--
            }
        }
    }
    return lcp
}

Инженерные решения:

  • Алгоритм Касая (Kasai's Algorithm): Позволяет вычислить LCP за строгое O(N), используя свойство LCP(rank[i]) ≥ LCP(rank[i-1]) - 1. Это избавляет от необходимости сравнивать символы заново с нулевой позиции.
  • Экономия памяти: Мы выделяем 3–4 целочисленных массива int размером $N$. Для N=10⁶ это всего ~16 МБ RAM. Никаких указателей и скрытых аллокаций.
  • Сравнение пар: Вместо упаковки в struct используем замыкание внутри sort.Slice.

Mechanical Sympathy: Кэш-линии, TLB и GC

Suffix Array — непревзойденный пример структуры данных, уважающей аппаратное обеспечение:

Плотность и Cache Locality

Срезы sa и rank представляют собой единые непрерывные блоки int. При выполнении бинарного поиска паттерна в SA мы последовательно читаем ячейки sa[mid], а затем переходим к s[sa[mid]...]. Поскольку массив sa компактен, он практически целиком оседает в L2/L3-кэше процессора. Чтение подстроки s[sa[mid]+k] подхватывается аппаратным Prefetcher-ом, загружающим 64-байтные кэш-линии на максимальной скорости шины.

Давление на GC и аллокации

В наивной реализации sort.Slice мог бы порождать новые строки s[i:], создавая $N$ заголовков StringHeader в куче. В нашей реализации мы оперируем исключительно индексами int. Компилятор Go видит, что базовая строка s неизменна. Сборщик мусора не видит новых динамических объектов, а паузы Stop-The-World (STW) остаются нулевыми.

Эффективность TLB (TLB Hit Rate)

Массив sa занимает минимальное количество страниц виртуальной памяти (в отличие от Trie, где узлы хаотично разбросаны по разным адресам кучи). Это сводит к нулю промахи буфера ассоциативной трансляции (TLB miss) и ошибки отсутствия страниц (page faults), что крайне важно для сервисов в Linux cgroups с жесткими лимитами памяти.

Поиск подстроки и применение в бэкенде

Построив массивы SA и LCP, мы получаем мощные инструменты:

  1. Поиск паттерна P: Двоичный поиск по SA. Сравниваем P с суффиксом S[SA[mid]...]. Сложность O(|P| * log N).
  2. Поиск всех вхождений: После нахождения одного совпадения расширяем границы диапазона влево и вправо, пока LCP >= |P|.
  3. Longest Repeated Substring: Находится как максимальный элемент массива LCP.
  4. Counting Distinct Substrings: Число уникальных подстрок рассчитывается по формуле $\sum (N - SA[i] - LCP[i])$ (Σ (N - SA[i] - LCP[i])).
Go 
// FindOccurrences возвращает индексы всех вхождений pattern в s.
// Требует предвычисленный sa и lcp.
func FindOccurrences(s string, sa, lcp []int, pattern string) []int {
    n := len(s)
    m := len(pattern)
    if m == 0 || n == 0 {
        return nil
    }

    // Бинарный поиск левой границы
    l, r := 0, n
    for l < r {
        mid := l + (r-l)/2
        idx := sa[mid]
        // Сравнение паттерна с суффиксом
        cmp := 0
        for i := 0; i < m && idx+i < n; i++ {
            if pattern[i] < s[idx+i] { cmp = -1; break }
            if pattern[i] > s[idx+i] { cmp = 1; break }
        }
        if cmp < 0 || (cmp == 0 && m > n-idx) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    start := l

    // Бинарный поиск правой границы
    l, r = start, n
    for l < r {
        mid := l + (r-l)/2
        idx := sa[mid]
        cmp := 0
        for i := 0; i < m && idx+i < n; i++ {
            if pattern[i] < s[idx+i] { cmp = -1; break }
            if pattern[i] > s[idx+i] { cmp = 1; break }
        }
        if cmp > 0 || (cmp == 0 && m > n-idx) {
            r = mid
        } else {
            l = mid + 1
        }
    }
    end := l

    if start >= end {
        return nil
    }

    res := make([]int, 0, end-start)
    for i := start; i < end; i++ {
        res = append(res, sa[i])
    }
    return res
}

Интервью и хардкор-вопросы

Итог

  • Suffix Array — компактная альтернатива Suffix Tree, представляющая собой отсортированный массив индексов суффиксов.
  • Построение за O N log^2 N через алгоритм удвоения практично и реализуемо. Алгоритм Касая вычисляет LCP за строго O N.
  • В Go реализация работает с непрерывными массивами int, минимизируя аллокации, давление на GC и улучшая cache locality. Срез строк s[i:] не копирует байты, что экономит память.
  • Применение: точный поиск паттернов за O M log N, подсчёт уникальных подстрок, нахождение longest repeat. Не подходит для fuzzy search.
  • Интервью фокус: знание Kasai's algorithm, инвариантов удвоения, сравнение памяти с Trie/Tree.
  • Production паттерн: преаллокация []int, явные проверки границ в бинарном поиске, использование терминальных символов для корректной сортировки.

Suffix Array покрывает задачи точного поиска и анализа повторяющихся фрагментов с минимальным расходом памяти. Однако когда требуется навигация по структуре подстрок, вставка/удаление символов или более сложные операции над суффиксами, массив индексов становится слишком статичным. В таких случаях инженеры возвращаются к указательным структурам, но уже оптимизированным для сжатия. В следующей статье мы детально разберём структуру, которая объединяет мощь Trie и эффективность массива, устраняя цепочки узлов с одним потомком и становясь стандартом для маршрутизаторов и поисковых движков.

7. Suffix tree