Я делюсь своим опытом работы с различными алгоритмами построения массива суффиксов (SACA).
Визуализатор дерева суффиксов https://visualgo.net/en/suffixtree

Несколько лет назад я наткнулся на эту прекрасную структуру данных Suffix Tree. Я должен признать, что его конструкция немного сложна. Изучая больше об этом, я прочитал о Suffix Array. Существует так много алгоритмов, разрабатываемых с учетом широкого применения массива суффиксов в сопоставлении шаблонов, сжатии, секвенировании генома. Эти алгоритмы можно разделить на три категории.

  • Удвоение префикса — Манабер-мейерс/Ларссон-Садакане
  • Рекурсивный алгоритм — DC3, алгоритм KA, алгоритм NZC
  • Индуцированная сортировка — алгоритм S/алгоритм MF

Полную таксономию этих алгоритмов можно найти здесь

Ключевая идея заключается в том, что если вы выполняете циклическое вращение в каждой позиции данной строки, сортируете ее и удаляете все после $ из каждой строки, у вас будет отсортированный суффикс. Давайте посмотрим на это на примере String = ababa Добавьте $ в конце, это поможет идентифицировать каждый уникальный суффикс, например, попробуйте создать дерево суффиксов для папы, это будет pa apa papa

a и apa имеют общий префикс a , поэтому суффикс «a» невидим, чтобы исправить это, мы добавляем суффиксы $ теперь $ a$ pa$ apa$ papa$

Итак, наша входная строка — ababaa$. Давайте сделаем циклическое вращение, отсортируем ее и удалим все после символа $. Циклическое вращение есть не что иное, как начало с каждого индекса с учетом каждого символа и, наконец, окончание в одной предыдущей позиции.

Таким образом, окончательный массив суффиксов будет [6, 5, 4, 2, 0, 3, 1]. Теперь, как преобразовать это в эффективный алгоритм. Сначала мы будем сортировать 1 символ, а затем на каждой итерации удваивать, поэтому общее количество итераций будет log(n) , на каждой итерации мы будем выполнять цикл «n» для вычисления «порядка» и «ранга». Таким образом, общая сложность будет O(n log(n)) Давайте объясним этот порядок и ранг.

порядок: индекс суффикса в лексикографическом порядке в этом цикле сканирования. ранг: различные типы строк, с которыми мы столкнулись в этом цикле сканирования.

Начнем с 1 ababaa$ Сортировка подсчета Частичная сумма [число] $ -> 1 $ -> 1 a -> 4 a -> 5
b -> 2 b -> 7

Сканирование от обратного Каждый счет[символ] — порядок [счет[символ] —] = позиция

абабаа$

Мы просматриваем входную строку в обратном направлении и знаем, основываясь на сортировке couting, что они равны 1 $, 4 a и 2 b, поэтому a заканчивается (количество $) + количество a, т.е. на 5, аналогично b заканчивается на 7 Еще одна вещь — это стабильная сортировка, т. е. если мы встретим 2, порядок a будет определяться на основе порядка появления в строке. Итак, у нас есть 4 a с индексами 0,2,4,5, и в массиве суффиксов они идут в том же порядке. Вот как мы рассчитали порядок, когда брали по 1 символу за раз.

массив рангов: каждый выделенный символ встречается в порядке ранга = [0,1,1,1,1,2,2], потому что есть только 3 разных элемента, т.е. $, a, b

Аналогично, в следующей итерации мы будем брать по 2 символа за раз из порядка/ранга предыдущего цикла. 0123456 Оригинал = ababaa$ порядок = [6, 0, 2, 4, 5, 1, 3] ранг = [0, 1, 1, 1, 1, 2, 2]

Сканировать порядок предыдущего цикла сзади. Получить его порядок и переместить позицию L назад и получить класс этого индекса. order[‘b’]= 3 переместить символ L назад, т.е. ‘a’ newOrder[rank[‘a’]]]== pos

