Самый быстрый алгоритм С++ для тестирования строк по списку предопределенных семян (без учета регистра)

Ответ 1

Вы можете использовать алгоритм Aho-Corasick

Он строит trie/automaton, где некоторые вершины, помеченные как терминалы, которые означают, что у строки есть семена.

Он построен в O(sum of dictionary word lengths) и дает ответ в O(test string length)

Преимущества:

• Он работает с несколькими словарями, а время проверки не зависит от количества слов (если мы не рассматриваем случаи, когда оно не подходит для памяти и т.д.)
• Алгоритм не сложно реализовать (по крайней мере, по сравнению с структурами суффиксов)

Вы можете сделать регистр нечувствительным, опустив каждый символ, если ASCII (несимволы ASCII не совпадают)

Ответ 2

Если имеется конечное количество совпадающих строк, это означает, что вы можете построить дерево, которое, прочитав от корня до листьев, аналогичные строки будут занимать аналогичные ветки.

Это также называется trie или Radix Tree.

Например, у нас могут быть строки cat, coach, con, conch, а также dark, dad, dank, do. Их трю может выглядеть так:

Поиск одного из слов в дереве будет искать дерево, начиная с корня. Приведение его к листу соответствует совпадению с семенем. Независимо от того, каждый символ в строке должен соответствовать одному из своих детей. Если это не так, вы можете прекратить поиск (например, вы не будете рассматривать слова, начинающиеся с "g" или любые слова, начинающиеся с "cu" ).

Существуют различные алгоритмы для построения дерева, а также для его поиска, а также для его изменения на лету, но я думал, что я дам концептуальный обзор решения вместо конкретного, поскольку я не знаю, лучший алгоритм для него.

Концептуально алгоритм, который вы могли бы использовать для поиска в дереве, был бы связан с идеей создания типа radix фиксированного количества категорий или значений, которые символ в строке мог бы взять в данный момент времени.

Это позволяет вам проверить одно слово на word-list. Поскольку вы ищете этот список слов в качестве подстрок строки ввода, там будет больше, чем это.

Изменить:. Как упоминалось в других ответах, алгоритм Aho-Corasick для сопоставления строк - это сложный алгоритм для выполнения сопоставления строк, состоящий из trie с дополнительными ссылками для принятия "ярлыков" через дерево и иметь другой шаблон поиска, чтобы сопровождать это. (Интересно отметить, что Альфред Ахо также является автором популярного учебника компиляторов "Компиляторы: принципы, методы и инструменты", а также учебник по алгоритмам "Дизайн и анализ компьютерных алгоритмов". Он также является бывшим членом Bell Маргарет Дж. Корасик, похоже, не слишком много публичной информации о себе.)

Ответ 3

Вы должны попробовать ранее существовавшую утилиту regex, она может быть медленнее, чем ваш ручной алгоритм, но regex - это сопоставление нескольких возможностей, поэтому, скорее всего, он будет уже в несколько раз быстрее, чем хэш-карта или простое сравнение с все строки. Я считаю, что реализация регулярных выражений может уже использовать алгоритм Aho-Corasick, упомянутый RiaD, поэтому в основном вы будете иметь в своем распоряжении хорошо протестированную и быструю реализацию.

Если у вас есть С++ 11, у вас уже есть стандартная библиотека регулярных выражений

#include <string>
#include <regex>

int main(){
     std::regex self_regex("google|yahoo|stackoverflow");
     regex_match(input_string ,self_regex);
}

Я ожидаю, что это создаст наилучшее минимальное дерево совпадений, поэтому я ожидаю, что он будет очень быстрым (и надежным!)

Ответ 4

Одним из самых быстрых способов является использование дерева суффиксов https://en.wikipedia.org/wiki/Suffix_tree, но этот подход имеет огромный недостаток - сложная структура данных с трудным построением. Этот алгоритм позволяет построить дерево из строки в линейной сложности https://en.m.wikipedia.org/wiki/Ukkonen%27s_algorithm

Ответ 5

Изменить: Как указал Маттиу М., ОП спросил, содержит ли строка ключевое слово. Мой ответ работает только тогда, когда строка равна ключевому слову, или если вы можете разделить строку, например. символом пробела.

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

Стоимость выполнения - это хеширование строки, а затем сравнение с единственным возможным кандидатом (O (1) для размера семпла и O (1) для длины строки).

Чтобы сделать регистр сравнения нечувствительным, вы просто используете tolower для семени и вашей строки.

Ответ 6

Поскольку число строк невелико (~ 100), вы можете использовать следующий алгоритм:

• Рассчитайте максимальную длину слова, которое у вас есть. Пусть это N.
• Создайте массив контрольной суммы int checks[N];.
• Пусть контрольная сумма будет суммой всех символов в поисковой фразе. Таким образом, вы можете вычислить такую ​​контрольную сумму для каждого слова из вашего списка (это известно во время компиляции) и создать std::map<int, std::vector<std::wstring>>, где int - контрольная сумма строки, а вектор должен содержать все ваши строки с этой контрольной суммой. Создайте массив таких карт для каждой длины (до N), это также можно сделать и во время компиляции.
• Теперь перейдите по большой строке указателем. Когда указатель указывает на символ X, вы должны добавить значение X char ко всем checks целым числам, а для каждого из них (числа от 1 до N) удалить значение символа (XK), где K - число целых чисел в checks. Таким образом, вы всегда будете иметь правильную контрольную сумму для всей длины, хранящейся в массиве checks. После этого поиска на карте существуют строки с такой парой (длина и контрольная сумма), а если существует - сравните ее.

Он должен давать ложноположительный результат (когда контрольная сумма и длина равны, но фраза не очень).

Итак, пусть R - длина большой строки. Затем, перейдя через него, возьмем O (R). На каждом шаге вы выполняете N операций с небольшим числом "+" (char), N операций с небольшим числом "-" (char), это очень быстро. На каждом шаге вам нужно будет искать счетчик в массиве checks, а это O (1), потому что это один блок памяти.

Также каждый шаг вам нужно будет найти карту в массиве карт, которая также будет O (1), так как это также один блок памяти. И внутри карты вам придется искать строку с правильной контрольной суммой для журнала (F), где F - размер карты, и обычно она будет содержать не более 2-3 строк, поэтому мы можем вообще сделать вид, что это также O (1).

Также вы можете проверить, и если нет строк с той же контрольной суммой (что должно произойти с высокой вероятностью всего за 100 слов), вы можете вообще отбросить карту, сохраняя пары вместо карты.

Итак, наконец, это должно дать O (R), с довольно малым O. Этот способ вычисления checksum может быть изменен, но он достаточно прост и полностью быстр, с очень редкими ложноположительными реакциями.

Ответ 7

Как вариант ответа DarioOOs, вы можете получить, возможно, более быструю реализацию соответствия регулярного выражения, закодировав lex parser для ваших строк, Хотя обычно используется вместе с yacc, это случай, когда lex сам выполняет задание, а lex parsers обычно очень эффективны.

Этот подход может упасть, если все ваши строки длинны, а затем алгоритм, например Aho-Corasick, Commentz-Walter или Rabin-Karp, вероятно, предложит значительные улучшения, и я сомневаюсь, что lex реализация использует любой такой алгоритм.

Этот подход сложнее, если вам нужно настроить строки без реконфигурации, но поскольку flex является открытым исходным кодом, вы можете cannibalize его код.