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

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

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

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

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

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

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

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

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

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

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

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