Как искать текстовые фрагменты в базе данных

Question

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

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

РЕДАКТИРОВАТЬ : [Добавлено, чтобы прояснить, почему эти первые предложения не решат проблему:]

Вот почему встроенный в MySQL полнотекстовый индекс не справится с работой, равно как и Lucene или Sphinx, и все они были предложены в ответах. Я уже рассматривал оба из них, но, насколько я могу судить, они основаны на индексации слов , исключая стоп-слова и делая все возможное для реального полнотекстового поиска. Однако это не подходит, потому что я мог бы искать поисковый термин, такой как «oison», который должен соответствовать «Roisonic Street», а также «Poison-Ivy». Ключевым отличием здесь является то, что поисковый термин - это просто фрагмент содержимого столбца , который не должен быть ограничен какими-либо специальными символами или пробелами.

EDIT2 : [Добавлена ​​дополнительная справочная информация:] Запрашиваемая функция, которая должна быть реализована на основе этого, является очень свободным поиском описаний товаров в системе управления товарами. Пользователи часто не знают правильный номер элемента, а только часть названия элемента. К сожалению, качество этих описаний довольно низкое, они происходят из устаревшей системы и не могут быть легко изменены. Если, например, люди искали кувалду, они входили в «сани». С индексом на основе слова / токена это не будет находить совпадения, которые хранятся как «кувалда», а только те, которые слушают «кувалду». Есть все виды странных отклонений, которые должны быть покрыты, делая подход на основе токенов нецелесообразным.

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

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

Если возможно, индекс должен быть обновляемым (без необходимости полного перестроения), поскольку данные могут измениться и должны быть доступны для поиска немедленно другими клиентами.

Я был бы рад получить рекомендации и / или отчеты об опыте.

EDIT3: Коммерческое решение показало, что "просто работает" Несмотря на то, что я получил много хороших ответов на этот вопрос, я хотел отметить здесь, что в итоге мы пошли с коммерческим продуктом под названием «QuickFind», изготовленным и проданным немецкой компанией под названием «HMB Datentechnik». Обратите внимание, что я не связан с ними каким-либо образом, потому что это может выглядеть так, когда я продолжаю и описываю, что может делать их продукт. К сожалению, их веб-сайт выглядит довольно плохо и только на немецком языке, но сам продукт действительно великолепен. В настоящее время у меня есть пробная версия от них - вам придется связаться с ними, без загрузки - и я очень впечатлен.

Поскольку в Интернете нет исчерпывающей документации, я пока попытаюсь описать свой опыт.

Они создают собственный индексный файл на основе содержимого базы данных. Они могут интегрироваться через ODBC, но, как мне сказали, клиенты редко делают это. Вместо этого - и это то, что мы, вероятно, будем делать - вы генерируете текстовый экспорт (например, CSV) из своей основной базы данных и передаете его в свой индексатор. Это позволяет вам быть полностью независимым от фактической структуры таблицы (или вообще от любой базы данных SQL); фактически мы экспортируем данные, объединенные из нескольких таблиц. Индексы могут постепенно обновляться позже на лету.

Исходя из того, что их сервер (всего 250 КБ или более, работающий как консольное приложение или служба Windows) обслуживает запросы на порт TCP. Протокол основан на тексте и выглядит немного «старым», но он прост и работает. В основном вы просто передаете, какой из доступных индексов вы хотите запросить, а также условия поиска (фрагменты), разделенные пробелом. Доступны три формата вывода: массив HTML / JavaScript, XML или CSV. В настоящее время я работаю над оболочкой Java для несколько устаревшего проводного протокола. Но результаты потрясающие: в настоящее время у меня есть примерный набор данных приблизительно из 500 000 записей с индексированными 8 столбцами, и мое тестовое приложение запускает поиск по всем 8 столбцам содержимого JTextField при каждом нажатии клавиши во время редактирования. и может обновлять отображение результатов (JTable) в режиме реального времени! Это происходит без обращения к экземпляру MySQL, откуда изначально были получены данные. Основываясь на возвращаемых вами столбцах, вы можете запросить «оригинальную» запись, запросив MySQL с первичным ключом этой строки (конечно, должен быть включен в индекс QuickFind).

