Хеш таблица для быстрого поиска по названию или его части

[ilghiz]

Добрый день,

имеется волонтерская база химических веществ, в которой имеется около 100 миллионов записей. По многочисленным просьбам трудящихся, хочется в базу прикрутить удобный поиск по названию, другие способы поиска уже более-менее функционируют, на базу можно посмотреть здесь.

Каждое название вещества - это что-то типа

Цитата:

(2E,5R)-2-[3-bromo-4-(4-fluorobenzyl)oxy-5-nitro-benzylidene]-7-ethyl-3-keto-5-phenyl-5H-thiazolo[3,2-a]pyrimidine-6-carboxylic acid methyl ester

то есть строка иногда недеццкой длины. То есть хочется это хешировать по лексемам, например как

Цитата:

brom
fluor
benzyl
oxy
nitro
ethyl
keto
phenyl
thiazolo
pyrimidine
carboxylic
acid
methyl
ester

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

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

Или найти минимальный малоранговый набор столбцов (но тут будет больше неоднозначности).

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

Спасибо!

[mihaild]

Пока не очень понятно. У вас каждое вещество представленно набором лексем, пользователь вводит тоже набор лексем, и хочется найти вещества, содержащие все указанные пользователем лексемы, без учета порядка?

[aitap]

Я думаю, что это задача полнотекстового поиска. Именно SQLite использовать, может быть, и не предлагаю (хотя на редко изменяемых базах данных размером до гигабайта с хорошо построенными индексами он может летать), но саму идею обратного индекса для решения задачи поиска рекомендую.

Суть в том, что строки (и те, которые нужно искать, и те, которые ищет пользователь) тем или иным способом разбивают на слова. При работе с "человеческими" текстами их обычно обрабатывают дальше (стеммером/лемматизатором, чтобы автоматически привести слова к эквиваленту начальной формы), но здесь, возможно, достаточно применить знания о номенклатуре ИЮПАК. После этого создают таблицу, которая соотносит токены с индивидуальными номерами, а также таблицу, содержащую по строке на каждое вхождение токена в документ.

Вас интересует, как выделить наиболее важные токены, руководствуясь не априорными знаниями (стеммер/лемматизатор/ИЮПАК), а $n$-граммами (подпоследовательностями из $n$ символов). Если у Вас есть возможность получить все $n$-граммы для всех формул, возможно, поможет пропустить их через tf-idf: для каждой $n$-граммы в каждой формуле посчитать частоту её встречаемости в данной формуле и поделить на (обычно логарифм) частоту встречаемости формул с данной $n$-граммой. После этого можно отобрать $n$-граммы по максимальному значению $\mathrm{tf} \cdot \mathrm{idf}$ или по другому критерию. Какая-то предобработка текста точно понадобится, иначе такой подход подберёт уникальные опечатки и другие вещи, которые реальные пользователи, скорее всего, искать не будут.

Возможно, в книге Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze, Introduction to Information Retrieval, Cambridge University Press. 2008 Вы найдёте что-то полезное.

[Geen]

ilghiz в сообщении #1544942 писал(а):

для каждого названия найти все возможные комбинации слов и их кусков

Насколько это осмысленно? - перестановка скобок или пары букв может дать совершенно другое вещество. Скорее, речь может идти о синонимах (в рамках правил UIPAC).

-- 03.01.2022, 00:28 --

В любом случае, с такими вопросами полезнее идти к химикам, а не программистам.

[rockclimber]

ilghiz в сообщении #1544942 писал(а):

По многочисленным просьбам трудящихся, хочется в базу прикрутить удобный поиск по названию

В чем будет заключаться "удобство"? Можете привести пример вида: вот такие несколько (похожих) строк есть в БД, вот такое вводит пользователь, вот эти строки - находим, вон те - нет?

ilghiz в сообщении #1544942 писал(а):

(2E,5R)-2-[3-bromo-4-(4-fluorobenzyl)oxy-5-nitro-benzylidene]-7-ethyl-3-keto-5-phenyl-5H-thiazolo[3,2-a]pyrimidine-6-carboxylic acid methyl ester

Как именно осуществляет поиск пользователь? Насколько я помню ИЮПАК, он работает так: в молекуле выделяется "основная часть", она получает название, дальше на это основное название навешиваются в строго заданном порядке названия "дополнительных" частей молекулы. Пользователь же не будет вводить всю строку, начиная с "(2E,5R)", а скорее начнет с "pyrimidine-6-carboxylic acid"? Или нет?

ilghiz в сообщении #1544942 писал(а):

То есть хочется это хешировать по лексемам

Так ли нужно именно хэшировать? Каждая лексема в данном случае - "вещь в себе", ее можно просто обозначить одним битом. Например так:
1. Анализируем всю базу, выделяем все лексемы
2. Нумеруем лексемы
3. Создаем битовые маски для каждого вещества
4. Анализируем запрос, выделяем лексемы запроса
5. Из лексем делаем битовую маску.
Допустим, в БД есть вещества с лексемами "метил" (№1), "спирт" (№2), "эфир" (№3). Пользователь вводит запрос, содержащий "метил" и "спирт". Получается битовая маска 110. Дальше сравниваем ее с аналогично построенными битовыми масками для веществ в базе, выводим наименее отличающиеся.

Писал быстро и сумбурно, спать уже хочется. Надеюсь, понятно написал.

ilghiz в сообщении #1544942 писал(а):

имеется волонтерская база химических веществ, в которой имеется около 100 миллионов записей.

Вы вроде писали, что работаете в компании, которая разрабатывает софт для ЯМР спектрометров? Или это уже другая база?

P. S. А СУБД у вашей волонтерской базы какая? Реляционная или какая-то специализированная? Я, если что, очень хорошо знаю SQL и всё, что с ним связано, и когда-то знал химию. Могу немного порпобовать поучаствовать, если вы принимаете волонтеров.

P. P. S.

Geen в сообщении #1544967 писал(а):

В любом случае, с такими вопросами полезнее идти к химикам, а не программистам.

Полезнее всего с такими вопросами идти к программистам, которые когда-то были химиками. Например, ко мне

[ilghiz]

Спасибо большое, всем за интересные обсуждения и советы!

Попытаюсь дополнить что я вижу, и зачем мне этот поиск.

База создана в нашей фирме, так как мы провели математическое моделирование тех молекул, что есть в этой базе для другого проекта, а резульаты такого мататематического моделирования мы решили предоставлять бесплатно всем и вдальнейшем регулярно пополнять. То есть мы предоставляем полностью бесплатную возможность поиска всех 1.7 миллиардов конформеров и сохранения результатов поиска с стандартном MOL формате, но саму базу скачать у нас нельзя - мы это не даем, также как и не разглашаем все детали алгоритмов, которые позволили сохранить всю этту информацию всего-то в 260 гигабайтах с довольно быстрым индексированием.

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

Почему это нужно.

Вот допустим, Вы ищите глюкозу. Если Вам известна брутто формула (C6H12O6), вы ее конечно можете вбить, но, результаты поиска Вас, к сожалению не обрадуют. Их будет больше 5000 и Вы можете не найти в этих результатах искомую глюкозу просто недолистав до нужной страницы. На данный момент дополнительно Вы можете указать кучу дополнительных свойств, как например, число двойных-тройных связей, наличие каких-либо функциональных групп, и сильно сузить поиск, но все равно будет десятки-сотни результатов, а может и десятки-сотни страниц результатов поиска.

Я хочу добвить часть лексемы из названия (у нас есть и номенклатурные и общеупотребительные названия), и дополнить способ поиска по какой-то лексеме.

В случае глюкозы, либо надо будет написать еще в одном поле "glucose" либо хотя бы "tetrol".

