Каково значение суффиксов, сортируемых в массив суффиксов?

Question

Я знаю, что само определение суффиксного массива состоит в том, что это отсортированный массив всех суффиксов строки. Но я пытаюсь понять, каково значение этой операции сортировки здесь? Предположим, что мы создаем массив всех суффиксов строки и выбираем не сортировать его и продолжаем создавать массив LCP, что мы теряем в этой ситуации, когда пытаемся решить такие распространенные проблемы, как подстрока Longest Palindromic, Самая длинная повторяющаяся подстрока?

Answer 1

Есть две основные причины, по которым вы хотите отсортировать все суффиксы внутри суффиксного массива.

Во-первых, если S и T - строки, мы знаем следующее:

T является подстрокой S, если и только если это префикс суффикса S.

Например, если S - это "избегание", а T - "ida", тогда T - это подстрока S, потому что это префикс суффикса "idance". Поэтому приложения, которым требуются быстрые запросы о подстроках S, можно перефразировать в терминах поиска префиксов суффиксов S.

Учитывая это, если вы заинтересованы в поиске префиксов суффиксов S, имеет смысл хранить эти суффиксы в структуре данных, которая обеспечивает быстрый поиск. Если мы помещаем суффиксы в массив, сохраняя их отсортированными, то вы можете посмотреть, где должны быть эффективны различные префиксы. Следовательно, наличие суффиксного массива в виде массива всех суффиксов S, сохраненных в отсортированном порядке, позволяет осуществлять быстрый поиск префиксов суффиксов и, следовательно, подстрок S.

Что касается вашего второго вопроса о массивах LCP - вы могли бы вычислить их, если бы суффиксы не были отсортированы, и что бы вы потеряли, если бы сделали? - вы абсолютно можете вычислить их для любого массива, даже для несортированного массива суффиксов, поэтому нет никаких фундаментальных причин, почему вы не могли этого сделать. Однако массив LCP массива отсортированных суффиксов имеет множество приятных свойств, которых нет у массива LCP массива несортированных суффиксов. Например, массив LCP в массиве суффиксов может использоваться для определения глубины внутренних узлов в соответствующем дереве суффиксов или для вычисления самых длинных общих расширений и т. Д.

Одним из чрезвычайно важных свойств отсортированных массивов суффиксов и LCP является то, что если вы вычисляете парную информацию LCP для всех строк, вы можете вычислить LCP по произвольным парам строк, выполнив запрос минимального диапазона по массиву LCP. Причина, по которой это работает, заключается в том, что если суффиксы отсортированы, максимальное количество совпадений между смежными строками сохраняется. Это не работает в случае, когда массив не отсортирован (я упомяну это в самом конце снова.)

Чтобы конкретно увидеть, где что-то сломалось, давайте рассмотрим самую длинную повторяющуюся проблему подстроки. Обычный алгоритм линейного времени для этого с использованием массивов суффиксов следующий:

• Создайте массив суффиксов для строки T.
• Создайте массив LCP для обобщенного массива суффиксов.
• Выполните итерацию по массиву суффиксов и найдите строку, значение LCP которой является максимальным.

Важно подумать о том, почему этот последний шаг работает. Рассмотрим любую подстроку, которая повторяется дважды, назовите ее S. Поскольку любая подстрока является префиксом суффикса, это означает, что строки Sα и Sβ должны быть суффиксами строки T. Если вы храните массив суффиксов в отсортированном порядке, то все строки начинающиеся с префикса S будут последовательно появляться в массиве суффиксов (понимаете почему?). Следовательно, если S - самая длинная повторяющаяся подстрока, то первый суффикс, начинающийся с S, имеет LCP со следующей строкой длины |S|.

Теперь рассмотрим, что произойдет, если вы сделаете это без сортировки массива. В этом случае, если S - самая длинная повторяющаяся подстрока, строки Sα и Sβ по-прежнему будут суффиксами строки T. Однако они не обязательно будут последовательными в массиве суффиксов, и поэтому не обязательно будет линейно алгоритм времени их нахождения. Например, рассмотрим строку

abracadabra

Несортированный массив суффиксов

abracadabra$
bracadabra$
racadabra$
acadabra$
cadabra$
adabra$
dabra$
abra$
bra$
ra$
a$
$

После аннотирования с помощью информации LCP, мы получаем

0 abracadabra$
0 bracadabra$
0 racadabra$
0 acadabra$
0 cadabra$
0 adabra$
0 dabra$
0 abra$
0 bra$
0 ra$
0 a$
  $

Таким образом, вы можете видеть, что этот алгоритм не найдет "abra", потому что они не являются последовательными. Вы все еще можете понять, что это была "абра", испробовав все пары, но это не эффективно для больших строк.

Ранее я упоминал, что информация LCP о смежных парах строк в отсортированных суффиксных массивах может использоваться для вычисления информации LCP о произвольных парах строк в отсортированных суффиксных массивах. Это не так, если строки не отсортированы; выше, вы можете видеть, что все строки имеют соседний парный LCP, равный 0, хотя некоторые строки, безусловно, имеют ненулевой общий префикс.

Надеюсь это поможет!