Адаптация текстового поиска для алгоритмов сравнения графиков / молекул
Я ищу механизм текстового поиска для нетрадиционного вида текстового поиска и хочу получить совет о том, какой инструмент (Lucene, Sphinx, Xapian или что-то еще) наиболее подходит для меня, а также указатели того, с чего начать.
У меня есть молекулы, представленные в виде графиков (атомы и связь). У меня есть способ перечислить все подграфы до размера к. Будучи техническими, входными данными являются SMILES, а выходными - канонический SMARTS, а также число раз, которое встречается каждый подграф /SMARTS.
Например, если входной молекулой является " CCO", то каноническими результатами являются {"C": 2, "O": 1, "CC": 1, "OC": 1, "CCO": 1}, и если молекула " SCO", тогда канонические результаты: {"C": 1, "S": 1, "O": 1, "CS": 1, "OC": 1, "SCO": 1}. Это крошечные примеры. Для реальной молекулы я получил около 500 "слов", которые выглядят как "CC(C)O", "CCCOCC", "cn" и "cccc(c)O").
Рассматривая молекулы как совокупность характерных строк плюс число, я должен иметь возможность использовать инструмент текстового поиска для сравнения на текстовом уровне с надеждой, что они имеют смысл на химическом уровне.
Например, я могу использовать косинусное сходство, возможно, с весом tf-idf, и найти похожие молекулы, ища аналогичные субпаттерны. С примерами "CCO" и "SCO" выше, косинусное сходство составляет (2*1+1*1+1*1)/sqrt(2*2+1*1+1*1+1*1+1*1)/ кв.м (6*(1*1)) = 4/ кв.м (8*6) = 0,58.
В другом примере, если я хочу найти молекулы, которые содержат субструктуру "CCS", тогда я могу выполнить быстрый поиск по инвертированному индексу на основе подсчета (молекулы должны иметь по крайней мере 2 "C", по крайней мере 1 "CS", и т. д.) до решения проблемы изоморфизма NP-подграфа. То есть текстовые методы могут выступать в качестве фильтра для отклонения очевидных несоответствий.
Я пытаюсь выяснить текстовые решения, которые существуют, но это немного сложно. Мне не нужны стоп-слова, мне не нужно останавливаться, мне нет дела до порядка слов; Мне не нужно много функций, которые существуют. Мне нужна возможность сохранять векторы слов, так как важно знать, появляется ли буква "С" 2 раза или 3.
Какой текстовый поисковик мне больше всего подходит? Похоже на Lucene, особенно с работой в Mahout. Можете ли вы порекомендовать, какие части документации посмотреть или соответствующие руководства? Те, что я нашел, предназначены для полнотекстового поиска, с основами и другими функциями, которые мне не нужны.
3 ответа
РЕДАКТИРОВАТЬ: Я, возможно, понял это лучше сейчас. Вы хотите сравнить графики, представленные в виде строк. Строки имеют "слова", которые могут повторяться. Вы можете использовать Lucene, и в этом случае я поддерживаю Solr. По сути, каждый документ Solr будет состоять из одного поля; Поле будет содержать строку, которую я предлагаю вам развернуть: write C C вместо C:2, Если вы используете пробел для разделения слов, вы можете использовать WhiteSpaceAnalyzer. Если вы используете другой разделитель, вам может потребоваться написать собственный анализатор, что не так сложно сделать.
Это хорошая идея? Я не уверен. Вот почему:
- Lucene (и Solr) не используют сходство косинусов как таковое, а скорее сходство Lucene, которое смешивает косинус, TF/IDF и булевую оценку с некоторыми конкретными модификациями. Это хорошо работает для большинства текстовых вариантов использования, но может отличаться от того, что вам нужно.
- Вам нужно сравнить хиты из разных поисков? Если вы делаете, это трудно сделать с помощью Solr, поскольку он нормализует каждый поиск до максимального значения 1.
Я предлагаю вам попробовать Solr для небольшого образца вашей базы данных. Если Solr работает на вас, хорошо. Если нет, то, вероятно, лучше всего использовать shingling и min-hash. Mining of Massive Datasets от Rajaraman и Ullman - недавняя бесплатная книга по этим предметам. Я предлагаю вам прочитать это. Он охватывает поиск похожих строк в горах данных. Я полагаю, что дифференциатор: вам нужно относительно большое пересечение? Если это так, используйте shingling и min-hash. Если нет, возможно, Solr достаточно.
Хм... не знаю, что такое СМАРТС, или как на самом деле работает химическое сходство. Если вы хотите использовать Lucene, сначала подумайте об использовании Solr. Поскольку ваши данные представлены в виде графиков, вы можете взглянуть на neo4j с компонентом solr. Кроме того, будет ли эта проблема более тесно связана с документом рядом с дубликатами? Для помощи в этом есть целый ряд алгоритмов LSH, Spotsigs, shingling и simhash. Хотел бы я иметь больше помощи.
Не используйте люцен. Или солр. Внутренние модели устарели и выложены булыжником; хотя они делают хорошую работу. Найти движок с минимальными критериями (если вы хотите отобразить внутри текстового движка) BM25F полностью поддерживается. Если бы я захотел этого, и мне нужно было сообщество по масштабируемости, производительности и низкой стоимости поддержки, честно говоря, я бы пошел с SQL Server и кубами. Лицензирование с SQL Server могло бы стать полной блокировкой. Удачи.