предисловие
Когда дело доходит до сопоставления двух строк, мы, естественно, думаем о сопоставлении с двумя слоями циклов.Таким образом, мы можем понять, содержит ли строка другую строку.Этот алгоритм называется алгоритмом BF.
Алгоритм БФ
Алгоритм БФ, то есть алгоритм насилия (Brute). И второй символ второго символа t; если не равен, то второй символ S и T первого символа сравнение продолжается последовательно до тех пор, пока не получен конечный результат матча.
Реализация алгоритма BF
public static int bruteforce(String s,String t){
int length = s.length();//目标字符串的长度
int plength = t.length();//模式串的长度
//循环目标字符串
for(int i=0;i<length-plength;i++){
//循环模式串
int j=0;
while((j < plength) && (s.charAt(i+j) == t.charAt(j))){
j++;
}
if(j == plength){
return i;
}
}
return -1;
}
Алгоритм BF представляет собой алгоритм грубой силы без какой-либо оптимизации, он просто использует двухуровневое сравнение циклов, когда строка относительно большая, эффективность выполнения очень низкая, и он не подходит для сравнения очень больших строк.
В худшем случае алгоритм
сравнения, временная сложность
. Таким образом, если мы используем грубую силу для поиска «n» строк в строке «m» символов, нам нужно попытаться n * m раз.
Хотя поиск методом грубой силы прост в реализации и позволяет найти решение, если оно существует, его стоимость пропорциональна количеству возможных решений. Из-за этого во многих практических задачах стоимость будет меняться в зависимости от размера проблемы. . Поэтому поиск методом грубой силы часто используется, когда размер проблемы ограничен или когда существуют эвристики для конкретной проблемы, которые можно использовать для уменьшения набора возможных решений до управляемого размера. Кроме того, этот метод также используется, когда простота реализации важнее вычислительной эффективности.
Мы видим насилие, хотя нет алгоритма поиска строк с предварительной обработкой, но относительно низкая эффективность, потому что нужно делать много ненужных совпадений, поэтому нам нужен более эффективный алгоритм.
Алгоритм автоматов переменного тока
Алгоритм Ахо-Корасик — это алгоритм поиска строк, изобретенный Альфредом В. Ахо и Маргарет Дж. Корасик для сопоставления подстрок в предварительно построенном дереве Trie в строке входных строк. Разница между ним и обычным сопоставлением строк заключается в том, что оно сопоставляется со всеми строками словаря одновременно. Амортизированный случай алгоритма имеет примерно линейную временную сложность, которая равна длине строки плюс количество всех совпадений.
Пусть m — длина шаблона, n — длина строки для поиска, а k — длина алфавита. Поскольку этот алгоритм должен заранее построить мутированное дерево Trie, ему необходимо
время предварительной обработки. Но временная сложность при фактическом поиске строки составляет
, что значительно сокращает время поиска строки.
Алгоритм в основном основан на построении конечного автомата (аналогично добавлению указателей несоответствия в дерево Trie) для реализации. Эти дополнительные указатели несоответствия допускают откат в случае сбоя поиска строки (например, если слово cat в Trie не соответствует, но в Trie есть другое слово cart, указатель несоответствия будет указывать на префикс ca), превращаясь в другие ветви префикса свободны от повторного сопоставления префикса и повышают эффективность алгоритма.
Когда известен набор строк словаря (например, база данных компьютерных вирусов), автомат может быть рассчитан и сохранен в автономном режиме для последующего использования.В этом случае временная сложность алгоритма является входной строкой.Сумма длины и числа совпадений также широко используется в алгоритмах автоматов переменного тока.
структура
1. Дерево, которое строит Trie на основе слов или контента. Это также называется таблицей перехода.
2. В конце слова будет символ, указывающий на корень Trie-дерева или другие ветки, которые совпадают с ним.Это резервный указатель, который позволяет избежать повторения совпадающего префикса и повышает эффективность алгоритм. Например, буква s в конце слова his на рисунке ниже указывает на букву s в слове she, и вы можете продолжить поиск по исходной основе, чтобы уменьшить количество совпадений префикса. Это также называется таблицей отказов.
найти
Сначала ищите «дочерний узел» текущего узла, если совпадений не найдено, ищите дочерний элемент его суффиксного узла, если все еще нет, то ищите дочерний элемент суффиксного узла соответствующей таблицы отказов суффиксного узла. , и так далее, до корневого узла, если он достигает. Если корневой узел по-прежнему не находит соответствия, он завершается.
Когда алгоритм находит узел, он выводит все элементы словаря, которые заканчиваются в текущей позиции. Шаг вывода состоит в том, чтобы сначала найти суффикс словаря узла, а затем выполнять рекурсивно до тех пор, пока у узла не будет префикса словаря. В то же время, если узел является узлом словаря, выводится сам узел.
выполнить
На GitHub есть реализации с открытым исходным кодом, заинтересованные студенты могут ознакомиться.GitHub.com/Robert-Weak/…
Существует ли алгоритм, который не требует такой большой обработки заранее и быстрее сопоставляется позже?
Ответ — алгоритм KMP.
Алгоритм КМП
Он назван в честь трех изобретателей, буква К в начале — известный ученый Дональд Кнут.
Пример алгоритма КМП Ключом к этому алгоритму является та часть таблицы сопоставления (таблица частичного совпадения, также называемая таблицей PMT), то как эту часть таблицы сопоставить? Смотрим шаблонную строку "abababca" часть таблицы соответствий:
char: | a | b | a | b | a | b | c | a |
index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
value: | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
Соответствующее значение является частью строки шаблона "abababca" таблицы сопоставления.
Чтобы понять таблицы частичного соответствия, нам нужно знать префиксы и суффиксы.
«Префикс» означает все комбинации заголовков строки, кроме последнего символа;
«Суффикс» относится ко всем конечным комбинациям строки, кроме первого символа.
字符串：Knuth
前缀： K, Kn, Knu, Knut
后缀： nuth, uth, th, h
Теперь мы находим таблицу частичного соответствия для шаблона «абабабка» на основе «префикса» и «суффикса».
1. "a" 的前缀和后缀都为空集，没有共有元素，长度为 0；
2. "ab" 的前缀为[a]，后缀为[b]，没有共有元素，长度为 0；
3. "aba" 的前缀为[a, ab]，后缀为[ba, a]，共有元素 "a", 长度为 1；
4. "abab" 的前缀为[a, ab, aba]，后缀为[bab, ab, b]，共有元素 "ab", 长度为 2；
...
7. "abababc" 的前缀为[a, ab, aba, abab, ababa, ababab]，后缀为[bababc, ababc, babc, bc, c]，没有共有元素, 长度为 0；
8. "abababca" 的前缀为[a, ab, aba, abab, ababa, ababab, abababc]，后缀为[bababca, ababca, babca, bca, ca, a]，共有元素 "a", 长度为 1；
Как искать по таблице частичного соответствия?
Когда мы находим частичное совпадение, мы можем использовать значение из таблицы частичного совпадения для пропуска (вместо повторного выполнения ненужных старых сравнений).
移动位数 = 已匹配的字符数 - 对应部分匹配表值
Мы используем строку режима «abababca», чтобы соответствовать строке «BacBababaabCBAB».
bacbababaabcbab
|
abababca
На первом шаге, поскольку наша строка шаблона начинается с «а», а затем повторяется по строке, вторым символом является «а», что означает, что есть совпадение для одного символа. Поскольку следующий символ не совпадает, нам нужно двигаться. Количество сдвинутых битов равно таблице частичного соответствия [количество совпадающих символов - 1], что является значением 0 в следующей таблице в таблице частичного сопоставления, которая равна 0. Поэтому нам нужно пропустить 0 символов и продолжить цикл.
bacbababaabcbab
|||||
abababca
Теперь, когда совпало 5 символов, количество символов, которые нужно пропустить, равно 5 - 3 = 2, которые нужно сдвинуть назад на 2.
// x 表示跳过的字符
bacbababaabcbab
xx|||
abababca
Теперь, когда совпали 3 символа, количество символов, которые необходимо пропустить, равно 3 - 1 = 2, которые необходимо сдвинуть назад на 2 бита.
bacbababaabcbab
xx|
abababca
На данный момент наш образец длиннее, чем остальные символы в тексте, поэтому мы знаем, что совпадения нет.
Суммировать
Алгоритм BF относится к методу взлома методом перебора, он использует перебор для поиска строк, когда строка слишком длинная, скорость поиска очень низкая.
Итак, есть алгоритм автомата AC, который сначала строит структуру, аналогичную Trie-дереву, а затем ищет соответствующую строку по Trie-дереву, его временная сложность почти линейна, но Trie-дерево нужно строить заранее.
Существует ли алгоритм, который не является исчерпывающим и не требует предварительного построения дерева Trie?
Это знаменитый алгоритм KMP, который позволяет избежать повторной проверки ранее совпадающих символов, используя тот факт, что само слово содержит достаточно информации, когда оно не соответствует, чтобы определить, где начнется следующее совпадение, что позволяет избежать повторной проверки ранее совпавших символов, что является нашим частичным совпадением выше таблицы. (таблица ПМТ).
PS:
Чистые горы и чистые воды начинаются с пыли, а знания ценнее усердия.
Следите за общедоступной учетной записью WeChat, чтобы быть в курсе последних статей.
Публичный аккаунт WeChat: "болтать".
Добро пожаловать в чат и поговорим о коде.