Главная » Java, Структуры данных и алгоритмы » Алгоритмы шаблонного сопоставления – Силовое решение

0

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

Силовое шаблонное сопоставление

При использовании этой методики для проектирования алгоритма силового шаблонного сопоставления (brute-force pattern matching) остановимся на наиболее очевидном в такой ситуации варианте алгоритма, который может прийти в голову — просто проверяем всевозможные положения Р относительно Т. Этот алгоритм достаточно прост, смотрите фрагмент кода 11.1.

Алгоритм BruteForceMatchCr,/3):

Input: строка Г (текст) из п символов и Р (шаблон) из т символов.

Output: индекс начала подстроки, соответствующей Р, в строке Гили признак того, что Р не является подстрокой Т.

for / <- 0 to п — т { для каждого подходящего индекса в Т } do

У <- О

while (j < m and T[i + j] = P[j]) do

У <- У + 1

if j = m then return /

return "There is no substring of T matching P" Фрагмент кода 11Л. Алгоритм силового шаблонного сопоставления

Упростить алгоритм силового шаблонного сопоставления просто невозможно. Он состоит из двух вложенных циклов. Внешний цикл проходит все возможные индексы начала шаблона в тексте, внутренний цикл — все символы шаблона, сравнивая их с потенциальными символами текста. Таким образом, правильность алгоритма силового шаблонного сопоставления вытекает из такого тщательного поискового подхода.

Производительность

Нельзя сказать, однако, что время выполнения силового шаблонного сопоставления в наихудших случаях будет очень хорошим, так как для каждого символа Гследует выполнить до т сравнений, чтобы выяснить, что Р не соответствует Т для этого индекса. Из фрагмента кода 11.1 видно, что внешний цикл максимально выполняется за п — m + 1 времени, а внутренний цикл — за m времени. Следовательно, время выполнения метода силового согласования составит 0((п — m + 1) m), или просто О(пт)[22]. Таким образом, в наихудшем случае, когда пит приблизительно равны, этот алгоритм имеет квадратичное время выполнения.

Пример 11.3. Допустим, имеется текстовая строка Т = «abacaabaccabacabaabb»

и шаблонная строка

Р = «abacab»

На рис. 11.1 показано выполнение алгоритма силового шаблонного сопоставления Т и Р.

Л|с. i/./. Пример выполнения алгоритма силового шаблонного согласования. Алгоритм выполняет 27 сравнений символов, отмеченных номерами

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии