Алгоритм Рабіна — Карпа
Алгоритм Рабіна-Карпа
Загальний Опис
Алгоритм Рабіна-Карпа – це алгоритм пошуку рядка в іншому рядку, що демонструє високу практичну ефективність. Алгоритм заснований на хешуванні та дозволяє швидко знаходити збіги підрядкових у великих текстах.
Основна Ідея
Припустимо, у нас є текст Т довжиною n і рядок-зразок Р довжиною m (m <= n). Алгоритм обчислює хеш-значення обох рядків і порівнює їх. Якщо вони збігаються, алгоритм перевіряє, чи рядки також збігаються посимвольно. Це дозволяє швидко знаходити потенційні збіги без необхідності посимвольно перевіряти весь текст.
Хешування
Хеш-функція – це функція, яка перетворює рядок фіксованої довжини на число. В алгоритмі Рабіна-Карпа зазвичай використовують хеш-функцію, засновану на потентіруванні:
Hash(S) = (S[0]*b^(m-1) + S[1]*b^(m-2) + … + S[m-1]) % q
де:
- S – рядок
- b – константа (зазвичай велике просте число)
- q – просте число більше за m
Пошук Збігів
Для пошуку збігів алгоритм обчислює хеш-значення підрядкових тексту Т довжиною m і порівнює їх з хеш-значенням рядка-зразка Р. Якщо вони збігаються, алгоритм додатково перевіряє збіг рядків посимвольно, щоб підтвердити збіг.
Алгоритм Покроково
- Обчисліть хеш-значення рядка-зразка Р.
- Обчисліть хеш-значення першого підрядкового тексту Т.
- Порівняйте хеш-значення. Якщо вони збігаються, перейдіть до кроку 4.
- Перевірте, чи підрядковий текст збігається з рядком-зразком. Якщо це так, це збіг.
- Обчисліть хеш-значення наступного підрядкового тексту Т.
- Повторіть кроки 3-5, доки не досягнете кінця тексту або не знайдете збіг.
Узагальнення
Алгоритм Рабіна-Карпа також можна узагальнити для вирішення інших пов'язаних задач:
- Пошук анаграм у тексті
- Перевірка чи два рядки є обертаннями одного і того ж рядка
- Пошук найдовшого загального підрядкового рядка
Алгоритм Рабіна-Карпа – це ефективний алгоритм пошуку рядка, який використовує хешування для швидкого знаходження збігів у великих текстах. Він має широке застосування в обробці тексту та інформаційному пошуку.
Часто Задані Питання
- Як вибрати константу b? Зазвичай вибирають велике просте число, близьке до діапазону значень хеш-функції.
- Чому важливо вибирати просте число для q? Це запобігає колізіям в хеш-таблиці.
- Як можна прискорити алгоритм? Можна використовувати методи перегляду таблиць, щоб уникнути переобчислення хеш-значень підрядкових.
- Які обмеження алгоритму Рабіна-Карпа? Він може давати хибні збіги, якщо рядок має багато анаграм.
- Чи існують альтернативні алгоритми пошуку рядка? Так, наприклад, алгоритм Бойєра-Мура та алгоритм Кнута-Морріса-Пратта.
Опубліковано