Как организовать алгоритм поиска по массиву ключевых слов?
Нужно создать сопоставление в логике поиска, чтобы, когда пользователь делает определенный запрос, мы сопоставляли его с нашими данными с этим сопоставлением.
Пример сопоставления:
Джон эквивалентен Джонатану
Ронни эквивалентен Рональду.
Также имена и фамилия при поиске возможно находить их как синонимы.
То есть тут не совсем поиск только по слогам, тут вдобавок еще и синонимы.
Имеется таблица Owners с first_name last_name полями.
runapa, нет ту данные могут быть разными, то есть сама реализация без ручного указания, то есть и чтобы синонимы как то понимал алгоритм и соответственно выводил найденные имена или фамилии с синонимами
mayton2019, Джон и Джонатану, Левенштейн по ним даст различие 5, т.е. по нему это абсолютно разные вещи.
Триграмный поиск упрется в тоже самое.
Фонетический анализ тоже мало чем поможет, разве что в варианте Джон и Джонатану, и то, только за счет совпадения начал слов.
Здесь только словарь и никак иначе, это реально разные слова.
mayton2019, а ложно-положительные срабатывания? Если я задам порог чувтствительности 5, то Левенштейн и Бронштейн будут одним и тем же. Если брать относительную чувствительность, т.е. поделить на кол-во букв в слове, то
Джон отличается от Джонатану на 125%
Джонатану от Джон на 55%
Левенштейн от Бронштейн на 55%
Vitsliputsli, в целом вы права. Но мы сейчас с вами заняты придумыванием технического задания.
Реальное задание может быть проще. Оно может иметь зазор погрешности. Оно может быть толерантно
к ложно-положительным срабатываниям. Вообще если речь идет о пользовательской системе подсказок
при поисковых операциях - то пользователь будет толерантен к выводу лже-позитивных срабатываний
при условии что в drop-down он все равно находит нужное.
Inajaf, готового нет, так как все зависит от задачи. Выше описано несколько алгоритмов и они будут давать разный результат. Если выберите расстояние Левенштейна, то учтите, что при сравнении придется накладывать эту функцию на каждую пару сравниваемое-образец. Т.е. это фулскан таблицы словаря, в зависимости от размера словаря и необходимой скорости ответа может и не подойти. Как вариант дерево Буркхарда-Келлера, но оно эффективно при получении одного ответа, при желании получить несколько, скорость работы будет деградировать очень сильно.
Примерно также с трехграмным поиском.
Фонетический анализ проще, мы в словаре можем хранить сформированный код и поиск будет по нему, здесь уже будут работать индексы и скорость будет высокой. Проблема здесь в том, что различные функции могут дать разные и очень неожиданные результаты. И дело не только в том, что они захватят лишнее, они могут не выдать очень похожие результаты.
Что касается синонимов в словаре, то группируете их (какое-нибудь поле group_id) и при совпадении одного слова выводите все слова группы.
Все очень зависит от ваших требований, быть может будет достаточно сравнения по расстоянию Левенштейна с определенным порогом чувствительности, как написал mayton2019.
Inajaf, PHP - слой вам здесь не подходит потому-что нужен очень быстрый поиск по таблице. Поэтому вам нужны поисковые функции текста на стороне MySQL. Я не специалист в MySQL и не знаю какие модули или расширения нужно поставить чтобы получить функцию левенштейна. Но на стаковер я находил ее исходники в языках stored procedures для MySQL. Какие брать? Левенштейн. Soundex. Methaphone. Триграммный поиск. Биграммный. И еще бесконечное количество текстовых функций.
Берите их последовательно. Пробуйте. Какая-то подойдет к вашей задаче насктолько что будет достаточно. По Soundex/Metaphone можно строить индекс. Это ускоряет поиск.
Простой