Введение
Алгоритм поиска строк
В информатике алгоритм Рабина-Карпа (Rabin–Karp algorithm) или алгоритм Карпа-Рабина (Karp–Rabin algorithm) — это алгоритм поиска строк, использующий хеширование для нахождения точного соответствия строки-образца в тексте. Он применяет скользящий хеш для быстрой фильтрации позиций в тексте, которые не могут соответствовать образцу, а затем проверяет соответствие в оставшихся позициях. Обобщения этой идеи могут быть использованы для поиска нескольких соответствий одного образца или для поиска соответствий для нескольких образцов. Для поиска единственного соответствия одного образца ожидаемое время работы алгоритма линейно зависит от суммарной длины образца и текста, хотя в наихудшем случае временная сложность равна произведению этих длин. Для поиска нескольких соответствий ожидаемое время работы линейно зависит от длины входных данных плюс суммарная длина всех соответствий, которая может превышать линейную зависимость. В отличие от этого, алгоритм Ахо-Корасика (Aho–Corasick algorithm) может находить все соответствия нескольких образцов за время и объем памяти, линейно зависящие от длины входных данных и количества соответствий (а не от общей длины соответствий). Практическое применение алгоритма — обнаружение плагиата. При наличии исходного материала алгоритм может быстро искать в документе фрагменты предложений, взятых из исходного материала, игнорируя детали, такие как регистр и пунктуация. Из-за большого количества искомых строк алгоритмы поиска одной строки оказываются непрактичными.
although its worst case time complexity is the product of the two lengths. To find multiple matches, the expected time is linear in the input lengths, plus the combined length of all the matches, which could be greater than linear. In contrast, the Aho–Corasick algorithm can find all matches of multiple patterns in worst case time and space linear in the input length and the number of matches (instead of the total length of the matches). A practical application of the algorithm is detecting plagiarism. Given source material, the algorithm can rapidly search through a paper for instances of sentences from the source material, ignoring details such as case and punctuation. Because of the abundance of the sought strings, single string searching algorithms are impractical.
Обзор
Наивный алгоритм поиска подстроки сравнивает заданный образец со всеми позициями в заданном тексте. Каждое сравнение занимает время, пропорциональное длине образца, а количество позиций пропорционально длине текста. Следовательно, время в наихудшем случае для такого метода пропорционально произведению двух длин. Во многих практических случаях это время можно значительно сократить, прерывая сравнение в каждой позиции, как только обнаружено несовпадение, но эта идея не гарантирует ускорения. Несколько алгоритмов поиска подстроки, включая алгоритм Кнута — Морриса — Пратта и алгоритм поиска подстроки Бойера — Мура, уменьшают время в наихудшем случае для поиска подстроки, извлекая больше информации из каждого несовпадения, что позволяет им пропускать позиции текста, которые гарантированно не соответствуют образцу. Алгоритм Рабина — Карпа вместо этого достигает ускорения, используя хеш-функцию для быстрого выполнения приблизительной проверки для каждой позиции, а затем выполняя точное сравнение только на позициях, прошедших эту приблизительную проверку. Хеш-функция — это функция, которая преобразует каждую строку в числовое значение, называемое ее хеш-значением; например, может быть хеш("hello") = 5. Если две строки равны, их хеш-значения также равны. Для хорошо разработанной хеш-функции обратное верно в приближенном смысле: неравные строки вряд ли будут иметь одинаковые хеш-значения. Алгоритм Рабина — Карпа вычисляет для каждой позиции текста хеш-значение строки, начинающейся в этой позиции и имеющей ту же длину, что и образец. Если это хеш-значение равно хеш-значению образца, он выполняет полное сравнение в этой позиции. Для того чтобы это работало эффективно, хеш-функцию следует выбирать случайным образом из семейства хеш-функций, которые вряд ли будут давать много ложных срабатываний, то есть позиции текста, которые имеют то же хеш-значение, что и образец, но на самом деле не соответствуют ему. Эти позиции вносят вклад во время работы алгоритма без необходимости, не приводя к совпадению. Кроме того, используемая хеш-функция должна быть инкрементной хеш-функцией, значение которой можно быстро обновить при переходе от каждой позиции текста к следующей. Пересчет хеш-функции с нуля для каждой позиции был бы слишком медленным.
and the number of positions is proportional to the length of the text. Therefore, the worst case time for such a method is proportional to the product of the two lengths. In many practical cases, this time can be significantly reduced by cutting short the comparison at each position as soon as a mismatch is found, but this idea cannot guarantee any speedup. Several string matching algorithms, including the Knuth–Morris–Pratt algorithm and the Boyer–Moore string search algorithm, reduce the worst case time for string matching by extracting more information from each mismatch, allowing them to skip over positions of the text that are guaranteed not to match the pattern. The Rabin–Karp algorithm instead achieves its speedup by using a hash function to quickly perform an approximate check for each position, and then only performing an exact comparison at the positions that pass this approximate check. A hash function is a function which converts every string into a numeric value, called its hash value; for example, we might have hash("hello")=5. If two strings are equal, their hash values are also equal. For a well designed hash function, the inverse is true, in an approximate sense: strings that are unequal are very unlikely to have equal hash values. The Rabin–Karp algorithm proceeds by computing, at each position of the text, the hash value of a string starting at that position with the same length as the pattern. If this hash value equals the hash value of the pattern, it performs a full comparison at that position. In order for this to work well, the hash function should be selected randomly from a family of hash functions that are unlikely to produce many false positives, that is, positions of the text which have the same hash value as the pattern but do not actually match the pattern. These positions contribute to the running time of the algorithm unnecessarily, without producing a match. Additionally, the hash function used should be a rolling hash, a hash function whose value can be quickly updated from each position of the text to the next. Recomputing the hash function from scratch at each position would be too slow.