Потребность C++ сравнить одну строку с 200 000 слов
В моей программе в C++...
Пользовательские типы в программе представляют "нечто" в виде строки.
Я должен сравнить эту строку со своими строками в txt файлах для записи: эта строка является существительным! (или прилагательное...)
Я получил немного файлов TXT - один файл с существительными, 2-й файл с прилагательными..., но в каждом файле является приблизительно 200 000 слов.
Как я могу эффективно сравнить эту строку "нечто" со строками в моих файлах?
Что я должен использовать?
6 ответов
Используйте для этого структуру данных TRIE . Вам понадобится немного памяти для построения структуры данных. Но ваша цель будет наиболее эффективной.
Я бы рекомендовал вместо этого использовать sqlite для ваших файлов.
Вы можете создать CRC для каждого значения ключа и сохранить ключ и значения (int) в таблице. Создайте индекс для ключевого поля.
Если вы хотите выполнить поиск, вы можете взять CRC слова и выполнить поиск в таблице.
Поместите свои слова в контейнеры std :: set и выполните поиск по ним. Это дает время O (log n) для доступа, которого, вероятно, достаточно для того, что вы делаете.
Вы также можете использовать std :: map , где ключ - это слово, а значение - это класс (например, «существительное»).
Радикс-дерево обеспечит лучшее использование памяти для строк, чем «обычное» дерево, если у вас много строк с общими корнями / префиксами (что, вероятно, имеет место для словаря, то есть слов с многие формы - хотя это, вероятно, будет зависеть от языка).
Вам просто нужно подтвердить, соответствует ли оно чему-либо?
Если да, используйте Trie.
Вы можете сохранить внешний файл, проиндексированный как btree или как связанную хеш-таблицу, это обеспечит действительно быстрое время поиска и минимальное количество попыток найти данные.