В настоящее время я работаю над реализацией нечеткого поиска для веб-службы терминологии и ищу предложения о том, как улучшить текущую реализацию. Это слишком большой код, чтобы поделиться им, но я думаю, что объяснения может быть достаточно, чтобы предложить вдумчивые предложения. Я понимаю, что это много читать, но я был бы признателен за любую помощь.
Во-первых, терминология - это всего лишь несколько имен (или терминов). Для каждого слова мы разделяем его на токены по пробелам, а затем перебираем каждый символ, чтобы добавить его в три. На терминальном узле (например, когда достигается символ y в клубнике) мы сохраняем в списке индекс для основного списка терминов. Таким образом, конечный узел может иметь несколько индексов (поскольку конечный узел для клубники будет соответствовать «клубника» и «аллергия на клубнику»).
Что касается фактического поиска, то поисковый запрос также разбивается на токены по пробелам. Алгоритм поиска запускается для каждого токена. Первым символом поискового токена должно быть совпадение (поэтому траул никогда не совпадет с клубникой). После этого мы проходим дочерние элементы каждого последующего узла. Если есть дочерний элемент с совпадающим символом, мы продолжаем поиск со следующего символа токена поиска. Если дочерний элемент не соответствует данному символу, мы смотрим на дочерних элементов, используя текущий символ маркера поиска (поэтому не продвигаем его). Это часть нечеткости, поэтому «stwb» будет соответствовать «клубничке».
Когда мы дойдем до конца поискового токена, мы проведем поиск по оставшейся части структуры trie в этом узле, чтобы получить все потенциальные совпадения (поскольку индексы для основного списка терминов находятся только на терминальных узлах). Мы называем это сверткой. Мы храним индексы, устанавливая их значение в BitSet. Затем мы просто и BitSets из результатов каждого результата поиска токена. Затем мы берем, скажем, первые 1000 или 5000 индексов из анодированных битовых наборов и находим фактические термины, которым они соответствуют. Мы используем Левенштейна для оценки каждого термина, а затем сортируем по баллам, чтобы получить окончательные результаты.
Это работает довольно хорошо и довольно быстро. В дереве более 390 тыс. Узлов и более 1,1 млн. Имен реальных терминов. Тем не менее, есть проблемы с этим в его нынешнем виде.
Например, поиск 'car cat' вернет катетеризацию, когда мы этого не хотим (поскольку поисковый запрос состоит из двух слов, результат должен быть не менее двух). Это было бы достаточно легко проверить, но это не относится к ситуации, подобной процедуре катетеризации, поскольку это два слова. В идеале, мы бы хотели, чтобы это соответствовало чему-то вроде сердечной катетеризации.
Исходя из необходимости исправить это, мы предложили некоторые изменения. С одной стороны, мы проходим через три в смешанном поиске глубины / ширины. По сути, мы углубляемся до тех пор, пока персонаж совпадает. Те дочерние узлы, которые не совпадают, добавляются в очередь с приоритетами. Очередь приоритетов упорядочена по расстоянию редактирования, которое можно рассчитать при поиске дерева (поскольку при совпадении символов расстояние остается неизменным, а если нет, оно увеличивается на 1). Делая это, мы получаем расстояние редактирования для каждого слова.
Мы больше не используем BitSet. Вместо этого это карта индекса для объекта Terminfo. Этот объект хранит индекс фразы запроса, термин фразы и оценку. Таким образом, если поиск - «автомобильная кошка», а соответствующий термин - «процедура катетеризации», индексы фраз будут равны 1, как и индексы фраз запроса. Для «сердечной катетеризации» термины индексы фраз будут равны 1,2, как и индексы фраз запроса. Как вы можете видеть, впоследствии очень просто взглянуть на количество индексов терминов и индексов фраз запроса, и если они по крайней мере не равны количеству поисковых слов, их можно отбросить.
После этого мы складываем расстояния редактирования слов, удаляем слова из термина, которые соответствуют индексу фразы термина, и подсчитываем оставшиеся буквы, чтобы получить истинное расстояние редактирования. Например, если вы соответствовали термину «аллергия на клубнику», а ваш поисковый запрос был «солома», у вас было бы 7 баллов по клубнике, то вы бы использовали термин «индекс фразы», чтобы отбросить клубнику из этого термина, и просто сосчитать «аллергия на» (минус пробелы), чтобы получить оценку 16.
Это дает нам точные результаты, которые мы ожидаем. Тем не менее, это слишком медленно. Если раньше мы могли получить 25-40 мс при поиске по одному слову, то теперь это могло быть целых полсекунды. Это в значительной степени связано с такими вещами, как создание экземпляров объектов TermInfo, использование операций .add (), операций .put () и тот факт, что мы должны возвращать большое количество совпадений. Мы могли бы ограничить каждый поиск только 1000 совпадений, но нет гарантии, что первые 1000 результатов для "автомобиля" будут соответствовать любому из первых 1000 совпадений для "кошки" (помните, что существует более 1,1 миллиона терминов).
Даже для одного слова запроса, такого как cat, нам все еще нужно большое количество совпадений. Это потому, что если мы ищем 'cat', поиск будет соответствовать машине и свернет все терминальные узлы под ней (что будет много). Однако, если мы ограничим количество результатов, это будет делать слишком сильный акцент на словах, начинающихся с запроса, а не на расстоянии редактирования. Таким образом, такие слова, как катетеризация, будут включены с большей вероятностью, чем что-то вроде пальто.
Так, в принципе, есть какие-нибудь мысли о том, как мы могли бы справиться с проблемами, которые исправила вторая реализация, но без такой большой скорости, которую она представила? Я могу включить некоторый выбранный код, если он может прояснить ситуацию, но я не хотел размещать гигантскую стену кода.