Поиск в строках, массивах, последовательностях:
Нечеткий поиск.

pm[i, c+1] = pm[i, c+2] = … = pm[i, 2k+1] = m+1

Таким образом, для merge интерес представляет строка i - r таблицы несовпадений, причем используются значения pm[i-r, 1…t], где t – самое правое несовпадение в pm[i-r, 1…2k+1], такое, что pm[i-r, t] < j-i+1, так как требуются только несовпадения в подстроке x(1, j-i).

Чтобы понять, как упомянутая информация может использоваться в процедуре merge, рассмотрим в тексте позицию p, находящуюся в соответствующем диапазоне, i+1 < p < j. Позиция p может удовлетворять или не удовлетворять любому из приведенных ниже условий.

A: когда символы x₁ и y_r+1 совмещены, позиция p в тексте соответствует предварительно выявленному несовпадению между образцом и текстом, то есть y_p =/=x_p-r, и это несовпадение номер v, где q < v < k+1, то есть p - r = tm[r, v].

B: для двух копий образца, со сдвигом относительно друг друга i - r, совмещенных с текстом так, что их начальные символы лежат, соответственно, над y_r+1 и y_i+1, позиция p соответствует несовпадению между двумя шаблонами, то есть x_p-r =/=x_p-i. Это u-е несовпадение при этом сдвиге, где 1 < u < t, то есть p-i = pm[i-r, u].

Вспомним, что нас интересует, совпадает ли символ текста в позиции p с соответствующими символом образца, когда x₁ совмещен с y_i+1, то есть верно ли, что y_p = x_p-i. Рассмотрим этот вопрос при разных комбинациях указанных выше условий.

Случай 1: не выполняется ни условие A, ни условие B. То есть, y_p = x_p-r и x_p-r = x_p-i, откуда y_p = x_p-i. Нет необходимости сравнивать символ текста с символом шаблона, так как ясно, что в этой позиции они совпадают.

Случай 2: выполняется только одно из условий, то есть либо условие A, либо условие B, но не оба сразу. В любом случае y_p =/=x_p-i. Если лишь условие A истинно, то y_p =/=x_p-r и x_p-r = x_p-i, откуда y_p =/=x_p-i. С другой стороны, если выполнено только условие B, то y_p = x_p-r и x_p-r =/=x_p-i, и опять, y_p =/=x_p-i. Как и в предыдущем случае, нет необходимости сравнивать символ текста с символом шаблона, так как известно, что они не совпадают.

Случай 3: выполняются оба условия – и условие A, и условие B. В этом случае мы ничего не можем сказать о том, совпадают ли символы y_p и x_p-i, поэтому их надо сравнить.

В случае 2, или если в случае 3 выявлено несовпадение символов, необходимо увеличить количество несовпадений символов b на единицу и обновить tm[i, b] в процедуре merge.

Теперь опишем процедуру merge, представленную на рисунке 27. Как упоминалось ранее, соответствующими значениями таблицы для merge являются tm[i-r, 1…t] и tm[r, q…k+1]. Переменные u и v в начале устанавливаются равными индексам первых элементов этих двух векторов, соответственно, и последовательно увеличиваются соответственно векторным компонентам.

Условия окончания работы процедуры следующие. Во первых, если b = k+1, то для случая, когда шаблон расположен относительно текста так, что x₁ совмещен с y_i+1, обнаружено k+1 несовпадение, поэтому из процедуры можно выйти. Во вторых, вспомним, что самая правая из интересующих нас позиций в merge, а именно, j, равна r+tm[r, k+1], если v = k+2, поэтому tm[r, k+1] будет уже использовано для предыдущего значения v, а именно, v = k+1, и поэтому позиция j должна быть пропущена. Следовательно, в этом случае также можно выйти из процедуры. Наконец, процедуру можно прервать, если i+pm[i-r, u] > j и tm[r, v] = m+1. Если выполняется вторая часть этого условия, то r+tm[r, v] равняется j, и соответствует суммам для последующих значений v вплоть до k+1. В этом случае процедура может быть прервана, если выполняется также первая часть приведенного условия, так как она указывает, что позиция текста j фактически пропущена.

Остается показать, что число позиций несовпадений в таблице несовпадений шаблона достаточно для того, чтобы merge нашла все, или, если их больше k+1, первые k+1 несовпадений для y(i+1, j). Это можно показать следующим образом. Условие A выполняется не больше чем для k+1 позиции текста в диапазоне [i+1, j]. Условие B выполняется для некоторого неизвестного числа позиций в этом же интервале. Строка i-r в таблице несовпадений шаблона, tm[i-r, 1 ... 2k+1], содержит не больше чем 2k+1 позиций несовпадений между двумя копиями шаблона, с соответствующим сдвигом i-r. Если pm[i-r, 2k+1] > j - i, то таблица содержит все позиции несовпадения шаблона самим с собой, у которых условие B выполняется для позиций текста в интервале [i+1, j]. С другой стороны, если pm[i-r, 2k+1] < j-i, то таблица может дать 2k+1 позиций текста в диапазоне [i+1, j-1], для которых выполняется условие B. Поскольку j = r+tm[r, k+1], в диапазоне [i+1, j-1] имеется до k позиций текста, для которых выполняется условие A. Таким образом, в худшем случае может быть k позиций, для которых имеет место случай 3, и которые требуется сравнить напрямую. Остается по крайней мере k+1 позиций, удовлетворяющих условию B, но не условию A (случай 2), что является достаточным, чтобы заключить, что для данного положения шаблона относительно текста имеется не меньше k+1 несовпадений между текстом и шаблоном.

