Comments 10
Алгоритмы Левенштейна (как с, так и без Дамерау) и Оливера чувствительны к перестановке слов.
Каковы будут успехи, если задать в качестве поиска строку «Новгород Великий» или «Корея Южная»?
Каковы будут успехи, если задать в качестве поиска строку «Новгород Великий» или «Корея Южная»?
Эта статья — лишь отправная точка в алгоритмах нечёткого поиска, где был рассмотрен частный случай и его простая реализация средствами PHP и MySQL. В случае перестановки слов можно предложить разбитие строки на слова (по пробелам) и дальнейший поиск каждого слова по отдельности; а в словаре все названия, состоящие из нескольких слов, также разбить на отдельные слова. Таким образом, «Нижний Новгород», «Нижний», и «Новгород» в словаре будут указывать на один и тот же id, и далее необходимо будет сопоставлять найденные id. К примеру, там, где «Нижний» в словаре будет указывать на «Нижний Тагил», впоследствии не укажет на «Нижний Новгород» при поиске «Новгород Нижний», поскольку у первого «Нижнего» будет другой id.
На счёт транспозиции — я встречал определение, что транспозиция без возможности выполнения дальнейших действий. Хотя, по мне логичнее, что без выполнения других действий, иначе в некоторых случаях оно получится переоценённым:
Но иногда полезно оперировать другими категориями, чем символы (пример выше), использовать частные случаи замены, весовые коэффициенты и т. п…
Но иногда полезно оперировать другими категориями, чем символы (пример выше), использовать частные случаи замены, весовые коэффициенты и т. п…
все это будет в сотни раз медленнее существующих решений и в продакшн не годится
Хорошая ли это идея создавать массивы $from и $to при каждом вызове функции mtphn($s)? В масштабах поставленной задачи, это, конечно, копейки… или нет?
Это решение крайне неэффективно, даже если использовать реализацию пользовательской функции на Си.
В промышленных системах, имеющих поддержку нечёткого поиска, используется автомат Левенштейна (например, поисковые движки на базе Lucene). Он для заданного наперёд расстояния Левенштейна выдаёт результат «истина» или «ложь». Его прелесть в том, что функция сложности этого алгоритма линейная, то есть, упрощённо, он близок по скорости к обычному линейному поиску по набору данных.
В промышленных системах, имеющих поддержку нечёткого поиска, используется автомат Левенштейна (например, поисковые движки на базе Lucene). Он для заданного наперёд расстояния Левенштейна выдаёт результат «истина» или «ложь». Его прелесть в том, что функция сложности этого алгоритма линейная, то есть, упрощённо, он близок по скорости к обычному линейному поиску по набору данных.
Круто! Спасибо!
Sign up to leave a comment.
Расстояние Левенштейна в MySQL и алгоритмы нечёткого поиска средствами PHP