Советы по улучшению текущей реализации нечеткого поиска

Question

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

Во-первых, терминология - это в основном просто несколько имен (или терминов). Для каждого слова мы разбиваем его на токены по пробелу, а затем повторяем каждый символ, чтобы добавить его в trie. На терминальном узле (например, когда символ y в клубнике достигнут), мы сохраняем в списке индекс в список основных терминов. Таким образом, терминальный узел может иметь несколько индексов (поскольку терминальный узел для клубники будет соответствовать «клубнике» и «аллергии на клубнику»).

Что касается фактического поиска, поисковый запрос также разбивается на токены по пространству. Алгоритм поиска запускается для каждого токена. Первым символом маркера поиска должно быть совпадение (поэтому травер никогда не будет соответствовать клубнике). После этого мы проходим через детей каждого последующего узла. Если есть дочерний элемент с символом, который соответствует, мы продолжаем поиск со следующим символом маркера поиска. Если дочерний элемент не соответствует указанному символу, мы смотрим на детей, используя текущий символ маркера поиска (чтобы не продвигать его). Это нечеткая часть, поэтому «stwb» будет соответствовать «клубнике».

Когда мы дойдем до конца токена поиска, мы проведем поиск по остальной структуре trie на этом узле, чтобы получить все потенциальные совпадения (так как индексы к списку основных терминов относятся только к терминальным узлам). Мы называем это сверткой. Мы сохраняем индексы, устанавливая их значение на BitSet. Затем мы просто и BitSets получаем результаты каждого результата токена поиска. Затем мы берем, скажем, первые 1000 или 5000 индексов из битовых наборов и находим фактические условия, которым они соответствуют. Мы используем Levenshtein для оценки каждого термина, а затем сортируем по результату, чтобы получить наши окончательные результаты.

Это работает довольно хорошо и довольно быстро. В дереве содержится более 390 тыс. Узлов и более 1,1 млн. Имен реальных терминов. Однако есть проблемы с этим, поскольку он стоит.

Например, поиск «car cat» вернет катетеризацию, когда мы этого не хотим (так как поисковый запрос состоит из двух слов, результат должен быть не менее двух). Это было бы достаточно легко проверить, но он не позаботится о такой ситуации, как процедура катетеризации, поскольку это два слова. В идеальном случае мы хотели бы, чтобы он соответствовал чему-то вроде сердечной катетеризации.

Основываясь на необходимости исправить это, мы придумали некоторые изменения. Во-первых, мы проходим через три в смешанном поиске глубины/ширины. По сути, мы начинаем глубже, пока символ совпадает. Те дочерние узлы, которые не совпадают, добавляются в очередь приоритетов. Очередь приоритетов упорядочивается по расстоянию редактирования, которое можно вычислить при поиске trie (поскольку, если есть совпадение символов, расстояние остается неизменным, а если нет, оно увеличивается на 1). Делая это, мы получаем расстояние редактирования для каждого слова. Мы больше не используем BitSet. Вместо этого это карта индекса для объекта Terminfo. Этот объект хранит индекс фразы запроса, а также термин фраза и оценка. Поэтому, если поиск - «автомобиль-кот», а термин «процедура катетеризации», индексы фразы будут равны 1, как и индексы фразы запроса. Для «сердечной катетеризации» индексы фразы будут равны 1,2, как и индексы фразы запроса. Как вы можете видеть, после этого очень просто посмотреть на подсчет индексов фразы и индексов фразы запросов, и если они не равны, по крайней мере, количеству слов в поисковом слове, они могут быть отброшены.

После этого мы добавляем отредактированные расстояния слов, удаляем слова из термина, соответствующие термину фраза фразы, и подсчитываем оставшиеся буквы, чтобы получить истинное расстояние редактирования.Например, если вы соответствовали термину «аллергия на клубнику», и ваш поисковый запрос был «соломой», у вас было бы 7 баллов из клубники, тогда вы использовали бы термин фраза «индекс», чтобы отбросить клубнику от этого термина и просто посчитать «аллергия на» (минус пробелы), чтобы получить оценку 16.

Это дает нам точные результаты, которые мы ожидаем. Однако это слишком медленно. Где раньше мы могли получить 25-40 мс при поиске по одному слову, теперь это может быть ровно полсекунды. Это в значительной степени от таких вещей, как создание экземпляров объектов TermInfo, использование операций .add(), операций()() и факт, что мы должны вернуть большое количество совпадений. Мы можем ограничить каждый поиск только возвращением 1000 матчей, но нет никакой гарантии, что первые 1000 результатов для «автомобиля» будут соответствовать любому из первых 1000 матчей для «кошки» (помните, что их насчитывается более 1,1 миллиона).

Даже для одного слова запроса, такого как кошка, нам по-прежнему нужно большое количество совпадений. Это связано с тем, что если мы ищем «кот», поиск будет соответствовать автомобилю и сворачивать все терминальные узлы под ним (что будет много). Однако, если мы ограничили количество результатов, это сделало бы слишком тяжелым акцент на словах, которые начинаются с запроса, а не расстояния редактирования. Таким образом, слова, подобные катетеризации, скорее всего будут включены, чем что-то вроде пальто.

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

Answer 1

Wow ... жесткий один.

Хорошо, почему вы не внедряете lucene? Это лучший и современный уровень техники, когда дело доходит до таких проблем, как ваш афайк.

Однако я хочу поделиться некоторыми мыслями ...

Fuziness - это не что-то вроде соломы *, это скорее неправильное написание некоторых слов. И каждый недостающий/неправильный символ добавляет 1 к расстоянию.

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

Tokenizing, как правило, хорошая идея.

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

Я видел несколько хороших реализаций с использованием многомерных деревьев.

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

Вы можете использовать семантическую базу данных, такую ​​как кунжут, и при импорте документов импортировать каждый токен и документ в качестве узла. Затем, в зависимости от позиции в документе и т. Д., Вы можете добавить взвешенное отношение.

Тогда вам нужны жетоны в некоторой структуре, где вы можете делать эффективные нечеткие совпадения, такие как bk-деревья. Я думаю, что вы могли бы индексировать маркеры в базе данных mysql и выполнять бит-мутные функции сравнения, чтобы получить различия. Theres - функция, которая возвращает все соответствующие биты, если вы переводите свои строки в ascii и группируете биты, которые вы могли бы достичь довольно быстро.

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

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

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

Вы также можете проиндексировать все слово или различные конкатенации токенов.

Однако могут быть специальные реализации bk-tree, которые поддерживают это, но я его никогда не видел.

Answer 2

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

(в сторону: Вы будете удивлены, как много способов, врачи могут попытаться записать «ацетилсалициловая кислота».)

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

ОТНОСИТЕЛЬНО всего этого, у вас есть проблема с производительностью. Самое приятное в проблемах с производительностью - чем они хуже, тем легче их найти. Я был настоящим вредителем в StackOverflow, указывая на это. This link объясняет, как это сделать, ссылки на подробный пример и пытается развеять некоторые популярные мифы. В двух словах, чем больше времени тратится на то, что вы можете оптимизировать, тем более вероятно, что вы поймете, что это сделает, если вы просто приостановите его и посмотрите. Мое подозрение в том, что много времени идет на операции над раздутой структурой данных, а не просто на получение ответа. Это обычная ситуация, но ничего не исправить, пока образцы не указывают на проблему.