адаптация текстового поиска для алгоритмов сравнения графиков / молекул

Question

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

У меня есть молекулы, представленные в виде графиков (атомы и связь). У меня есть способ перечислить все подграфы до размера k. Будучи техническими, входными данными являются 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. Можете ли вы порекомендовать, какие части документации посмотреть или соответствующие руководства? Те, что я нашел, предназначены для полнотекстового поиска, с основами и другими функциями, которые мне не нужны.

Answer 1

РЕДАКТИРОВАТЬ: Возможно, я понял это лучше сейчас. Вы хотите сравнить графики, представленные в виде строк. Строки имеют «слова», которые могут повторяться. Вы можете использовать Lucene, и в этом случае я поддерживаю Solr. По сути, каждый документ Solr будет состоять из одного поля; Поле будет содержать строку, которую я предлагаю вам развернуть: напишите C C вместо C:2. Если вы используете пробел для разделения слов, вы можете использовать WhiteSpaceAnalyzer. Если вы используете другой разделитель, вам может потребоваться написать собственный анализатор, что не так сложно сделать.

Это хорошая идея? Я не уверен. И вот почему:

1. Lucene (и Solr) не используют сходство косинусов как таковое, а скорее Подобие Lucene , которое смешивает косинус, TF / IDF и булевую оценку с некоторыми конкретными модификациями. Это хорошо работает для большинства текстовых вариантов использования, но может отличаться от того, что вам нужно.
2. Вам нужно сравнить хиты из разных поисков? Если вы это сделаете, то с помощью Solr это трудно сделать, так как при каждом поиске нормализуется максимальное значение 1.

Я предлагаю вам попробовать Solr для небольшого образца вашей базы данных. Если Solr работает на вас, хорошо. Если нет, то, вероятно, можно использовать shingling и min-hash. Разработка массивов массивных данных Раджараманом и Уллманом - это недавняя бесплатная книга на эту тему. Я предлагаю вам прочитать это. Он охватывает поиск похожих строк в горах данных. Я думаю, что дифференциатор: вам нужно относительно большое пересечение? Если это так, используйте shingling и min-hash. Если нет, возможно, Solr достаточно.

Answer 2

Хм ... на самом деле не знаю, что такое СМАРТС или как на самом деле работает химическое сходство. Если вы хотите использовать Lucene, сначала подумайте об использовании Solr. Поскольку ваши данные представлены в виде графиков, вы можете взглянуть на neo4j с компонентом solr. Кроме того, будет ли эта проблема более тесно связана с документом рядом с дубликатами? Для помощи в этом есть ряд алгоритмов LSH, Spotsigs, shingling и simhash. Хотелось бы мне больше помочь.

Answer 3

Не используйте люцен. Или солр. Внутренние модели устарели и выложены булыжником; хотя они делают хорошую работу. Найти движок с минимальными критериями (если вы хотите отобразить внутри текстового движка) BM25F полностью поддерживается. Если бы мне было нужно, и я хотел бы сообщества по масштабируемости, производительности и низкой стоимости поддержки, честно говоря, я бы пошел с SQL Server и кубами. Лицензирование с SQL Server могло бы стать полной блокировкой. Удачи.