Быстрый способ проверить, содержит ли String слово из файла словаря?

Question

Скажем, у меня есть файл со словами:

• Яблоко
• Bacon
• Телефон
• И так далее, есть около 2000 слов.

Я тогда строка:

I was eating some Apple-bacon when the phoNe rang. 

Я пытаюсь найти быстрый способ привести:

I was eating some *****-***** when the ***** rang. 

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

Я использую C++ 98.

Answer 1

Мне просто интересно, есть ли лучший способ, чем итерация через вектор.

Используйте либо binary_search на отсортированном векторе или std::set для гарантированного O (Lg п) время поиска. lg (2000) = 7,6, в 263-кратном увеличении скорости теории, не обращая внимания на любые постоянные факторы.

(Хотя это на самом деле лучше подходит для регулярных выражений.)

Answer 2

Первую попытку будет разметить фразу и искать каждое слово в карте или set.

Однако, если у вас есть сервер, которому необходимо обработать много сообщений, вы могли бы подумать о его внедрении немного умнее. Пройдите через строку, посимвольно и поиск внутри некоторых лучше структуры данных, как те:

• дерева суффиксов всех слов, или
• значения хэша всех слов

Затем замените символы место с *.

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

Answer 3

Есть несколько вариантов, чтобы ускорить поиск.
Один из самых простых подходов, если у вас уже есть вектор слов, это sort вектор и сделать binary_search

Answer 4

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

Пример:

слова: Ape, Ace, Апа, По,

Дерево

 A  B 
    /|  | 
    p c  y 
    /| | 
    e a e 

поиск:

1) итерация корыто каждый символ в строке для верхних символов уровня (A или B)
2) если найдено, проверьте, является ли следующая буква первым.

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

Answer 5

Поиск Trie - это, вероятно, лучший способ. Создайте дерево всех слов в словаре и сравните ввод сверху. Когда видит букву не алфавита, перезагрузите и начните с вершины дерева снова