У меня есть названия, я могу получить с них лексемы, и найти наиболее употребительные лексемы, либо пойти по принципу гугла. Но в моем случае, напрямую подход Гугла с резреженным сингулярным разложением, как мне кажется, не будет работать, так как мне надо выщемлять из названия общеупотребительные части, и делать это автоматически. Я не хочу это делать руками, я хочу придумать автоматический способ нахождения таких лексем, так как в базе около 100 миллионов названий и часто у названия есть еще несколько синонимов.

Собственно поэтому этот вопрос тут и возник. То есть также, с радостью прислушаюсь к любым Вашим предложениям как удобнее искать по названию в нашей базе.

-- 03.01.2022, 01:55 --

rockclimber в сообщении #1544969 писал(а):

Пользователь же не будет вводить всю строку, начиная с "(2E,5R)", а скорее начнет с "pyrimidine-6-carboxylic acid"? Или нет?

да, верно, более того, хочется, чтобы пользователь мог ввести две-три правильные лексемы, типа "pyrimidine" + "carboxylic" + "acid" и, добавив бруттто-формулу получил уже очень ограниченный результат поиска, в котором не надо долго искать то, что ему надо.

-- 03.01.2022, 01:57 --

rockclimber в сообщении #1544969 писал(а):

Вы вроде писали, что работаете в компании, которая разрабатывает софт для ЯМР спектрометров?

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

-- 03.01.2022, 01:59 --

rockclimber в сообщении #1544969 писал(а):

Так ли нужно именно хэшировать? Каждая лексема в данном случае - "вещь в себе", ее можно просто обозначить одним битом. Например так:
1. Анализируем всю базу, выделяем все лексемы
2. Нумеруем лексемы
3. Создаем битовые маски для каждого вещества
4. Анализируем запрос, выделяем лексемы запроса
5. Из лексем делаем битовую маску.
Допустим, в БД есть вещества с лексемами "метил" (№1), "спирт" (№2), "эфир" (№3). Пользователь вводит запрос, содержащий "метил" и "спирт". Получается битовая маска 110.

правильно, именно так у нас по радикалам поиск устроен, но у меня основная проблема - как автоматически выделить лексемы, чтобы они были наиболее информативны и их не было очень много.

[rockclimber]

ilghiz в сообщении #1544972 писал(а):

основная проблема - как автоматически выделить лексемы, чтобы они были наиболее информативны и их не было очень много

Поскольку лексемы эти изначально происходят из естественного языка, полностью автоматическое решение кажется мне в принципе невозможным... Я бы начал так:
1. Сгенерировать полный список лексем (выделяя, например, из строк с названиями куски, состоящие из букв, если их длина - 3 и больше символов)
2. Посчитать, сколько раз каждая лексема встречается в базе
3. Вывести наиболее редко встречающиеся, просмотреть глазами, определить, есть ли среди них "неинформативные"
4. Вывести самые короткие, просмотреть глазами, определить, есть ли среди них "неинформативные"
5. Создать список исключений из неинформативных элементов.

Или, как еще одно дополнительное решение - сделать график вида "количество раз, сколько лексема встречается в базе" (по оси X) - "количество лексем, встречающихся столько раз" (ось Y). Посмотреть на график глазами, есть ли на нем какие-то резкие перепады, и объявить неинформативными те лексемы, которые встречаются меньше раз, чем количество, выбранное на графике. Или наоборот, неинформативными могут показаться те, которые встречаются слишком часто.

[ilghiz]

Спасибо большое, rockclimber, за советы!

Лексмы я уже строил, их больше 200к. Почти полное заполнение двух и трехбуквенных лексем, и даже 4-х буквенных больше 10к имеется и почти сотня тысяч длинных от 8 букв.

Конечно величины распространения у них сильно отличаются, но те короткие, что встречаются, очень неинформативны.

Мне хотелось бы иметь под сотню лексем, может 2-3 сотни, максимум. Ведь для моей базы каждая сотня лексем потянет на гигабайт индексного массива, который надо иметь в быстрой памяти, а мне не хотелось бы много такой памяти расходовать.

