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

Алгоритм поиска подстроки, основанный на конечных автоматах

Читайте также:
  1. CRC-алгоритмы обнаружения ошибок
  2. VII. Алгоритмы продаж
  3. Алгоритм 4. Транспонування бази даних
  4. Алгоритм 5. Пошук автофильтром
  5. Алгоритм Apriori
  6. Алгоритм De Boor
  7. Алгоритм De Boor для Кривых NURBS

С этого момента мы будем говорить о строках в понимании языка С.

Итак, в строке S, strlen(S)==N, следует найти все вхождения подстроки W, strlen(W)==M, т.е. следует найти все такие 0£ i £N-M, что strncmp(S+i,W,M)==0.

 

Будем говорить, что строка b является префиксом строки a, если

strlen(b)<=strlen(a) && strncmp(b,a,strlen(b))==0.

 

Будем говорить, что строка b является суффиксом строки a, если

strlen(b)<=strlen(a) && strcmp(b,a+strlen(a)-strlen(b))==0.

 

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

strncmp(S+strlen(S)-l,W,l)==0

Например, для S=(ababa), W=(abac): h(S,W)= 3.

Если, при этом, выполнится условие

h(S,W)==strlen(W)

то это будет обозначать, что найдено вхождение W в строку S.

Допустим, что в некоторый момент мы знаем значение функции h(S,W). Пусть строка S2 получена с помощью добавления очередного символа a из входного потока данных в конец строки S.

Легко увидеть, что h(S2,W) <= h(S,W)+1 (иначе, мы сразу получим, что строка S имеет суффикс длины большей h(S,W), совпадающий с префиксом W), но зная значение h(S,W) мы сразу получаем значения h(S,W) последних символов S (это – первые h(S,W) символов строки W). Т.о. значение функции h(S2,W) может быть вычислено исходя из знания значения h(S,W) и a.

Итак, мы строим конечный автомат, в котором состояние системы задается величиной H= h(S,W). В качестве входного алфавита будут выступать символы, текста. Принимающим будет такое состояние H, когда H==strlen(W).Начальное состояние H0=0. О вычислении функции перехода поговорим позднее.

Итак, легко увидеть, что, если не задумываться о вычислении функции перехода, то основная часть алгоритма поиска выполняется за время T=Q(N), где N – длина входной последовательности текста.

Функцию перехода предлагается вычислять в лоб. Т.е. для случая, когда ищется строка W и когда алфавит состоит из 256 символов, строится таблица tab из 256 столбцов и strlen(W) строк. j- ый столбец будет соответствовать появлению символа с кодом j, а i- ая строка будет соответствовать состоянию автомата i. Для получения значения tab[i][j] следует рассмотреть строку, состоящую из i первых символов строка W с добавленным в конец символом с кодом j. Длина максимального суффикса полученной строки, совпадающего с префиксом W, будет искомым значением tab[i][j].

Для получения значения tab[i][j] нужно не более i раз сравнить подстроку W с подстрокой полученной строки. Итого, tab[i][j] вычисляется за время O(M2). Все значения tab[i][j] вычисляются за время O(256M3), где 256 – количество символов входного алфавита, M – длина искомого слова. Легко увидеть, что для данного алгоритма данная оценка точна. Т.о. мы доказали следующую теорему

 

Теорема. Поиск подстроки длины M, состоящей из символов алфавита из K символов, в тексте длины N с помощью предложенного алгоритма, использующего конечные автоматы, требует основного времени T1=Q(N). На подготовку, зависящую только от искомой подстроки и размера входного алфавита, требуется время T0=Q(K M3).

 

 


Лекция 15

 


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


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

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