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

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

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

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

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

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

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

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

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

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

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

#include <string>
#include <regex>

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

этот подход может упасть, если все ваши строки длинны, как тогда алгоритм, такой как АХО-Корасик,Commentz-Walter или Рабин-Карп вероятно, предложит значительные улучшения, и я сомневаюсь, что реализации lex используют любой такой алгоритм.

этот подход сложнее, если вы должны быть в состоянии настроить струны без перенастройки, но так как гибкий график работы С открытым исходным кодом вы можете каннибализировать его код.