Итак, после этой итерации у нас есть SA, когда берутся 2 символа за раз. Затем вычислите ранг для них, сравнив первую половину и вторую половину для следующей строки. Повторите тот же процесс теперь L = 2, и в следующей итерации мы удвоим, т.е. 2 символа назад.

  • БВТ
  • BWT помогает преобразовать и ввести строку, содержащую повторяющуюся подпоследовательность, в серии, а затем можно использовать кодирование длины серии для сжатия. Для заданной входной строки отсортируйте все циклические вращения в лексиграфическом порядке, и последний столбец даст вам BWT. Например, ababaa$ Обратитесь к таблице выше, BWT(ababaa$) = aabb$aa На самом деле они являются одним предыдущим символом в массиве суффиксов. Уловка в английском языке — это любое обычное слово, такое как и, когда суффикс отсортирован по предыдущим символам (в последнем столбце), будет a, и это будет способствовать запуску.
  • Инвертирование Давайте посмотрим, есть ли у нас BWT, можем ли мы восстановить исходную строку. Для наглядности пронумеруем a и b. Строка = 0b 0a 1b 1a 2a 3$
  • Наивный путь.
  • Как мы знаем, BWT является последним столбцом в отсортированном циклическом вращении. Мы также знаем, что первый столбец отсортирован.
  • объединить их, потому что мы знаем, что предшествует каждому отсортированному суффиксу, а затем отсортировать
  • a$ $a — -aa$a $ab — aa$ab $aba — aa$aba $abab-a a$abab $ababaa aa a$ — -a aa$ a$a — a aa$aa$ab — a аа$аб а$аба-а аа$аба а$абаба ба аа — -б баа аа$ — б баа$ аа$а — б баа$а аа$аб-б баа$аб аа$абаб ба Сорт-›аб — -b Соединение -› bab Сортировка →aba — b Соединение-›baba Сортировка-›abaa — b Соединение-›babaa Сортировка-›abaa$-bСоединение-›babaa$Сортировка-›abaa$ab
    $a ab — -$$ab aba — $$aba abab — $$abab ababa-$$ababa ababaa$ ab ba — -a aba baa — a abaa baa$ — a abaa$ baa$aa abaa$a baa$aba ab ba — -а аба баб — абаб баба — а абаба бабаа-а абабаа бабаа$а
  • Продолжайте делать это, и в конце концов мы получим входную строку. Но проблема в том, что требуется намного больше памяти.
  • Первое последнее свойство.
  • Наличие любого символа в первом и последнем столбце совпадает. Хитрость в том, что мы знаем, что BWT содержит символ, предшествующий массиву суффиксов (которые находятся в лексикографическом порядке). Итак, начнем с $ (потому что мы точно знаем, что это последний символ в исходной строке). Теперь BWT, соответствующий этому $, сообщает, что находится перед $, так что символ продолжается $ в исходной строке, выполняет поиск в первом столбце и снова находит соответствующий символ BWT. Повторяя этот процесс, мы произносим исходную строку. Возьмем пример выше $-›a1->a2->b1->a3->b2->a4->$ Итак, исходная строка ababaa$
  • Сопоставление с образцом с использованием сопоставления LF Далее рассмотрим, как BWT полезен при сопоставлении с образцом. Суть в том, чтобы начать поиск шаблона в обратном порядке, потому что BWT хранит то, что находится перед любым заданным символом. Например, чтобы найти aba в ababaaa, начните с ab a и посмотрите в первый столбец. Есть 4 места, начинающиеся с a, но только 2 имеют последние столбцы как b (строки 2 и 3). Выберите эти строки b и посмотрите, в каком из них последний столбец равен >aba , обе строки b имеют, поэтому aba встречается в исходном тексте 2 раза. Проблема с этим подходом заключается в том, что нужно линейно сканировать весь диапазон последнего столбца, чтобы найти символ. Это можно решить с помощью фильтра подсчета, который сохраняет в каждой строке для каждого символа его количество в последнем столбце. Итак, теперь, ища последний столбец, обратите внимание на диапазон перехода символа. Например
  • Поскольку a в первом столбце b изменяется от 0 до 2 , это означает, что в последнем столбце данного первого столбца a есть 2 b в последнем столбце. Перейдите к столбцу B, а затем найдите «a», и он изменится с 2 на 3, что означает, что это 1 a до того, как шаблон aba встречается в строке один раз.
  • FM-Index Есть еще 3 проблемы с описанным выше способом сопоставления с образцом.
  • Сканирование в последнем столбце может быть линейным сканированием и в худшем случае может быть O (n). Ключевая идея исправления состоит в том, чтобы хранить итоговую таблицу для появления каждого символа в последнем столбце. Например а |б — -| — — 0 | 0 1 | 0 2 | 0 2 | 1 2 | 2 3 | 2 4 | 2 В основном это говорит о том, сколько a и b видно в каждой строке, например, row = 3 , a=2 и b=1, т.е. видно 2 a и 1 b .
  • Теперь хранение таблицы такого типа также может занимать место, вместо этого мы сохраняем каждую 5-ю или около того (контрольную точку) запись и выводим требуемое значение из ближайшей контрольной точки. Это также решило вторую проблему экономии места.
  • Хранение массива count для каждого символа занимает O(n) * |alphabet|
  • Этот тип сопоставления с образцом не сообщает позицию, в которой происходит совпадение. Используйте массив суффиксов, но сохраняйте суффиксы в каждой другой позиции «k» относительно массива n без суффиксов. Это важно, потому что сохранение каждого k-го суффикса по отношению к T дает нам постоянное время до k, чтобы найти массив суффиксов, который не был доступен в данной позиции строки. Мы будем использовать сопоставление LF, чтобы найти строку, в которой присутствует значение массива суффиксов.
  • SA (строка) = SA (k) + количество переходов отображения LF.
  • Отпечаток памяти FM-Index Сначала мы сохраняем строки F и L, F - это в основном символ в отсортированном вхождении, просто сохраняем начальный индекс для каждого символа. L в основном представляет собой BWT из N , поэтому его размер будет O(n). Для контрольной точки мы сохраняем часть суммы, скажем, мы хотели a долю, поэтому общий размер будет n * a * размер_символа
  • Для SA , так как мы храним каждый k-й суффикс в T , общий размер будет n * k
  • Ссылка: https://www.youtube.com/watch?v=kvVGj5V65io&t=824s https://www.cs.jhu.edu/~langmea/resources/lecture_notes/bwt_and_fm_index.pdf
  • Дерево вейвлета Во время сопоставления с образцом мы должны искать последний столбец от 0 до начала/конца индекса первого символа. Как и при поиске aba, мы сначала переходим к первому столбцу и находим диапазон a, т.е. 1,4, а в последнем столбце мы должны найти b rank(1, b) и rank( 4, б) мы хотели найти количество b в последнем столбце от 0 до 1 и от 0 до 4. Мы достигли этого, используя массив count и некоторую оптимизацию в предыдущем разделе. Здесь мы увидим альтернативный подход с использованием дерева вейвлетов для ответа на эти запросы за время O (1). В общих чертах это шаги.
  • Кодировать первую половину строки как 0, а вторую половину как 1
  • Сгруппируйте каждый символ с кодировкой 0 как левое поддерево
  • Символ, закодированный в группе 1, как правое поддерево
  • Рекурсивно сделайте это.
  • Давайте посмотрим, как мы создаем вейвлет-дерево BWT aabb$aa {$,a} -> 0 {b} -> 1 aabb$aa 0011000 // aa$aa 11011
  • aabb$aa 0123456 Suppose we need to find rank(4,a) , since a is encoded as 0 find rank(0, 4) which would be 2. At this level 1, a is encoded as 1 so find rank(1,2), which would be 2. Take right child path this will be all a i.e. 1111, do a rank query of rank(1,2) which is 2 hence we rank(4,a) would be 2. https://alexbowe.com/wavelet-trees/ https://github.com/alexbowe/wavelet-paper/blob/master/thesis.pdf
  • Структура данных РРР. Узел дерева вейвлетов https://alexbowe.com/rrr/ при сохранении в виде последовательности RRR может отвечать на ранговые запросы за время O(1)

Первоначально опубликовано на https://github.com.