Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Эвристика безопасного суффикса

Читайте также:
  1. Гласные в суффиксах наречий и предлогов
  2. Полнозначные слова можно определить по суффиксамипрефиксам

Рассмотрим несколько примеров.

Пример 1.S=”abababbaab”, W=”abbaab”.

Сначала сравниваем суффикс S6 и W. Как уже отмечалось, сравнение производим справа налево. Выясняется, что максимальный совпадающий суффикс S6 и W”ab” состоит из двух символов. Ближайшее справа вхождение подстроки ”ab” в строку W начинается с позиции 0, поэтому далее можно сравнивать с W уже S6+strlen(W)-strlen(”ab”)+0=S10, т.к. при таком сдвиге впервые та же самая подстрока ”ab” строки S совпадет с соответствующей подстрокой W.

Иными словами, в этом примере мы искали максимальное i<6, такое что ”ab” являлась суффиксом Wi. Следующий претендент на сравнение вычислялся по формуле S6+strlen(W)-i.

 

Пример 2.S=”abababbaab”, W=”bbbaab”.

Сначала, как и в предыдущем примере, сравниваем суффикс S6 и W. Как уже отмечалось, сравнение производим справа налево. Выясняется, что максимальный совпадающий суффикс S6 и W”ab” состоит из двух символов. Подстрока ”ab” больше в строку W не входит. Однако максимальное начало строки W, совпадающее с соответствующим суффиксом ”ab”, имеет длину 1,поэтому далее можно сравнивать с W уже S6+strlen(W)-strlen(”ab”)+1=S11. Действительно, при таком сдвиге впервые часть той же самой подстрока ”ab” строки S (имеется в виду подстрока ”b”) совпадет с соответствующей подстрокой W.

Иными словами, в этом примере мы искали максимальное i£2, такое что Wi являлась бы суффиксом ”ab”. Следующий претендент на сравнение вычислялся по формуле S6+strlen(W)-i (сравнить с предыдущим примером).

 

 

Введем обозначение. Будем говорить, что строки A и B сравнимы: A ~B, если A является суффиксом B или B является суффиксом A.

Обобщая приведенные примеры, мы можем сказать, что мы искали максимальное i<strlen(W), такое что Wi~”ab”.

Введем функцию g, такую что g(l) равна максимальному i<strlen(W), такому, что Wi сравнима с суффиксом W длины l. Если такого не нашлось, то g(l)=0.

Пусть сравнивается суффикс Sk и W. Пусть C - максимальный по длине общий суффикс Sk и W. Следующим претендентом на сравнение будет

Sk+ strlen(W) - g(strlen(C)).

 

Осталось выяснить – каким образом задать функцию g(l).

По определению g(l)=Max{i<strlen(W): Wi~Suff(W,l)}, где Suff(W,l) – суффикс W длины l. То же самое можно переписать иначе:

g(l) = Max{ Max{i<strlen(W): Wi– суффиксSuff(W,l)},

Max{i<strlen(W): Suff(W,l) – суффикс Wi} }

 

Выше мы ввели функцию p(i), равную максимальной длине суффикса строки Wi, являющегося префиксом W. По определению имеем, что Wp(strlen(W)) является суффиксом W, поэтому Wp(strlen(W)) ~ Suff(W,l). Из последнего вытекает, что

g(l) ³ p(strlen(W))

Т.о. получаем

g(l) = Max{ Max{i<strlen(W): Wi– суффиксSuff(W,l)},

Max{i<strlen(W): Suff(W,l) – суффикс Wi} }

 

Более того, Max{i<strlen(W): Wi– суффиксSuff(W,l)} не может превзойти Wp(strlen(W)), т.к. если бы это произошло, то мы получили бы суффикс Suff(W,l) (а следовательно и суффикс W), являющийся префиксом W, длиной больше максимально возможной длины суффикса W, являющегося префиксом W. Т.о. получаем

g(l) = Max{ p(strlen(W)), Max{ p(strlen(W))£i<strlen(W): Suff(W,l) – суффикс Wi} }

Легко увидеть, что поиск

w(l)=Max{ p(strlen(W))£i<strlen(W): Suff(W,l) – суффикс Wi}

сводится к поиску самого правого участка строки W, совпадающего с Suff(W,l) (естественно, рассматриваются участки левее самого Suff(W,l)).

Пример:

l=2; W=” abac ab ac ab”;// выделен Suff(W,l) и его правое вхождение в W

 

Отметим, что такого участка может не существовать. Если рассмотреть строку W’, представляющую собой перевернутую строку W, то задачу можно свести к поиску самого левого вхождения строки W’l в строку W’ (правее начальной позиции):

w(l)=Max{ p(strlen(W))£i<strlen(W): Suff(W,l) – суффикс Wi} =

=strlen(W) - Min{ i>l: W’l – суффикс Wi}+l

Пример:

l=2; W’=”ba ca ba caba ”;// выделен W’l и его левое вхождение в W

 

Рассмотрим начало строки W’, завершающееся найденным левым вхождением W’l в строку W (в примере это – ”ba ca ba”). Более формально: рассмотрим W’I, где I=argMin{ i>l: W’l – суффикс Wi}.

Легко увидеть: l=p’(I), где p’ – префикс-функция W’. Действительно, если бы нашелся больший суффикс W’I, являющийся одновременно префиксом W’, то, соответственно, нашлось бы и более левое вхождение подстроки W’l в строку W (т.к. начало более длинного суффикса должно совпадать с W’l).

С другой стороны равенство l==p’(I) влечет за собой тот факт, что W’l является суффиксом W’I.

Т.о. имеем

Min{ i>l: W’l – суффикс Wi} = Min{ i>l: l==p’(i)}

Тогда получаем

w(l)= strlen(W) +l - Min{ i>l: l==p’(i)}

 

 

Последнее равенство дает алгоритм вычисления w(t): следует перебрать все значения i в порядке убывания и для каждого из них выполнить присвоение

w[p’(i)]= strlen(W) + p’(i) – i если i>p’(i)

В конце концов, получаем

g[l] = Max{ p(strlen(W)), w[l]}

В двух последних формулах мы реализовали w и g как массивы.

 

В прилагаемой программе реализованы функции создания массивов m, p и g. Реализованы функции поиска, использующие только эвристику стоп-символа, только эвристику безопасного суффикса и, наконец, функция поиска по обоим эвристикам.


Дата добавления: 2015-10-30; просмотров: 118 | Нарушение авторских прав


Читайте в этой же книге: Однопроходное добавление элемента в красно-черное дерево | Удаление элемента из красно-черного дерева | Отступление на тему языка С. Быстрый поиск и сортировка в языке С | Удаление вершины из B-дерева | Метод линейных проб | Доказательство. | Метод цепочек | Хэш-функции на основе деления | CRC-алгоритмы обнаружения ошибок | Алгоритм поиска подстроки, основанный на конечных автоматах |
<== предыдущая страница | следующая страница ==>
Алгоритм поиска подстроки Кнута-Морриса-Пратта (на основе префикс-функции)| The form the schedule of performance and delivery of works

mybiblioteka.su - 2015-2024 год. (0.013 сек.)