Статьи

Алгоритм недели: поиск строки Рабина-Карпа

Декабрь 9, 2018

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

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

Этот алгоритм медленный по двум причинам. Во-первых, мы должны проверить каждый символ из текста. С другой стороны, даже если мы находим соответствие между текстовым символом и первым символом шаблона, мы продолжаем проверять шаг за шагом (символ за символом) каждый отдельный символ шаблона, чтобы найти его в тексте. Так есть ли другой подход, чтобы найти, содержит ли текст образец?

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

Этот подход известен как алгоритм Рабина-Карпа.

обзор

Майкл О. Рабин и Ричард М. Карп выступили с идеей хеширования шаблона и проверки его по хешированной подстроке из текста в 1987 году. В целом идея кажется довольно простой, единственное, что нам нужно хеш-функция, которая дает разные хеши для разных подстрок. Например, указанная хеш-функция может использовать коды ASCII для каждого символа, но мы должны быть осторожны для многоязычной поддержки.

Хеш-функция может варьироваться в зависимости от многих вещей, поэтому она может состоять из преобразования ASCII-символов в числа, но может быть и чем-то еще. Единственное, что нам нужно, — это преобразовать строку (шаблон) в некоторый хеш, который быстрее сравнивать. Допустим, у нас есть строка «hello world», и давайте предположим, что ее хеш имеет значение hash («hello world») = 12345. Поэтому, если hash (‘he’) = 1, мы можем сказать, что шаблон «he» содержится в текст «Привет, мир». Таким образом, на каждом шаге мы берем из текста подстроку длиной m, где m — длина шаблона. Таким образом, мы хэшируем эту подстроку и можем напрямую сравнивать ее с шаблоном хеширования, как на картинке выше.

Реализация

До сих пор мы видели некоторые диаграммы, объясняющие алгоритм Рабина-Карпа, но давайте посмотрим на его реализацию здесь, в этом очень простом примере, где используется простая хеш-таблица для преобразования символов в целые числа. Код PHP и используется только для иллюстрации принципов этого алгоритма.

function hash_string($str, $len)
{
	$hash = '';
 
	$hash_table = array(
		'h' => 1,
		'e' => 2,
		'l' => 3,
		'o' => 4,
		'w' => 5,
		'r' => 6,
		'd' => 7,
	);
 
	for ($i = 0; $i < $len; $i++) {
		$hash .= $hash_table[$str{$i}];
	}
 
	return (int)$hash;
}
 
function rabin_karp($text, $pattern)
{
	$n = strlen($text);
	$m = strlen($pattern);
 
	$text_hash = hash_string(substr($text, 0, $m), $m);
	$pattern_hash = hash_string($pattern, $m);
 
	for ($i = 0; $i < $n-$m+1; $i++) {
		if ($text_hash == $pattern_hash) {
			return $i;
		}
 
		$text_hash = hash_string(substr($text, $i, $m), $m);
	}
 
	return -1;
}
 
// 2
echo rabin_karp('hello world', 'ello');

Многократное совпадение паттернов

Приятно сказать, что алгоритм Рабина-Карпа отлично подходит для сопоставления с несколькими образцами. Действительно, его природа должна поддерживать такую ​​функциональность, что является его преимуществом по сравнению с другими алгоритмами поиска строк.

сложность

Алгоритм Рабина-Карпа имеет сложность O (nm), где n , конечно, является длиной текста, а m — длиной шаблона. Так, где это по сравнению с грубой силой соответствия? Что ж, сложность подбора грубой силы равна O (нм), так что, похоже, выигрыш в производительности невелик. Однако считается, что сложность Рабина-Карпа на практике составляет O (n + m), и это делает его немного быстрее, как показано на графике ниже.

Обратите внимание, что алгоритм Рабина-Карпа также требует времени предварительной обработки O (m).

заявка

Как мы увидели, Рабин-Карп не намного быстрее, чем подбор методом грубой силы. Так, где мы должны использовать это?

3 причины, почему Рабин-Карп это круто

1. Хороший для плагиата, потому что это может иметь дело с множественным соответствием образца!

2. Not faster than brute force matching in theory, but in practice its complexity is O(n+m)!

3. With a good hashing function it can be quite effective and it’s easy to implement!

2 Reasons Why Rabin-Karp is Not Cool

1. There are lots of string matching algorithms that are faster than O(n+m)

2. It’s practically as slow as brute force matching and it requires additional space

Final Words

Rabin-Karp is a great algorithm for one simple reason – it can be used to match against multiple patterns. This makes it perfect to detect plagiarism even for larger phrases.

70
Share: