Выполните поиск по ключевому слову, реализовав алгоритм Рабина-Карпа.

Здравствуйте, в этой статье я расскажу об алгоритме Рабина-Карпа для поиска текста в предложении или сопоставления с образцом. Я буду использовать JavaScript для этого алгоритма. Давайте копаем алгоритм Рабина-Карпа.

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

Хеш-функция

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

Демо

Я буду использовать Visual Studio Code в качестве текстового редактора для демонстрации алгоритма Рабина-Карпа. Я создал два файла, то есть rabin_karp.js и index.js. В файле rabin_karp.js я создам класс RabinKarp с соответствующими методами в файле index.js. Приступим к созданию RabinKarp класса с помощью методов searchText(text, string), areStringEqual(firstString, secondString) и calculateHash(myText, largePrime, randomNumber).

  1. areStringEqual(firstString, secondString): Используется для сравнения двух строк после вычисления хэша. В качестве аргумента он принимает две строки: firstString и secondString. Если обе строки совпадают, возвращается истина, если не ложь.
  2. calculateHash(myText, largePrime, randomNumber): Он используется для вычисления хэша строки, которую мы хотим найти. Он принимает три аргумента: myText, largePrime и randomNumber. Возвращает хеш.
  3. searchText(text, string): это основная функция, которая ищет определенный текст и возвращает позицию в предоставленной строке для поиска.

Начнем с areStringEqual(firstString, secondString).

1. areStringEqual (firstString, secondString)

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

2. calculateHash(myText, largePrime, randomNumber)

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

3. searchText(text, string)

Мы реализовали алгоритм Рабина-Карпа. Давайте создадим отправную точку для алгоритма Рабина-Карпа - файл index.js. В этом файле мы создадим объект RabinKarp и вызовем метод searchText(sentence, textToSearch), который отвечает за поиск нашего текста в данном предложении и вывод позиции строки в консоль.

Это все об алгоритме Рабина-Карпа. Понять этот алгоритм очень просто, не так ли? Если вам понравилась эта статья, пожалуйста, хлопайте в ладоши. Если вам нужны дополнительные объяснения или у вас есть какие-либо вопросы, свяжитесь со мной или оставьте ответы ниже. Также посетите мой средний профиль, чтобы прочитать другие мои статьи в Medium. Я загрузил алгоритм Рабина-Карпа на свой GitHub, вы можете скачать исходный код с моего GitHub. Оставайтесь с нами, ребята. И, хорошего дня и оставайтесь в безопасности.

Всегда помни. Продолжай учиться. Это поможет вам во многих сферах.

Удачного кодирования!