Как сделать idea-подобный поиск?

Question

[pqgg7nwkd4]

В идее можно искать (Shift, Shift) идентификаторы таким образом по началам слов:
Допустим чтобы найти ArrayList можно набрать al, ali, arrli, li, ...
Или что бы найти LinkedHashMap: lh, lhmap, hm, ...

Допустим, разбить идентификаторы на слова я могу, как мне составить индекс и как быстро искать по нему?

UPD: немного уточню/переформулирую вопрос:
Есть список предложений от 100000 штук. В каждом предложении по 1–4 слова.
Допустим одно из предложений "зелёный лес".
Пользователь набирает слово-запрос для поиска и из всего списка предложений нужно найти подходящие. Предложение подходит по запросу, если запрос состоит из конкатенации начал слов в предложении (можно с пропусками слов).
Допустим зелёному лесу соответствуют запросы:
з (зелёный лес)
зл (зелёный лес)
злес (зелёный лес)
зелле (зелёный лес)
зе (зелёный лес)
ле (зелёный лес)
А эти не соответствуют:
зес
ел
ес
Вопрос, как такой фильтр сделать?

Answer 1

[maaGames]

ArrayList
разделяешь на отдельные слова по заглавной букве, подчёркиванию и любым другим символам, допускаемым языком, в том числе и цифрам. получается два слова "array" и "list". регистр ужн оубрать, либо не учитывать его при поиске (либо учитывать, если хочется).
Далее для всех слов создаёшь комбинации, как было описано в комментарии выше, но не вручную, а автоматически
a + l = al
ar + l = arl
arr + l = arrl
...
array + l = arrayl
...
Если слов в идентификаторе больше двух, то проделываешь это для всех слов. Для каждой аббревиатуры записываешь, из какого идентификатора она была получена, одной аббревиатуре может соответствовать много различных идентификаторов).

Это может показаться страшным и занимающим кучу памяти, но идентификаторов в программах конечное число и оно довольно маленькое по машинным меркам.

Comments

[pqgg7nwkd4]

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

[maaGames]

pqgg7nwkd4, Это не совсем перебор, но, в принципе, да. Вариантов будет много "для человека", "для компьютера" вариантов будет не много, буквальнов 20-50 раз больше, чем в программе есть идентификаторов, т.е. не намного больше.

[pqgg7nwkd4]

Я взял для примера список словосочетаний найденный в интернете (dict.ruslang.ru/magn.php?act=search) примерно из 10000 строк (это соизмеримо с тем, что нужно будет мне).
При формировании такого индекса хром занял для этой вкладки дополнительные 120 мегабайт. Не знаю даже много это или нормально. Но, в принципе, на время тестирования "зайдет новая фича или нет", думаю, пойдет. Спасибо.
Но вопрос об оптимизации ещё открыт

[maaGames]

pqgg7nwkd4, В качестве оптимизации можно брать не более трёх первых символов в слове. Уже при наборе по всем потенциально подходящим идентификаторам (их уже будут сотни, а то и всего десятки вариантов) проверять по всем символам.
Ну и понятно, что занимаемая память и скорость поиска будут зависить от способа хранения данных, т.е. от служебных расходов на хранения каждой пары и от того, будет ли идентификатор храниться непосредственно для каждой пары или будет отдельная таблица идентификаторов и для аббревиатур будет указываться индекс идентификатора... Много чего по мелочи можно приделать всякого.

[pqgg7nwkd4]

maaGames, про три я тоже уже попробовал. Допустим человек хочет найти словосочетание "номер комнаты" и вполне вероятно наберет слово номер полностью "номер" - такое уже не найдется, поскольку в индексе этого не будет.

[maaGames]

pqgg7nwkd4, Не правильно поняли. Уточняю.
Пользователь вводит "номерКо". Программа находит все идентификаторы для "ном+ко: "номерКомнаты", "номенклатураКолошей" и т.д. Потом уже по этому списку ищет не по трём первым символам КАЖДОГО слова, а по всем символам. Либо по словам, либо по вхождению введённой части в полный идентификатор.

[pqgg7nwkd4]

maaGames, пользователь вводит "номерко" (без разбивки на слова), как я узнаю, что из этого запроса нужно убрать именно "ер"?
В этом вся и проблема. Это не полнотекстовый поиск. Я даже не знаю как его назвать. Нужно чтобы человек нажимал минимум клавиш.

[maaGames]

pqgg7nwkd4, На ум приходит разбивка вводимого слова по словарю, собранному и слов в имеющемся идентификаторе. Но тут и конфликты могут быть и пользователи любят писать с ошибками. Сразу какого-то действительно работающего решения в голову не приходит...
С другой строны, теперь кажется, что 120 мегабайт не так уж и много, браузеры гигабайты хавают только рекламным ибаннерами.)

Answer 2

[longclaps]

import re

names = ['ArrayList', 'LinkedHashMap']

for s in 'al', 'ali', 'arrli', 'li', 'lh', 'lhmap', 'hm':
    f = re.compile('\\w*'.join(s), flags=re.I).search
    print(f'{s:5}:', list(filter(f, names)))

выхлоп:

al   : ['ArrayList']
ali  : ['ArrayList']
arrli: ['ArrayList']
li   : ['ArrayList', 'LinkedHashMap']
lh   : ['LinkedHashMap']
lhmap: ['LinkedHashMap']
hm   : ['LinkedHashMap']

Comments

[Dimonchik]

чОтко

но про

разбить идентификаторы на слова

интереснее

хотя - корпус конечен, конечно, если все имена переменных в корректном стиле

[pqgg7nwkd4]

Хочу понять код, но не могу понять что за язык даже).
Что вот это значит '\\w*'.join(s)?

[longclaps]

pqgg7nwkd4, это python. А ты хоть что-то знаешь?

[pqgg7nwkd4]

longclaps, решение неверное. В твоем случае по запросу "rr" найдется ArrayList, а не должен.

[longclaps]

Как сделать idea-подобный поиск?

Ну что ж, pqgg7nwkd4, идеи под рукой нет, но есть PyCharm - те же яйца. Проверим.

Так должен или не должен?

[pqgg7nwkd4]

longclaps, видимо не те же. В идее в явовском проекте по rr не находится ArrayList (при настройках по умолчанию).
Я попытался уточнить вопрос.

[longclaps]

pqgg7nwkd4, я посмотрел на твой пример и думаю, что это плохая идея. Смотри:
Вот ты набрал строчку abc. Сколько паттернов она порождает?

Abc
A\w*Bc
Ab\w*C
A\w*B\w*C

- уже 4, т.е. 2^(колич.букв - 1). На длинных строчках это будет нещадно тормозить.

[pqgg7nwkd4]

longclaps, в идее же как-то работает

[longclaps]

в идее же как-то работает

pqgg7nwkd4, есть одна загвоздка - ты не миддл из JetBrains, и не фонтанируешь идеями относительно решения. Я сделал утверждение насчет числа паттернов - похоже, ты не в состоянии критически его осмыслить (оно верное, но я это знаю, а ты в лучшем случае примешь на веру).

решение неверное

У тебя пока нет и такого. Но ты можешь попробовать реализовать то, что предложил maaGames. Или допилить моё - как я бы смог. Но твой вердикт демотивирует - извини, дальше без меня.

[pqgg7nwkd4]

Пожалуйста, не пиши, если можешь не писать.