Теперь исследуем затраты времени на анализ текста. Если исключить вызовы процедур merge и extend, каждая из n-m+1 итераций цикла анализа текста выполняется за фиксированное время, что дает в общей сложности время O(n). Общее число операций, выполняемых процедурой extend во время вызовов равно O(n), так как она проверяет каждый символ текста не больше одного раза. Процедура merge при каждом вызове обрабатывает вектора pm[i-r, 1 ... 2k+1] и tm[r, 1…k+1], которые в сумме имеют 3k+2 элементов. Время работы merge можно рассчитать, соотнеся операции с фиксированным временем с каждым из этих входов, что дает время счета для каждого вызова, равное O(k). Таким образом, можно видеть, что общее время анализа текста составляет O(nk).

merge(i, r, j, b)

   u = 1

   v = q

   while (b < K + 1) AND (V < K + 2)

                     AND (I + PM[I - R, U] < j or tm[r, v] =/=m + 1)

      if i + pm[i - r, u] > r + tm[r, v]

         - Случай 2, условие A

         b = b + 1

         tm[i, b] = tm[r, v] - (i - r)

         v = v + 1

      else if i + pm[i - r, u] < R + TM[R, V]

         - СЛУЧАЙ 2, УСЛОВИЕ B

         B = B + 1

         TM[I, B] = PM[I - R, U]

         U = U + 1

      else

         - I + PM[I - R, U] = R + TM[R, V]

         - СЛУЧАЙ 3

         IF Xpm[i-r,u] =/=yi+pm[i-r,u]

            b = b + 1

            tm[i, b] = pm[i - r, u]

         u = u +1

         v = v + 1

Рисунок 27: Процедура merge Ландау-Вишкина

- инициализация

 

r = 2l-1

j = 2l-1

- вычисление строк pm в множестве l

for i = 2l-1 to 2l - 1

   b = 0

   if i < J

      merge(I, R, J, B)

      IF 

         r = i

         extend(i, j, b)

Рисунок 28: Предварительная обработка образца Ландау-Вишкина

Теперь осталось только обратиться к вычислению таблицы несовпадений шаблона на стадии предварительных вычислений. Не теряя общности, можно предположить, что m является некоторой степенью 2. В алгоритме предварительной обработки используется разбиение множества {1, 2, ... , m-1} из m-1 строк pm на следующие log₂m подмножеств:

{1}, {2, 3}, {4, 5, 6, 7}, ... , {m/2, ... , m-1}

Алгоритм состоит из log₂m этапов. На этапе s, где 1 < s < log₂m, вычисляются строки pm в множестве s, где множество s – это {2^s-1, ... , 2^s-1}.

Метод, используемый для вычисления этой таблицы, основан на методе, используемом на стадии анализа текста, алгоритм для этапа s приведен на рисунке 28. На стадии s входами для алгоритма анализа образца являются подстроки образца x(1, m-2^s-1) и x(2^s-1+1, m), которые трактуются здесь, соответственно, как образец и текст, и массив pm[1…2^s-1-1, 1…min{2^log(m)-s4k+1, m-2^s-1}], содержащий выходы предыдущих l - 1 стадий. (Число элементов в строках подмассива будет объяснено позже). Выходы стадии s вводятся в. За исключением стадии log₂m, на которой находят до 2k+1 несовпадений, на стадии s для каждой строки pm требуется найти до min{2^log(m)-s2k+1, m-2^s} несовпадений, а не до k+1, как в алгоритме анализа текста.

Используя аргументы, аналогичные применявшимся при проверке корректности процедуры merge, можно показать, что для нахождения требуемого количества несовпадений на стадии s требуется min{2^log(m)-s4k+1, m-2^s} позиций, для которых выполняется условие B, и в особом случае, а именно, на стадии log₂m, требуется 4k + 1 таких позиций.

На каждой стадии s из log₂m стадий анализа шаблона цикл for производит 2^s-1 итераций (2^s-1 < i < 2^s - 1). Если не считать время работы процедур merge и extend, каждая итерация требует фиксированного времени. Для всех итераций на шаге s процедуре extend требуется время O(m). Ранее было показано, что время работы merge пропорционально числу искомых несовпадений. Таким образом, каждый вызов merge занимает время , что равно . Таким образом, общее время для стадии s равно =O(km). Проведя суммирование по всем стадиям, получаем общее время счета . Таким образом, общие затраты времени, включающие предварительную обработку шаблона и анализ текста, равны O(k(n + m log m)).

Вверх по странице, к оглавлению и навигации.