Итак, я понимаю, что это охватывает широкий спектр тем, и их части были рассмотрены ранее в StackOverflow, например, этот вопрос . Точно так же, Частичное совпадение строк и Приблизительное совпадение строк , похоже, являются популярными алгоритмическими обсуждениями. Однако использование этих идей совместно для решения проблем, в которых необходимо обсудить обе эти проблемы, представляется крайне неэффективным. Я ищу способ эффективно объединить две проблемы в одно решение.
Сейчас я использую AppEngine с Java и Persistent DataStore. Это несколько раздражает, так как кажется, что в запросах нет никакого арифметического использования, чтобы упростить задачу, поэтому я в настоящее время рассматриваю возможность сделать некоторый предварительный расчет и сохранить его как дополнительное поле в базе данных. По сути, это идея, которая возникла у нас с другом о том, как, возможно, реализовать систему сопоставления, и я более или менее надеялся на предложения о том, как сделать ее более эффективной. Если это нужно отменить в пользу чего-то лучшего, что уже существует, я тоже могу с этим справиться.
Начнем с базового примера того, что я хотел бы найти для поиска. Рассмотрим следующее бессмысленное предложение:
Изолирующий слой ржет принципала под вашим лицемерным мусором.
Если пользователь выполняет поиск по
isalatig pri
Я бы подумал, что это будет довольно хорошее начальное совпадение для строки, и значение должно быть возвращено. Текущий метод, который мы рассматриваем, в основном присваивает значение для проверки делимости. По сути, есть таблица со следующими данными
A: 2 B: 3 C: 5
D: 7 E: 11 F: 13
...
с отображением каждого символа в простое число (несколько символов не имеют значения, необходим только один символ). И если строка запроса делит строку в базе данных, то значение возвращается как возможное совпадение.
После этого ключевые слова, которые не указаны в качестве стоп-слов, сравниваются из строки поиска, чтобы определить, являются ли они начальными подстроками слов в возможном совпадении под заданным порогом расстояния редактирования (в настоящее время используется расстояние Левенштейна).
distance("isalatig", "isolating") == 2
distance("pri", "principal") == 0 // since principal has a starting
// substring of pri it passes
Общее расстояние для каждого запроса затем ранжируется в порядке возрастания, а верхние значения n затем возвращаются человеку, выполняющему запрос.
Это основная идея алгоритма, хотя, поскольку я впервые имею дело с таким сценарием, я понимаю, что, возможно, упускаю что-то очень важное (или вся моя идея может быть ошибочной). Каков наилучший способ справиться с текущей ситуацией, которую я пытаюсь реализовать. Точно так же, если есть какие-либо утилиты, которые AppEngine в настоящее время предлагает для борьбы с тем, что я пытаюсь сделать, пожалуйста, дайте мне знать.