Суффиксный массив: отсортировать все места, откуда можно читать

Если ты выпишешь суффиксный массив слова kokos, найдёшь по нему все вхождения ko и объяснишь, почему массив хранит числа, а не суффиксы, - листай до «Теперь сам».

Как думаешь, что готовить - образец или текст

Текст из 10 000 символов лежит на диске и не меняется. К нему приходит тысяча запросов: «встречается ли такая строка и где». КМП на каждый запрос читает текст целиком - 12 с половиной тысяч сравнений, на тысячу запросов двенадцать с половиной миллионов.

Все алгоритмы прошлых глав готовили образец. Прежде чем читать дальше, подумай: что можно один раз сделать с ТЕКСТОМ, чтобы каждый следующий запрос стоил сотню действий? Подсказка лежит на последних страницах любого справочника.

На что это похоже

Представь алфавитный указатель в конце книги. Слова в нём отсортированы, поэтому нужное находится делением пополам: открыл середину, понял, раньше или позже, - и так несколько раз. Рядом со словом стоят номера страниц.

Такую заранее построенную вспомогательную структуру, по которой ищут вместо самого текста, называют индексом. Обычный указатель составлен по словам, и найти в нём можно только то, что автор счёл словом. Суффиксный массив - указатель, составленный по ВСЕМ местам текста, откуда можно начать читать. В нём нет ни одного слова, только номера позиций, но стоят они в таком порядке, как если бы текст, читаемый с каждой позиции, был словом словаря.

Механизм: суффиксы, их порядок и массив чисел

Суффикс текста - его кусок от позиции i до конца. У текста длины n суффиксов n. Сравниваются суффиксы как слова в словаре: по первому различающемуся символу, а если одна строка - начало другой, меньше та, что короче. Так же работает знак < между строками в Python. Суффиксный массив sa - номера начал суффиксов, выписанные в порядке возрастания самих суффиксов.

текст: banana

начало   суффикс              после сортировки:    sa     суффикс
  0      banana                                     5     a
  1      anana                                      3     ana
  2      nana                                       1     anana
  3      ana                                        0     banana
  4      na                                         4     na
  5      a                                          2     nana

Массив - это столбец sa: [5, 3, 1, 0, 4, 2]. Правый столбец хранить не нужно: суффикс с номером 3 - это t[3:], он и так лежит в тексте.

Теперь главное наблюдение. Любая подстрока - это начало какого-то суффикса: nan - начало суффикса nana. Значит, все вхождения образца - это суффиксы, которые с него начинаются. А в отсортированном списке такие суффиксы стоят подряд:

образец ana:    sa[1] = 3,  sa[2] = 1        вхождения с позиций 3 и 1
образец na:     sa[4] = 4,  sa[5] = 2        вхождения с позиций 4 и 2
образец nab:    таких суффиксов нет          образец не встречается

Границы такого отрезка находит двоичный поиск - тот же, что в разделе про поиск, только сравниваются не числа, а первые m символов суффикса с образцом.

Правило

Суффиксный массив - перестановка чисел от 0 до n − 1, в которой суффикс t[sa[i]:] меньше суффикса t[sa[i + 1]:]. Все вхождения образца длины m занимают в массиве сплошной отрезок; его левая и правая границы находятся двумя двоичными поисками, каждый - не больше log₂ n + 1 кругов по m символов. Число вхождений равно длине отрезка и получается без их перечисления. Позиции внутри отрезка идут в порядке суффиксов, а не в порядке текста.

Разбор: строим срезами и ищем двоичным поиском

def suf_massiv(t):
    pary = []
    i = 0
    while i < len(t):
        pary.append([t[i:], i])       # суффикс и номер его начала
        i = i + 1
    pary.sort()                       # списки сравниваются по первому элементу
    sa = []
    for para in pary:
        sa.append(para[1])            # суффиксы больше не нужны, остаются номера
    return sa

def granica(t, sa, p, strogo):
    m = len(p)
    lo = 0
    hi = len(sa)
    krugov = 0
    while lo < hi:
        krugov = krugov + 1
        mid = (lo + hi) // 2
        kusok = t[sa[mid]:sa[mid] + m]            # первые m символов суффикса
        if kusok < p or (strogo and kusok == p):
            lo = mid + 1
        else:
            hi = mid
    return [lo, krugov]

granica с strogo = False возвращает первое место в массиве, где начало суффикса не меньше образца; с strogo = True - первое место, где оно строго больше. Между ними лежат вхождения.

sa = suf_massiv("banana")                     [5, 3, 1, 0, 4, 2]
granica("banana", sa, "ana", False)           [1, 3]     левая граница 1, три круга
granica("banana", sa, "ana", True)            [3, 3]     правая граница 3
вхождений 3 − 1 = 2,  позиции sa[1], sa[2] = 3, 1

Теперь на большом тексте: t = tekst(10000, 4, 1), образец - шесть символов t[5000:5006].

левая граница     8535     13 кругов
правая граница    8538     14 кругов
вхождений 3:   позиции (после сортировки по возрастанию) 1430, 4847, 5000