Индекс составляет около 30-40% размера текстовой версии экспорта данных. Индексирование в основном зависело от скорости дискового ввода-вывода; мои 500.000 записей заняли около минуты или двух для обработки.

Трудно описать это, поскольку мне было даже трудно поверить, когда я увидел демо-версию собственного продукта. Они представили базу данных с адресами в 10 миллионов строк и искали фрагменты имен, адресов и телефонных номеров, и при нажатии кнопки «Поиск» результаты возвращались менее чем за секунду - и все это делалось на ноутбуке! Из того, что мне сказали, они часто интегрируются с системами SAP или CRM для улучшения времени поиска, когда агенты колл-центра просто понимают фрагменты имен или адресов вызывающего абонента.

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

Answer 1

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

Если вы работали в магазине Microsoft, большая часть того, что вы ищете, встроена в SQL Server, и можно включить подстановочные знаки, что даст вам возможность выполнять частичные совпадения слов.

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

Очевидно, что вы можете изменить экземпляр Query Parser в Lucene, чтобы переопределить это правило, установив для setAllowLeadingWildcard значение true.

Я вполне уверен, что поиск с подстановочными знаками на обоих концах слова по своей сути неэффективен. Списки пропуска иногда используются для повышения производительности при таких поисках с открытым текстом, но я думаю, что вы, скорее всего, найдете такую ​​реализацию в чем-то вроде grep, чем в обобщенном инструменте индексирования текста.

Существуют и другие способы решения описанной вами проблемы, когда одно слово может встречаться, записанное как два, или наоборот. Нечеткие запросы поддерживаются в Lucene, например. Ортогональные и морфологические варианты могут быть обработаны с использованием либо фильтра, предлагающего предложения, основанные на каком-либо байесовском механизме, либо путем индексации трюков, а именно, взятия совокупности частых вариантов и наполнения индекса этими терминами. Я даже видел знания из структурированных данных, вставленных в полнотекстовый движок (например, добавление названия города и слова «hotel» в записи из таблицы отелей, чтобы повысить вероятность того, что «Paris Hotels» будет включать запись для пенсии). Дом Caisse des Dépôts. Хотя это не совсем тривиальная проблема, она решается без ущерба для преимуществ поиска по словам.

Answer 2

У меня не было этого особого требования, но мой опыт подсказывает, что Lucene может справиться с задачей, хотя, возможно, и не самостоятельно. Я определенно использовал бы это через Solr, как описано Майклом Делла Биттой в первом ответе. Ссылка, которую он дал, была точной - прочитайте ее для получения дополнительной информации.

Вкратце, Solr позволяет вам определять собственные FieldTypes. Они состоят из анализатора времени индекса и анализатора времени запроса. Анализаторы выясняют, что делать с текстом, и каждый состоит из Tokenizer и от нуля до множества TokenFilters. Tokenizer разбивает ваш текст на куски, а затем каждый TokenFilter может добавлять, вычитать или изменять токены.

Таким образом, поле может в конечном итоге индексировать нечто совершенно отличное от исходного текста, включая несколько токенов, если это необходимо. Итак, вам нужна копия оригинального текста с несколькими токенами, которую вы запрашиваете, отправляя Lucene что-то вроде «my_ngram_field: sledge». Подстановочные знаки не используются: -)

Затем вы следуете модели, аналогичной поиску префиксов, предложенному в файле solrconfig.xml:

<fieldType name="prefix_token" class="solr.TextField" positionIncrementGap="1">
    <analyzer type="index">
        <tokenizer class="solr.WhitespaceTokenizerFactory"/>
        <filter class="solr.LowerCaseFilterFactory" />
        <filter class="solr.EdgeNGramFilterFactory" minGramSize="1" maxGramSize="20"/>
    </analyzer>
    <analyzer type="query">
        <tokenizer class="solr.WhitespaceTokenizerFactory"/>
        <filter class="solr.LowerCaseFilterFactory" />
    </analyzer>
