Эффективный поиск по словарю

Question

Эффективный поиск по словарю

Для моего приложения C++ существует требование проверить, является ли слово допустимым английским словарем или нет. Как лучше всего это сделать? Есть ли в свободном доступе словарь, который я могу использовать. Мне просто нужен набор всех возможных слов. Как сделать этот поиск наименее дорогим. Мне нужно, чтобы хэш.

554 3

c++

3 ответов:

Comments

Ничего не найдено.

James Kanze · Accepted Answer · 2011-06-02 10:56:48

Что касается наличия списка слов, то он зависит от платформы. В Linux /usr/share/dict/words содержит список английских слов это может удовлетворить ваши потребности. В противном случае такие списки, несомненно, существуют доступно в сети.

Учитывая размер таких списков, наиболее быстрым доступом будет их загрузка в хэш-таблицу. std::unsorted_set, если он у вас есть; в противном случае, многие Компиляторы C++ поставляются с hash_set, хотя разные компиляторы имеют немного другой интерфейс для него, и положить его в различный пространство имен. Если это все еще имеет проблемы с производительностью, это можно сделать лучше, если вы заранее знаете количество записей (так что таблица никогда должен расти), и реализовать хэш-таблицу в std:: vector (или даже a C style array); обработка коллизий будет немного сложнее, однако.

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

James McNellis · Accepted Answer · 2011-06-02 09:52:30

Используйте либо std::set<std::string>, либо std::unordered_set<std::string>. Последняя является новой в C++0x и может или не может поддерживаться вашей реализацией стандартной библиотеки C++; если она не поддерживает ее,она может включать в себя hash_set некоторого вида: обратитесь к документации, чтобы узнать.

Какой из них (set, использующий бинарное дерево поиска, и unordered_set, использующий хэш-таблицу) является более эффективным, зависит от количества элементов, которые вы храните в контейнере, и от того, как ваша стандартная реализация библиотеки реализует их. Лучше всего попробовать оба варианта и посмотреть, какой из них лучше подходит для вашего конкретного сценария.
В качестве альтернативы, если список слов фиксирован, вы можете использовать сортированный std::vector и использовать std::binary_search для поиска слов в нем.

TheChes44 · Accepted Answer · 2011-06-02 09:41:30

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

Как на этом сайте: http://wordlist.sourceforge.net/

Просто поместите его в текстовый файл и сравните слова с тем, что есть в списке. Это должен быть порядок n, где n - количество слов в списке. Нужна ли вам временная сложность быстрее?

Надеюсь, это поможет.