Самая длинная общая подстрока через массив суффиксов: действительно ли нам нужны уникальные часовые?

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

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

Это означает, что мы можем написать такой код:

for each character c in the shortest suffix
    if suffix_1[c] == suffix_2[c]
        increment count of common characters

Однако, чтобы облегчить это, нам нужно перепрыгнуть через некоторые препятствия, чтобы убедиться, что мы используем уникальных часовых, , о которых я спрашивал здесь.

Однако было бы более простым (для реализации) решением не было бы просто подсчитывать количество общих символов, останавливаясь, когда мы достигаем (единственного, уникального) сигнального символа, например:

set sentinel = '#'
for each character c in the shortest suffix
    if suffix_1[c] == suffix_2[c]
        if suffix_1[c] != sentinel
            increment count of common characters
        else
            return

Или мне здесь не хватает чего-то принципиального?


string algorithm data-structures longest-substring suffix-array
person Wad    schedule 29.08.2019    source источник
comment
Интуитивно ваше предложение звучит правильно, но я не эксперт в этом вопросе ...   -  person 500 - Internal Server Error    schedule 29.08.2019
comment
У меня точно такой же вопрос. Исходный код может помочь: github. com / williamfiset / Algorithms / tree / master / src / main / java /, но я не кодирую Java   -  person Tianyi Shi    schedule 01.11.2020
comment
Я даже не понимаю, зачем вообще нужен часовой. Если бы он был в суффиксе TREE, то для правильного обхода дерева необходим дозорный. Однако я действительно не вижу полезности часового в суффиксе ARRAY одной строки. Кроме того, даже при построении массива суффиксов из нескольких строк мы можем узнать, к какой исходной строке принадлежит символ, просмотрев его позицию, построив массив диапазонов, например. [[0,4], [4,6], [6,12]] для трех строк длиной 4, 2 и 6 (тогда, если у нас есть позиция, заданная SA, скажем, 5, мы знаем этот символ принадлежит второй строке)   -  person Tianyi Shi    schedule 01.11.2020

Ответы (2)


arrow_upward
0
arrow_downward

На самом деле я только что разработал алгоритм, который вообще не использует часовых: https://github.com/BurntSushi/suffix/issues/14

При объединении строк также запишите индексы границ (например, для 3 строк длиной 4, 2, 5 будут записаны границы 4, 6 и 11, поэтому мы знаем, что concatenated_string[5] принадлежит второй исходной строке, потому что 4<= 5 < 6).

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

person Tianyi Shi    schedule 01.11.2020

arrow_upward
0
arrow_downward

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

Более длинный ответ:

На высоком уровне основной алгоритм, описанный в видео, выглядит следующим образом:

  1. Создайте обобщенный массив суффиксов для строк T 1 и T 2.
  2. Создайте массив LCP для полученного массива суффиксов.
  3. Итерируйте по массиву LCP, ища смежные пары суффиксов, которые происходят из разных строк.
  4. Найдите самую большую LCP между любыми двумя такими строками; назовите это К.
  5. Извлеките первые k символов из любого из двух суффиксов.

Так где же здесь появляются часовые? В основном они возникают на этапах (1) и (2). Видео ссылается на использование алгоритма построения массива суффиксов линейного времени (SACA). Большинство быстрых SACA для генерации массивов суффиксов для двух или более строк предполагают в рамках своей работы наличие различных конечных маркеров на концах этих строк, и часто от этого зависит внутренняя правильность алгоритма. Таким образом, в этом смысле может потребоваться добавление конечных маркеров исключительно для использования быстрого SACA, полностью независимого от любого последующего использования, которое вы можете использовать.

(Зачем это нужно SACA? Некоторые из самых быстрых SACA, такие как алгоритм SA-IS, предполагают, что последний символ строки уникален, лексикографически предшествует всему и больше нигде не встречается. Чтобы использовать этот алгоритм с Для нескольких строк вам нужен какой-то внутренний разделитель, чтобы отметить, где заканчивается одна строка и начинается другая. Этот символ должен действовать как сильный, и теперь мы закончили с первым строковым символом, поэтому он должен лексикографически предшествовать всем другие персонажи.)

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

В этом смысле вы можете думать об этих часовых как о деталях реализации, необходимых для использования быстрого SACA, что вам нужно сделать, чтобы получить быстрое время выполнения.

person templatetypedef    schedule 01.11.2020