Ответ на вопрос из начала урока. 27 кругов, в каждом кусок из шести символов сравнивается с образцом один или два раза - меньше 250 сравнений символов вместо 12 455 у КМП. Образец ccc даёт отрезок от 6515 до 6674: 159 вхождений, и это число известно сразу, без единого шага по самим вхождениям.

Разбор: цена построения и удвоение

Построение срезами честное, но дорогое. Список pary держит все суффиксы целиком: n + (n − 1) + … + 1 символов, около n² / 2. Для текста в сто тысяч символов это пять миллиардов. Второй способ суффиксы не копирует вовсе.

Идея удвоения: сначала отсортировать суффиксы по первому символу. Потом по первым двум, потом по четырём, по восьми. Трюк в том, что первые 2k символов суффикса i - это первые k символов суффикса i и первые k символов суффикса i + k, а порядок по k символам уже известен для ВСЕХ суффиксов и записан числами-рангами. Значит, на каждом круге сортируются не строки, а пары чисел.

def suf_udvoenie(t):
    n = len(t)
    rang = []
    for c in t:
        rang.append(ord(c))                       # порядок по одному символу
    k = 1
    while True:
        klyuchi = []
        i = 0
        while i < n:
            vtoroj = -1                           # суффикс короче - идёт раньше
            if i + k < n:
                vtoroj = rang[i + k]
            klyuchi.append([rang[i], vtoroj, i])
            i = i + 1
        klyuchi.sort()                            # пары чисел, а не строки
        novyj = [0] * n
        r = 0
        j = 1
        while j < n:
            if klyuchi[j][0] != klyuchi[j - 1][0] or klyuchi[j][1] != klyuchi[j - 1][1]:
                r = r + 1                         # новая пара - новый ранг
            novyj[klyuchi[j][2]] = r
            j = j + 1
        rang = novyj
        if r == n - 1:
            break                                 # все ранги разные - порядок установлен
        k = k * 2
    sa = []
    for kl in klyuchi:
        sa.append(kl[2])
    return sa

Кругов не больше log₂ n, потому что длина сравниваемого начала удваивается. Каждый круг - сортировка n пар, то есть порядка n · log n действий; всего n · log n · log n, что записывают как n · log² n. Замер в шагах движка, случайный текст из четырёх букв:

  n       срезами     удвоением
 200       23 643       13 372
 400       87 672       36 073
 800      336 129       75 152

При удвоении n первый столбец растёт почти вчетверо, второй - в два-три раза. И это ещё льстит первому способу: движок берёт за сортировку n · log n шагов и не считает, сколько символов читает каждое сравнение суффиксов. На тексте из одинаковых букв оно читает суффиксы почти целиком.

Существуют алгоритмы, строящие суффиксный массив за линейное время; в библиотеках стоят они. Удвоение - то, что пишется руками за десять минут и чего хватает до сотен тысяч символов.

Что ломается без этого

Первое: сравнение с суффиксом целиком. Если в двоичном поиске сравнивать p с t[sa[mid]:], а не с первыми m его символами, то для образца an в слове banana суффиксы ana и anana окажутся «больше» образца, правая граница совпадёт с левой, и выйдет ноль вхождений вместо двух. Вхождение - это суффикс, который НАЧИНАЕТСЯ с образца, а не равен ему.

Второе: позиции приняты за отсортированные. Отрезок массива даёт 3, 1 для ana и 1430, 4847, 5000 только после отдельной сортировки. Если вхождения нужны в порядке текста, их надо упорядочить.

Третье: текст изменился, индекс остался. Символ, дописанный в конец, меняет КАЖДЫЙ суффикс и может переставить их: в тексте aa суффикс с позиции 1 (a) меньше суффикса с позиции 0 (aa), а после дописывания b наоборот - aab меньше ab. Суффиксный массив - структура для неизменного текста; после правки он перестраивается.

Четвёртое: ранги не пересчитаны, а только переставлены. В удвоении равные пары обязаны получить РАВНЫЙ ранг. Если раздать ранги просто по порядку после сортировки, на следующем круге случайный порядок среди равных будет принят за настоящий - и массив выйдет неверным на строках с повторами.

Зачем это в работе

Первый сюжет - поиск по неизменному корпусу: архив документов, исходный код, справочник. Индекс строится один раз, запрос любой строки стоит m · log n, а не длину корпуса.

Второй - геномы. Запись генома человека - три миллиарда букв, прочитанных фрагментов - сотни миллионов, и каждый надо найти в геноме. Суффиксный массив и его сжатые потомки - основа программ, которые это делают. Четыре байта на позицию дают двенадцать гигабайт на один массив, и отсюда вырос целый раздел про сжатые индексы; к ним вернёмся в главе про преобразование Барроуза-Уилера.

Третий - сжатие и сравнение файлов. Программы, которые строят двоичные заплатки для обновлений, ищут в старой версии самые длинные куски, совпадающие с новой, - через суффиксный массив старого файла.

Теперь сам

Выпиши суффиксный массив слова kokos. Затем по нему найди, сколько раз и с каких позиций входит ko.

начало   суффикс         после сортировки:    sa     суффикс
  0      kokos                                 0     kokos
  1      okos                                  2     kos
  2      kos                                   1     okos
  3      os                                    3     os
  4      s                                     4     s