Самый быстрый способ поиска по ключевым словам в большом тексте на C / C ++

Question

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

Моя текущая идея заключается в следующем:

• превратить ключевые слова в дерево суффиксов
• пройти по тексту послеузлы и всякий раз, когда символ не встречается (то есть, node-> next == NULL) в дереве суффиксов, переходите к следующему слову и ищите снова

Структура дерева суффиксов будет выглядеть примерно так:

struct node {
   int count; //number of occurences (only used at leaf node)
   /* for each lower-case char, have a pointer to either NULL or next node */
   struct node *children[26];
};

Я уверен, что есть более быстрый способ сделать это, но что это?Эффективность использования пространства в данном случае не имеет большого значения (отсюда и массив детей для более быстрого поиска), но эффективность времени действительно есть.Есть предложения?

Answer 1

Проблема с подходом дерева суффиксов заключается в том, что вам нужно начать поиск суффиксов для каждой буквы текста, который нужно найти. Я думаю, что лучшим способом было бы организовать поиск по каждому ключевому слову в тексте, но с использованием некоторого метода быстрого поиска с предварительно вычисленными значениями, например Boyer-Moore .

РЕДАКТИРОВАТЬ :

ОК, вы можете быть уверены, что это может быть быстрее. Бойер-Мур очень быстр в среднем случае. Рассмотрим, например, что строки имеют среднюю длину m. BM может быть так же быстро, как O (н / м) для «нормальных» струн. Это было бы 100 * O (н / м). Среднее значение должно составлять O (n * m) (но это правда, что в реальной жизни оно может быть намного быстрее), поэтому, если 100 >> m, то значение выигрыша получается.

Теперь о случайных идеях по оптимизации. В некоторых алгоритмах сжатия, которые должны выполнять обратный поиск, я видел частичные хеш-таблицы, проиндексированные двумя символами строки. То есть, если проверяемая строка представляет собой последовательность символов c1, c2 и c3, вы можете проверить, что указано:

if (hash_table[c1 * 256 + c2] == true) check_strings_begining with [c1,c2]

затем для c2 и c3, и так далее. Удивительно, сколько случаев вы избегаете, выполняя эту простую проверку, так как этот хэш будет истинным только каждые 100/65536 раз (0,1%).

Answer 2

Если это промышленное приложение, используйте Boost Regex

Это проверено, быстро, и есть вероятность, что это избавит вас от многих болей.

Answer 3

Вы, кажется, нащупываете свой путь к http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm

Цитата:

Сложность алгоритма линейна по длине паттернов плюс длинаискомый текст плюс количество найденных совпадений.Обратите внимание, что поскольку все совпадения найдены, может быть квадратичное количество совпадений, если каждая подстрока соответствует (например, dictionary = a, aa, aaa, aaaa, а входная строка - aaaa).

Answer 4

Это то, что я хотел бы сделать.

1. Поместите все ваши ключевые слова в хэш-таблицу пар ключ-значение, с количеством вхождений ключевого слова в качестве значения и ключевого слова в качестве (как вы уже догадались) ключ.
2. проверьте каждое слово в текстовом блобе против хеш-таблицы.если слово находится в хеш-таблице, увеличьте связанный с ним счетчик вхождений.

Это хороший способ, поскольку поиск по хеш-таблице выполняется (или должен быть) амортизированным O (1) разом.Весь алгоритм имеет линейную сложность:).

РЕДАКТИРОВАТЬ: Если ваши ключевые слова могут содержать пробелы, вам нужно будет сделать своего рода DFA.Сканируйте файл, пока не найдете слово, с которого начинается одна из ваших ключевых фраз.Если второе (или сколько угодно) следующих слов является частью «ключевой фразы», ​​то увеличьте счетчик совпадений.