Система автоматического дополнения запросов для поисковой системы.
Возвращает k наиболее релевантных фраз для поискового запроса пользователя.
Для демонстрации работы в тестах я взял k равное 5, а так можно взять любое.
Изначально система инициализируется списком фраз на естественном языке.
В качестве примера я взял список фраз на русском и английском языках.
Система автодополнения допускает опечатки пользователя, что слово может быть введено не до конца.
Ответы располагаются в порядке наилучшей релевантности.
Основная идея заключается в применении двух следующих техник:
- Использование дерева отрезков merge-sort для быстрого поиска k фраз максимальной стоимости
- Использование алгоритма эффективного поиска расстояния Левенштейна
Список фраз инициализации считывается из файла.
Если через ':' напротив фразы стоит число, то оно считается его частотой.
Если напротив фразы ничего нет, то считается, что частота запроса равна единице.
нужно ли взять сегодня с собой зонт: 143
как сварить Пельмени: 19
зачем искать ключи от машины
Необходимо склонировать репозиторий
git clone https://github.com/olegoratovskiy/vk-autocomplete.git
После этого в директории нужно выполнить следующие команды:
javac AutocompleteTest.java
java AutocompleteTest