Как сделать idea-подобный поиск? В идее можно искать (Shift, Shift) идентификаторы таким образом по началам слов:
Допустим чтобы найти ArrayList можно набрать al, ali, arrli, li, ...
Или что бы найти LinkedHashMap: lh, lhmap, hm, ...
Допустим, разбить идентификаторы на слова я могу, как мне составить индекс и как быстро искать по нему?
UPD: немного уточню/переформулирую вопрос:
Есть список предложений от 100000 штук. В каждом предложении по 1–4 слова.
Допустим одно из предложений "зелёный лес".
Пользователь набирает слово-запрос для поиска и из всего списка предложений нужно найти подходящие. Предложение подходит по запросу, если запрос состоит из конкатенации начал слов в предложении (можно с пропусками слов).
Допустим зелёному лесу соответствуют запросы:
з (зелёный лес)
зл (зелёный лес)
злес (зелёный лес)
зелле (зелёный лес)
зе (зелёный лес)
ле (зелёный лес)
А эти не соответствуют:
зес
ел
ес
Вопрос, как такой фильтр сделать?
Как сделать idea-подобный поиск? В идее можно искать (Shift, Shift) идентификаторы таким образом по началам слов:
Допустим чтобы найти ArrayList можно набрать al, ali, arrli, li, ...
Или что бы найти LinkedHashMap: lh, lhmap, hm, ...
Допустим, разбить идентификаторы на слова я могу, как мне составить индекс и как быстро искать по нему?
UPD: немного уточню/переформулирую вопрос:
Есть список предложений от 100000 штук. В каждом предложении по 1–4 слова.
Допустим одно из предложений "зелёный лес".
Пользователь набирает слово-запрос для поиска и из всего списка предложений нужно найти подходящие. Предложение подходит по запросу, если запрос состоит из конкатенации начал слов в предложении (можно с пропусками слов).
Допустим зелёному лесу соответствуют запросы:
з (зелёный лес)
зл (зелёный лес)
злес (зелёный лес)
зелле (зелёный лес)
зе (зелёный лес)
ле (зелёный лес)
А эти не соответствуют:
зес
ел
ес
Вопрос, как такой фильтр сделать?
Допустим чтобы найти ArrayList можно набрать al, ali, arrli, li, ...
Или что бы найти LinkedHashMap: lh, lhmap, hm, ...
Допустим, разбить идентификаторы на слова я могу, как мне составить индекс и как быстро искать по нему?
UPD: немного уточню/переформулирую вопрос:
Есть список предложений от 100000 штук. В каждом предложении по 1–4 слова.
Допустим одно из предложений "зелёный лес".
Пользователь набирает слово-запрос для поиска и из всего списка предложений нужно найти подходящие. Предложение подходит по запросу, если запрос состоит из конкатенации начал слов в предложении (можно с пропусками слов).
Допустим зелёному лесу соответствуют запросы:
з (зелёный лес)
зл (зелёный лес)
злес (зелёный лес)
зелле (зелёный лес)
зе (зелёный лес)
ле (зелёный лес)
А эти не соответствуют:
зес
ел
ес
Вопрос, как такой фильтр сделать?
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Для реализации такого поиска можно воспользоваться структурой данных Trie илипрефиксногодереваили префиксного дереваилипрефиксногодерева. Trie позволяет эффективно хранить и быстро искать строки, где каждая вершина представляет собой один символ.
Для вашего случая, можно построить Trie, в котором каждая вершина будет представлять одно слово из предложения. При этом для каждого слова из предложения нужно добавить в Trie все возможные комбинации начал слов, включая пропуски слов.
Например, для предложения "зелёный лес" в Trie будут добавлены следующие строки:
зелёный лесзелёныйзелёный лезелёный леслеслезеКогда пользователь вводит запрос, можно пройти по Trie, составленному из списка предложений, и проверять, есть ли в Trie соответствующая комбинация для данного запроса. Если такая комбинация найдена, то предложение соответствует запросу.
Такой фильтр позволит эффективно находить подходящие предложения по заданному запросу, осуществляя поиск за время, зависящее линейно от длины запроса.