Как LCP помогает определить количество вхождений паттерна?

Я прочитал, что Longest Common Prefix (LCP) можно использовать для определения количества вхождений шаблона в строку.

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

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

Например, для этого массива суффиксов для banana:

LCP  Suffix entry
N/A  a  
1    ana  
3    anana  
0    banana  
0    na  
2    nana

Как LCP помогает найти количество вхождений подстроки типа "банан" или "на", для меня не очевидно.

Любая помощь, чтобы выяснить, как LCP помогает здесь?

Источник

2 ответа

Решение

Я не знаю никакого способа использования массива LCP вместо выполнения бинарного поиска, но я полагаю, что вы обращаетесь к методике, описанной Udi Manber и Gene Myers в массивах Suffix: новый метод для поиска строк в сети.

Идея такова: чтобы найти количество вхождений данной строки P (длина m) в текст T (длина N),

  • Вы используете бинарный поиск по массиву суффиксов T (как вы и предлагали)
  • Но вы ускоряете его, используя массив LCP в качестве вспомогательной структуры данных. Более конкретно, вы генерируете специальную версию массива LCP (я буду называть ее LCP-LR ниже) и используете ее.

Проблема с использованием стандартного двоичного поиска (без информации LCP) заключается в том, что в каждом из сравнений O(log N), которые вам необходимо выполнить, вы сравниваете P с текущей записью массива суффиксов, что означает полное сравнение строк до до м символов. Таким образом, сложность O(m*log N).

Массив LCP-LR помогает улучшить это значение до O(m+log N) следующим образом:

  • В любой точке алгоритма бинарного поиска вы, как обычно, рассматриваете диапазон (L,...,R) массива суффиксов и его центральную точку M и решаете, продолжать ли поиск в левом поддиапазоне (L,...,M) или в правом поддиапазоне (M,...,R).
  • Чтобы принять решение, вы сравниваете P со строкой в ​​M. Если P совпадает с M, все готово, но если нет, то вы сравните первые k символов P и затем решите, является ли P лексикографически меньшим или больше, чем M. Давайте предположим, что в результате P больше, чем M.

  • Итак, на следующем шаге вы рассматриваете (M,..., R) и новую центральную точку M'посередине:

                  M ...... M' ...... R
              |
       we know:
          lcp(P,M)==k

    Хитрость заключается в том, что LCP-LR предварительно вычисляется так, что O(1)-сканирование сообщает вам самый длинный общий префикс M и M', lcp(M,M').

    Вы уже знаете (из предыдущего шага), что сам M имеет префикс k общих символов с P: lcp(P,M)=k. Теперь есть три возможности:

    • Случай 1: k меньше общих префиксных символов с M, чем M с M'. Это означает, что (k+1)-й символ M'такой же, как и у M, и, поскольку P лексикографически больше, чем M, он также должен быть лексикографически больше, чем M'. Итак, мы продолжаем в правой половине (M',...,R).
    • Случай 2: k > lcp(M,M'), т. Е. P имеет больше общих префиксных символов с M, чем M общего с M'. Следовательно, если бы мы сравнили P с M', общий префикс был бы меньше k, а M' был бы лексикографически большим, чем P, поэтому без фактического сравнения мы продолжаем в левой половине (M,..., М ').
    • Случай 3: k == lcp(M,M'). Таким образом, M и M'идентичны с P в первых k символах. Чтобы решить, продолжим ли мы в левой или правой половине, достаточно сравнить P с M', начиная с (k+1)-го символа.

  • Продолжаем рекурсивно.

Общий эффект заключается в том, что ни один символ P не сравнивается с каким-либо символом текста более одного раза. Общее количество сравнений символов ограничено m, поэтому общая сложность действительно равна O(m+log N).

Очевидно, что остаётся ключевой вопрос: как мы предварительно вычислили LCP-LR, чтобы он мог сообщить нам за O (1) время lcp между любыми двумя записями массива суффиксов? Как вы сказали, стандартный массив LCP сообщает вам только о lcp последовательных записей, то есть lcp(x-1,x) для любого x. Но M и M'в приведенном выше описании не обязательно являются последовательными записями, так как это сделать?

Ключом к этому является осознание того, что только двоичные диапазоны (L,...,R) будут когда-либо встречаться во время двоичного поиска: он всегда начинается с (0,...,N) и делит его на центр, а затем продолжается влево или вправо и разделить эту половину снова и так далее. Если вы думаете об этом: каждая запись массива суффиксов происходит как центральная точка ровно одного возможного диапазона во время бинарного поиска. Таким образом, существует ровно N различных диапазонов (L...M...R), которые могут играть роль во время бинарного поиска, и достаточно предварительно вычислить lcp(L,M) и lcp(M,R) для этих N возможных диапазоны. Таким образом, это 2*N различных предварительно вычисленных значений, следовательно, LCP-LR имеет размер O(N).

Кроме того, существует простой рекурсивный алгоритм для вычисления 2*N значений LCP-LR за O(N) времени из стандартного массива LCP - я бы предложил опубликовать отдельный вопрос, если вам нужно подробное описание этого.

Подводить итоги:

  • Можно вычислить LCP-LR за время O(N) и пространство O(2*N)=O(N) из LCP
  • Использование LCP-LR во время двоичного поиска помогает ускорить процедуру поиска от O(M*log N) до O(M+log N)
  • Как вы предложили, вы можете использовать два двоичных поиска, чтобы определить левый и правый конец диапазона совпадений для P, а длина диапазона совпадений соответствует числу вхождений для P.
Источник

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

Источник
Другие вопросы по тегам