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

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

Во-первых, если 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$
  $

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

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

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