Я понимаю, что из этого набора лексем можно найти какой-то минимальный набор, так, что для каждого вещества битовая маска этого набора не совпадала бы по базе, но я не представляю как построить такой набор, в голову приходят только эвристические алгоритмы, которые по вычислительной сложности не совместимы с поиском по 200к лексем и 100м записей.

Чисто гепотетически, если бы лексемы в названиях распределены были бы равнмерно, то для кодирования битовой маской 100 миллионов записей мне было бы достаточно меньше 30 лексем, но, я предполагаю, что так не получится и придется использовать пару сотен лексем.

В этом-то и весь сыр-бор по автоматическому поиску оптимального набора лексем. ИМХО, лексемы долны быть такими, чтобы юзер с их помощью дополнял свой поиск, вот ищет он дейтерированный агент в виде кислоты, значит надо написать "acid" "deuter" причем именно deuter, а не deutero, так как есть и deuteri. Конечно к меня есть это же в списке радикалов, но, туда никто не смотрит.

Пока, по совету уважаемого aitap (спасибо большое!!!), читаю книгу Маннинга, надеюсь, вычитать там что-то для себя полезное.

[Mihaylo]

ilghiz
Мне кажется, если вы добились выдачи результата в 5000 записей, то вам нужно просто автоматически сгруппировать их. Это выглядело бы как размещение в папках. В папках проще рыться.
То есть не спрашивать у пользователя допинформацию для дальнейшего поиска, а наоборот пойти ему навстречу и предоставить ему готовые варианты дальнейшего поиска.

Берете пул записей, находите среднераспространенную лексему (как можно ближе к 50% встречаемости в пуле) и тем самым делите пул на две части, кладете в разные папки "есть лексема ХХХ" и "нет лексемы ХХХ". И так далее и как-то так.

[ilghiz]

Спасибо большое, Mihaylo, за идею!

Для не очень большого числа результатов поиска (50-200) наверное это очень классное решение. Я могу попробовать сгруппировать по наличию радикалов и еще каких свойств, чтобы у юзера был только не очень большой список, который можно было бы потом раскрыть и посмотреть.

Для произвольно большого числа резульатов поиска, не все так хорошо, к сожалению.

Тут вот в чем проблема. База сильно структурирована и заточена на иерархический поиск по частям молекул и молекулы сохранены в иерархически сжатом виде. Грубо говоря, всреднем мне надо 3 байта на атом в конформере (один из вариантов как молекула представлена в пространстве) для хранения всей информации. Вот когда я из базы эту информацию вытащил, она уже сохраняется совсем не сжатом виде, и всреднем на атом в конформере мне надо около 40 байт (три флоата + индексы и все в текстовом json). Также я не запоминаю что юзер до этого искал - каждый запрос сразу резолвится в комплект данных, который улетает в веб интерфейс к юзеру и там визуализируется. В будующем данных будет еще больше, я хочу отрисовывать орбитали, и там вместо 40 байт на атом в конформере будет пару сотен байт.

Если послать юзеру весь комплект поиска на 5000 или более молекул, то это будет довольно много, 40(байт на атом в конформере)*50(среднее число атомов в конформере)*20(среднее число конформеров в молекуле)*5000(результат поиска) = 200МБ, а может и больше получиться. В этом случае морда (веб морда) у юзера может крякнуть от такого объема данных, да и сервер не на супержирном канале, не хотелось бы зазря посылать кучу не сильно нужной пользователю информации.

Хотя как раз такой способ с лексемами можно применить внутри поиска, но тут есть другая сторона медали. Если так сделать, то юзер совсем не будет ограничивать свой поиск наличием брутто-формулы и кучи других параметров, а у меня локально будет создаваться список из 5000 и больше подходящих кандидатов, из которых я буду все это парсить и только то, что отпарсилось, буду посылать. Если юзер задаст в поиске C1-999 (все, что содержит хотя бы один атом углерода), то у меня будет 1.3 миллиарда ответов, и поиск по их названиям будет весьма трудоемкий и совсем не оптимальный. В этом как раз-то и всесь сыр-бор.