Статьи

Алгоритм недели: поиск строки Морриса-Пратта

Сентябрь 8, 2017

Мы видели , что ни перебор строки поиска , ни строка поиска Рабина-Карпа эффективны. Однако для того, чтобы улучшить какой-либо алгоритм, сначала нам нужно понять его принципы в деталях. Мы уже знаем, что сопоставление строк методом грубой силы идет медленно, и мы пытались как-то улучшить его, используя хэш-функцию в алгоритме Рабина-Карпа. Проблема в том, что Рабин-Карп имеет ту же сложность, что и сопоставление грубой силы, а именно O (mn).

Очевидно, что нам нужен другой подход, но чтобы прийти к другому подходу, давайте посмотрим, что не так с поиском грубой силы. При более внимательном рассмотрении его принципов мы можем ответить на вопрос.

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

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

Это совершенно бесполезно, потому что мы уже знаем, что шаблон начинается с буквы «а», и ни одна такая буква не оказывается между позициями 1 и 3. Итак, как мы можем улучшить эту избыточность?

обзор

Ответ на этот вопрос пришел к Джеймсу Моррису и Вону Пратту в 1977 году, когда они описали свой алгоритм, который, пропуская множество бесполезных сравнений, более эффективен, чем сопоставление строк методом грубой силы. Давайте посмотрим на это подробно. Единственное, что нужно — это использовать информацию, собранную во время сравнения шаблона и возможного соответствия, как на рисунке ниже.

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

Генерация таблицы следующих позиций

Это сложная часть Morris-Pratt, и именно поэтому этот алгоритм преодолевает недостатки поиска строк методом перебора. Давайте посмотрим несколько фотографий.

Тем не менее, в случае повторяющегося символа в шаблоне, если у нас есть несоответствие после этого символа, возможное совпадение должно начинаться с этого повторяющегося символа, как на рисунке ниже.

Наконец, если в тексте более одного повторяющегося символа, в следующей таблице будет показана их позиция.

После того, как у нас есть эта таблица возможных «следующих» позиций, мы можем начать исследовать текст для нашего шаблона.

Реализация

Осуществить Моррис-Пратт не сложно. Сначала мы должны предварительно обработать шаблон, а затем выполнить поиск. Следующий код PHP показывает, как это сделать.

/**
 * Pattern
 * 
 * @var string
 */
$pattern = 'mollis';
 
/**
 * Text to search
 * 
 * @var string
 */
$text = 'Lorem ipsum dolor sit amet, consectetur adipiscing elit. Quisque eleifend nisi viverra ipsum elementum porttitor quis at justo. Aliquam ligula felis, dignissim sit amet lobortis eget, lacinia ac augue. Quisque nec est elit, nec ultricies magna. Ut mi libero, dictum sit amet mollis non, aliquam et augue';
 
/**
 * Preprocess the pattern and return the "next" table
 * 
 * @param string $pattern
 */
function preprocessMorrisPratt($pattern, &$nextTable)
{
	$i = 0;
	$j = $nextTable[0] = -1;
	$len = strlen($pattern);
 
	while ($i < $len) {
		while ($j > -1 && $pattern[$i] != $pattern[$j]) {
			$j = $nextTable[$j];
		}
 
		$nextTable[++$i] = ++$j;
	}
}
 
/**
 * Performs a string search with the Morris-Pratt algorithm
 * 
 * @param string $text
 * @param string $pattern
 */
function MorrisPratt($text, $pattern)
{
	// get the text and pattern lengths
	$n = strlen($text);
	$m = strlen($pattern);
	$nextTable = array();
 
	// calculate the next table
	preprocessMorrisPratt($pattern, $nextTable);
 
	$i = $j = 0;
	while ($j < $n) {
		while ($i > -1 && $pattern[$i] != $text[$j]) {
			$i = $nextTable[$i];
		}
		$i++;
		$j++;
		if ($i >= $m) {
			return $j - $i;
		}
	}
	return -1;
}
 
// 275
echo MorrisPratt($text, $pattern);

сложность

Этот алгоритм требует некоторого времени и пространства для предварительной обработки. Таким образом, предварительная обработка шаблона может быть выполнена в O (m), где m — длина шаблона, в то время как самому поиску необходим O (m + n). Хорошей новостью является то, что вы можете выполнить предварительную обработку только один раз, а затем выполнять поиск столько раз, сколько пожелаете!

Следующая диаграмма показывает сложность O (n + m) по сравнению с O (nm) для 5-буквенных шаблонов.

заявка

Почему это круто

  1. Его сложность поиска составляет O (m + n), которая быстрее, чем грубая сила и Рабин-Карп
  2. Это довольно легко реализовать

Почему это не круто

  1. Требуется дополнительное пространство и время — O (м) для предварительной обработки
  2. Это может быть немного оптимизировано (Кнут-Моррис-Пратт)

Заключительные слова

Очевидно, что этот алгоритм весьма полезен, потому что он очень элегантно улучшает сопоставление грубой силы. С другой стороны, вы должны знать, что существуют более быстрые алгоритмы поиска строк, такие как алгоритм Бойера-Мура. Однако алгоритм Морриса-Пратта может быть весьма полезным во многих случаях, поэтому понимание его принципов может быть очень удобным.

 

38
Share: