Алгоритм Рабина-Карпа

1.

Алгоритм Рабина-Карпа
ВЫПОЛНИЛА ГУБИНА ЕКАТЕРИНА, МПМ -101

2.

Что такое алгоритм Рабина-Карпа?
• Алгоритм Рабина-Карпа — это алгоритм поиска, который ищет шаблон
подстроки в тексте с использованием хеширования. Преимуществом алгоритма
Рабина-Карпа над другими алгоритмами сопоставления строк является
возможность сопоставления слов с несколькими шаблонами. Одним из
практических применений алгоритма Рабина-Карпа является обнаружение
плагиата.
• Хеш-функция — это функция, которая определяет значение признака конкретной
дроби слога. Он преобразует каждую строку в число, называемое хеш-значением.

3.

Как работает алгоритм?
1.
Вычисляется хеш шаблона строки.
2.
Вычисляется хеш подстроки в тексте
строки, начиная с индекса 0 и до m-1.
3.
Сравнивается хеш подстроки текста с
хешем шаблона.

4.

Полиномиальный хэш
где с — символ в строке, m — длина строки, b — константа.

5.

Пример
2
1
3
1
3
5
5
5
1

6.

Пример
2
1
3
1
3
5
H(135) = 1 * 102 + 3 * 101 + 5 * 100 = 135
5
5
1

7.

Пример
2
1
3
1
3
5
H(135) = 1 * 102 + 3 * 101 + 5 * 100 = 135
H(213) = 2 * 102 + 1 * 101 + 3 * 100 = 213
5
5
1

8.

Пример
2
1
3
1
3
5
5
5
1

9.

Пример
2
1
3
1
3
5
5
H(135) = 1 * 102 + 3 * 101 + 5 * 100 = 135
5
1

10.

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