MySQL поиск по релевантности (нечеткие, синонимы)

Question

Я создаю небольшое словарное приложение, которое требует от пользователя ввода слова (на любом из двух языков) и отображения наиболее релевантных результатов (из 10 или более). Мой клиент хочет, чтобы это объясняло орфографические ошибки, поэтому я использую формулу расстояния Дамерау-Левенштейна. В качестве примера приведен фрагмент того, что должно делать приложение:

MySQL fields - Term1 -> Value1 | Term2 -> Value2
Implementation - English Term -> English Value | German Term -> German Value
----------

forge -> to forge your parent's signature | fälschen -> die unterschrift de eltern fälschen
    Synonyms: fake, imitation, etc,
fake -> to fake your parent's signature | fälschen -> die unterschrift de eltern fälschen
    Synonyms: forge, imitation, etc,
black out -> to black out a classroom (with blinds) | verdunkeln -> (einen klassenraum) verdunkeln

Поскольку fake и forge похожи, я хочу, чтобы результаты поиска для forge (или foreg и т. Д.) Возвращали оба. У меня сейчас работает грубая реализация, которая просматривает каждую строку большой базы данных, но это долгий процесс, и мне нужна лучшая система.

В качестве дополнительной информации я использую тезаурус Moby для поиска синонимов каждого возвращаемого слова. Чтобы сократить объемные синонимы (так как в массив помещается около 20 результатов), я, вероятно, отброшу записи, которые не найдены в базе данных.

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

Большое спасибо!

Answer 1

Расстояние Дамерау-Левенштейна - это алгоритм, который невозможно оптимизировать с помощью предварительно вычисленного индекса. Таким образом, у вас возникнут проблемы с его ускорением в контексте СУБД. (Есть некоторые приемы, которые позволяют сравнивать одно слово с лексически организованным словарем, но они довольно экзотичны).

Однако, если вы можете извлечь подмножество содержимого таблицы тезауруса, и ТОГДА использовать алгоритм расстояний, вы можете выиграть.

Для первого шага попробуйте SOUNDEX (неаккуратный и очень дешевый алгоритм сопоставления звука), встроенный в mySQL. Или, если это приводит к слишком широкой сети, вы можете посмотреть алгоритм Metaphone или Double Metaphone.

Затем для второго шага сделайте то, что вы уже делаете с алгоритмом расстояния.

Проверьте этот вопрос и несколько ответов. Как сделать нечеткое совпадение названий компаний в MYSQL с PHP для автозаполнения?