</fieldType>

EdgeNGramFilterFactory - это способ реализации сопоставления префиксов для автозаполнения окна поиска. Он берет токены, полученные на предыдущих этапах (отдельные слова, разделенные пробелами, преобразуются в нижний регистр) и выводит их в каждую подстроку на переднем крае. кувалда = s, sl, sle, сани, санки, сани, санки и т. д.

Вы должны следовать этому шаблону, но замените EdgeNGramFilterFactory своим собственным, который выполняет все NGrams в поле. По умолчанию org.apache.solr.analysis.NGramFilterFactory - хорошее начало, но оно выполняет транспонирование букв для проверки орфографии. Вы можете скопировать его и удалить его - это довольно простой для реализации класс.

Как только вы получите свой собственный FieldType (назовите его ngram_text), используя свой собственный MyNGramFilterFactory, просто создайте свое оригинальное поле и поле ngram следующим образом:

    <field name="title" type="text" indexed="true" stored="true"/>
    <field name="title_ngrams" type="ngram_text" indexed="true" stored="false"/>

Затем скажите ему скопировать оригинальное поле в необычное:

<copyField source="title" dest="title_ngrams"/>

Хорошо, теперь, когда вы ищете "title_ngrams: sledge", вы должны получить список документов, которые содержат это. Затем в списке полей для запроса вы просто указываете ему получить поле с названием title, а не поле title_ngrams.

Этого должно быть достаточно, чтобы позволить вам совместить вещи и довольно легко настроить их на удивительные уровни производительности. На старой работе у нас была база данных с более чем десятью миллионами продуктов с большими описаниями HTML, и нам удалось заставить Lucene выполнить стандартный запрос и проверку орфографии менее чем за 200 мс на сервере среднего размера, обрабатывающем несколько десятков одновременных запросов. Когда у вас много пользователей, кеширование включается и заставляет его кричать!

Да, и инкрементное (хотя и не в реальном времени) индексирование является подпоркой. Он может делать это даже при высоких нагрузках, поскольку создает и оптимизирует новый индекс в фоновом режиме и автоматически согревает его перед заменой. Очень гладко.

Удачи!

Answer 3

