Queryable Language Dictionary и функция поиска слова

Question

В будущем проекте мне потребуется реализовать функцию, предназначенную для поиска слов (либо по длине, либо по заданному набору символов и их позиции в слове), которая будет возвращать все слова, которые соответствуют определенным критериям.

Для этого мне понадобятся языковые словари, которые можно легко запрашивать в LINQ. Прежде всего я хотел бы спросить, знает ли кто-нибудь о хороших словарях, которые можно использовать в таких приложениях и среде.

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

Answer 1

Не зная точного набора вещей, которые вы, вероятно, должны оптимизировать, трудно сказать.Стандартными структурами данных для эффективной организации большого набора слов для быстрого поиска является структура данных «trie», или, если важна нехватка места (например, если вы пишете программу для телефона или другую ограниченную памятью среду)затем DAWG - направленный ациклический словесный граф.(DAWG - это, по сути, трия, объединяющая общие пути к листьям.)

Другие интересные вопросы, на которые я хотел бы получить ответ перед тем, как разрабатывать структуру данных, таковы: изменится ли когда-нибудь словарь?Если это действительно изменится, есть ли ограничения производительности относительно того, как быстро новые данные должны быть интегрированы в структуру?Будет ли структура использоваться только в качестве устройства быстрого поиска, или вы хотели бы также хранить в ней сводную информацию о словах?(Если последнее, то DAWG не подходит, так как два слова могут совместно использовать одинаковые узлы префикса и суффикса.) И т. Д.

Я бы искал в литературе информацию о попытках, DAWG и способах оптимизации программ Scrabble.;Очевидно, что Scrabble требует всевозможных хитрых поисков совокупности строк, и в результате были созданы очень быстрые варианты структур данных DAWG, созданных энтузиастами Scrabble.

Недавно я написал неизменную структуру данных в Trie.C #, о котором я планирую вести блог в какой-то момент.Я обновлю этот ответ в ближайшие месяцы, если в конечном итоге сделаю это.