Лучший способ поддержки подстановочного поиска в большом словаре?

Question

Я работаю над проектом для поиска в большом словаре (100k ~ 1 млн слов). Элементы словаря выглядят как {ключ, значение, частота}. Моя задача - разработка алгоритма инкрементного поиска для поддержки точного совпадения, совпадения префикса и совпадения с подстановочными знаками. Результаты должны быть заказаны по частоте.

Например: словарь выглядит как

key1=a,value1=v1,freq1=4
key2=ab,value2=v2,freq2=2
key3=abc,value3=v3 freq3=1
key4=abcd,value4=v4,freq4=3

когда пользователь вводит 'a', возвращается v1, v4, v2, v3
когда пользователь вводит 'a? c', возвращают v4, v3

Теперь мой лучший выбор - это дерево суффиксов, представленное структурой данных DAWG, но этот метод не поддерживает подстановочные совпадения эффективно.

Есть предложения?

Answer 1

Вам нужно взглянуть на n-грамм для индексации вашего контента. Если вы хотите что-то из коробки, вы можете посмотреть на Apache Solr , который выполняет за вас большую тяжелую работу Он также поддерживает префикс, групповые запросы и т. Д.