1. Введение
В этой статье мы покажем несколько алгоритмов поиска шаблона в большом тексте. Мы опишем каждый алгоритм с предоставленным кодом и простой математической базой.
Обратите внимание, что предоставленные алгоритмы — не лучший способ выполнения полнотекстового поиска в более сложных приложениях. Чтобы правильно выполнять полнотекстовый поиск, мы можем использовать Solr или ElasticSearch .
2. Алгоритмы
Мы начнем с наивного алгоритма поиска текста, который является наиболее интуитивным и помогает обнаруживать другие сложные проблемы, связанные с этой задачей.
2.1. Вспомогательные методы
Прежде чем мы начнем, давайте определим простые методы вычисления простых чисел, которые мы используем в алгоритме Рабина-Карпа:
public static long getBiggerPrime(int m) {
BigInteger prime = BigInteger.probablePrime(getNumberOfBits(m) + 1, new Random());
return prime.longValue();
}
private static int getNumberOfBits(int number) {
return Integer.SIZE - Integer.numberOfLeadingZeros(number);
}
2.2. Простой текстовый поиск
Название этого алгоритма описывает его лучше, чем любое другое объяснение. Это самое естественное решение:
public static int simpleTextSearch(char[] pattern, char[] text) {
int patternSize = pattern.length;
int textSize = text.length;
int i = 0;
while ((i + patternSize) <= textSize) {
int j = 0;
while (text[i + j] == pattern[j]) {
j += 1;
if (j >= patternSize)
return i;
}
i += 1;
}
return -1;
}
Идея этого алгоритма проста: перебрать текст и, если есть совпадение для первой буквы шаблона, проверить, все ли буквы шаблона совпадают с текстом.
Если m — количество букв в шаблоне, а n — количество букв в тексте, временная сложность этих алгоритмов равна O(m(nm + 1)) .
Наихудший сценарий возникает в случае, когда String имеет много частичных вхождений:
Text: baeldunbaeldunbaeldunbaeldun
Pattern: foreach
2.3. Алгоритм Рабина Карпа
Как упоминалось выше, алгоритм простого текстового поиска очень неэффективен при длинных шаблонах и при наличии большого количества повторяющихся элементов шаблона.
Идея алгоритма Рабина Карпа состоит в том, чтобы использовать хеширование для поиска шаблона в тексте. В начале алгоритма нам нужно вычислить хэш шаблона, который позже используется в алгоритме. Этот процесс называется вычислением отпечатков пальцев, и мы можем найти подробное объяснение здесь .
Важной особенностью этапа предварительной обработки является то, что его временная сложность составляет O(m) , а итерация по тексту займет O(n) , что дает временную сложность всего алгоритма O(m+n) .
Код алгоритма:
public static int RabinKarpMethod(char[] pattern, char[] text) {
int patternSize = pattern.length;
int textSize = text.length;
long prime = getBiggerPrime(patternSize);
long r = 1;
for (int i = 0; i < patternSize - 1; i++) {
r *= 2;
r = r % prime;
}
long[] t = new long[textSize];
t[0] = 0;
long pfinger = 0;
for (int j = 0; j < patternSize; j++) {
t[0] = (2 * t[0] + text[j]) % prime;
pfinger = (2 * pfinger + pattern[j]) % prime;
}
int i = 0;
boolean passed = false;
int diff = textSize - patternSize;
for (i = 0; i <= diff; i++) {
if (t[i] == pfinger) {
passed = true;
for (int k = 0; k < patternSize; k++) {
if (text[i + k] != pattern[k]) {
passed = false;
break;
}
}
if (passed) {
return i;
}
}
if (i < diff) {
long value = 2 * (t[i] - r * text[i]) + text[i + patternSize];
t[i + 1] = ((value % prime) + prime) % prime;
}
}
return -1;
}
В худшем случае временная сложность этого алгоритма составляет O(m(n-m+1)) . Однако в среднем этот алгоритм имеет временную сложность O(n+m) .
Кроме того, существует версия этого алгоритма Монте-Карло, которая быстрее, но может привести к неправильным совпадениям (ложным срабатываниям).
2.4. Алгоритм Кнута-Морриса-Пратта
В алгоритме простого текстового поиска мы видели, как алгоритм может работать медленно, если есть много частей текста, соответствующих шаблону.
Идея алгоритма Кнута-Морриса-Пратта заключается в вычислении таблицы сдвигов, которая предоставляет нам информацию о том, где мы должны искать наши кандидаты в шаблоны.
Java-реализация алгоритма KMP:
public static int KnuthMorrisPrattSearch(char[] pattern, char[] text) {
int patternSize = pattern.length;
int textSize = text.length;
int i = 0, j = 0;
int[] shift = KnuthMorrisPrattShift(pattern);
while ((i + patternSize) <= textSize) {
while (text[i + j] == pattern[j]) {
j += 1;
if (j >= patternSize)
return i;
}
if (j > 0) {
i += shift[j - 1];
j = Math.max(j - shift[j - 1], 0);
} else {
i++;
j = 0;
}
}
return -1;
}
А вот как мы рассчитываем таблицу смен:
public static int[] KnuthMorrisPrattShift(char[] pattern) {
int patternSize = pattern.length;
int[] shift = new int[patternSize];
shift[0] = 1;
int i = 1, j = 0;
while ((i + j) < patternSize) {
if (pattern[i + j] == pattern[j]) {
shift[i + j] = i;
j++;
} else {
if (j == 0)
shift[i] = i + 1;
if (j > 0) {
i = i + shift[j - 1];
j = Math.max(j - shift[j - 1], 0);
} else {
i = i + 1;
j = 0;
}
}
}
return shift;
}
Временная сложность этого алгоритма также O(m+n) .
2.5. Простой алгоритм Бойера-Мура
Двум ученым, Бойеру и Муру, пришла в голову другая идея. Почему бы не сравнить шаблон с текстом справа налево, а не слева направо, сохраняя при этом направление смещения:
public static int BoyerMooreHorspoolSimpleSearch(char[] pattern, char[] text) {
int patternSize = pattern.length;
int textSize = text.length;
int i = 0, j = 0;
while ((i + patternSize) <= textSize) {
j = patternSize - 1;
while (text[i + j] == pattern[j]) {
j--;
if (j < 0)
return i;
}
i++;
}
return -1;
}
Как и ожидалось, это будет выполняться за время O(m * n) . Но этот алгоритм привел к реализации эвристики вхождения и совпадения, что значительно ускорило алгоритм. Мы можем найти больше здесь .
2.6. Алгоритм Бойера-Мура-Хорспула
Существует много вариантов эвристической реализации алгоритма Бойера-Мура, и самый простой из них — вариант Хорспула.
Эта версия алгоритма называется Бойера-Мура-Хорспула, и эта вариация решает проблему отрицательных сдвигов (мы можем прочитать о проблеме отрицательных сдвигов в описании алгоритма Бойера-Мура).
Как и в алгоритме Бойера-Мура, временная сложность сценария в наихудшем случае составляет O (m * n) , а средняя сложность — O (n). Использование пространства не зависит от размера шаблона, а только от размера алфавита, который равен 256, поскольку это максимальное значение символа ASCII в английском алфавите:
public static int BoyerMooreHorspoolSearch(char[] pattern, char[] text) {
int shift[] = new int[256];
for (int k = 0; k < 256; k++) {
shift[k] = pattern.length;
}
for (int k = 0; k < pattern.length - 1; k++){
shift[pattern[k]] = pattern.length - 1 - k;
}
int i = 0, j = 0;
while ((i + pattern.length) <= text.length) {
j = pattern.length - 1;
while (text[i + j] == pattern[j]) {
j -= 1;
if (j < 0)
return i;
}
i = i + shift[text[i + pattern.length - 1]];
}
return -1;
}
4. Вывод
В этой статье мы представили несколько алгоритмов текстового поиска. Поскольку для некоторых алгоритмов требуется более сильная математическая подготовка, мы попытались представить основную идею каждого алгоритма и изложить ее в простой форме.
И, как всегда, исходный код можно найти на GitHub .