Я бы использовал Apache Solr. Стратегия индексирования является полностью настраиваемой (см. http://wiki.apache.org/solr/AnalyzersTokenizersTokenFilters),, которая может постепенно считывать данные непосредственно из вашей базы данных для заполнения индекса (см. DataImportHandler в той же вики) и может запрашиваться практически из любого языка, говорящего на HTTP и XML или чего-то подобного JSON.

Answer 4

Если ваша таблица MyISAM, вы можете использовать возможности полнотекстового поиска MySQL: http://dev.mysql.com/doc/refman/5.0/en/fulltext-search.html

Если нет, то «отраслевой стандарт» равен http://www.sphinxsearch.com/

Некоторые идеи о том, что делать, если вы используете InnoDB: http://www.mysqlperformanceblog.com/2009/09/10/what-to-do-with-mysql-full-text-search-while-migrating-to-innodb/

Кроме того, хорошая презентация, которая представляет Sphinx и объясняет архитектуру + использование http://www.scribd.com/doc/2670976/Sphinx-High-Performance-Full-Text-Search-for-MySQL-Presentation

Обновление
Прочитав ваше разъяснение к вопросу - Сфинкс может делать совпадения подстрок. Вам нужно установить «enable-star» и создать индексный инфикс с соответствующей min_infix_length (1 даст вам все возможные подстроки, но, очевидно, чем больше его значение, тем меньше будет ваш индекс и тем быстрее будет выполняться поиск). Подробнее см. http://sphinxsearch.com/docs/current.html.

Answer 5

Поиск гальки может помочь.

http://en.wikipedia.org/wiki/W-shingling

Например, если вы используете 3-символьную черепицу, вы можете разделить «Roisonic» на: «roi», «son», «ic» и сохранить все три значения, связав их с исходной записью. При поиске «oison», вы сначала будете искать «ois», «iso», «son». Сначала вы нечетко сопоставляете все записи по черепице (находя запись с «сыном»), а затем вы можете уточнить поиск, используя точное совпадение строк.

Обратите внимание, что 3-символьный гонт требует, чтобы фрагмент в запросе был длиной не менее 5 символов, 4-символьный гонт требует 7-символьный запрос и т. Д.

Answer 6

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

Answer 7

То, что вы пытаетесь сделать, вряд ли когда-либо будет намного быстрее, чем LIKE '%searchterm%' без большого количества пользовательского кода. Хотя эквивалент LIKE 'searchterm%' должен быть тривиальным. Вы можете сделать то, что вы просите, создав индекс всех возможных частичных слов, которые не охватываются конечным символом подстановки, но это приведет к невероятно большому размеру индекса и будет необычно медленным для обновлений. Длинные токены приведут к плохим вещам ™. Могу я спросить , почему вам это нужно? Re: Spotlight ... Вы понимаете, что Spotlight не делает этого, верно? Он основан на токене, как и любой другой полнотекстовый индексатор. Обычно расширение запроса - это подходящий метод получения неточных совпадений, если это ваша цель.

Edit:

В какой-то момент у меня был такой проект; номера деталей для всех видов вещей. Мы наконец остановились на searchterm* в Xapian, но я думаю, что у Lucene также есть аналог. Вы не найдете хорошего решения, которое бы выполняло поиск с подстановочными знаками по обе стороны от токена, но конечный подстановочный знак обычно более чем достаточно для того, что вы хотите, и я подозреваю, что вы обнаружите, что пользователи адаптируются к вашему система довольно быстро, если они имеют какой-либо контроль над очисткой данных. Объедините это с расширением запросов (или даже ограниченным расширением токенов), и вы должны быть достаточно хорошо настроены. Расширение запроса конвертирует запрос для «кувалды» в «кувалду * ИЛИ (кувалда * молот *)» или что-то подобное. Не каждый запрос будет работать, но люди уже достаточно хорошо подготовлены к тому, чтобы пробовать похожие запросы, когда что-то не работает, и если хотя бы один или два очевидных запроса дают ожидаемые результаты, у вас все будет в порядке. Лучше всего по-прежнему очистить данные и упорядочить их. Вы будете удивлены, насколько легко это закончится тем, что вы все измените и внедрите эгалитарную политику редактирования. Может быть, пусть люди добавляют ключевые слова к записи и обязательно их индексируют, но устанавливают ограничения на их количество. Слишком много, и вы можете фактически ухудшить результаты поиска.

Answer 8

Точный ответ на ваш вопрос прямо здесь Будет ли он достаточно хорошо работать для размера ваших данных - это другой вопрос

Answer 9

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

Вы только надеетесь, что если есть какие-то закономерности для допущенных «ошибок». Вы можете применить набор правил типа «AI» к входящему тексту и создать каноническую форму текста, которую затем можете применить к полному тексту. текстовый индекс к. Примером правила может быть разделение слова, оканчивающегося на молоток, на два слова s / (\ w?) (hammer) / \ 1 \ 2 / g или изменение слов «sledg», «sled» и «schledge». "to" sledge ". Вам нужно будет применить тот же набор правил к тексту запроса. Таким образом, продукт, описанный как" sledgehammer ", может быть сопоставлен с поиском" sledg hammer ".

Answer 10

Я почти уверен, что Mysql предлагает полнотекстовую опцию, и, вероятно, также можно использовать Lucene.

См. Здесь для связанных комментариев

Лучший эффективный способ сделать полнотекстовый поиск в MySQL