Метафон против Левенштейна против Соундекса против Хемминга
Я хочу реализовать Fuzzy Search используя php 7 и MySQL 5.7. Я сделал несколько поисков в Google и обнаружил, что эти алгоритмы используются для этой цели: Metaphone, Levenshtein, Soundex и Hamming.
я бы хотел search for song titles в моем столе. Таким образом, пользователь может искать, используя название, имена художников или оба с орфографической ошибкой также, как YouTube для бывших.
Какой алгоритм лучше всего использовать для этой цели и как его можно реализовать в php / MySQL?
Решение
SOUNDEX () — это простой алгоритм начала двадцатого века, настроенный для поиска собственных имен в американском английском. Он был создан для операторов справочной системы Bell System. Он предназначен для генерации множества ложных срабатываний, из которых человек может выбрать вероятные попадания. Это, вероятно, не подходит для ваших целей, потому что ваши слова в основном не являются собственными именами.
Метафон и двойной метафон являются улучшением на SOUNDEX. Они работают над более широким разнообразием слов.
Они работают лучше по словам, а не по фразам, таким как названия песен. Если вы реализуете что-то из этого, вам нужно реализовать пословное сопоставление и какую-то схему подсчета очков. Хорошая новость заключается в том, что они подходят для индексации и работают на основе звуков слов.
Расстояние Левенштейна воздействует на слова или фразы, и работает на правописание, а не на звуки. Он не подходит для индексированного поиска, потому что эти расстояния работают в паре. По моему опыту, сложно оценить расстояния Левенштейна, потому что у более длинных фраз гораздо больше способов отличаться от других длинных фраз, чем у коротких.
Прежде чем вы попытаетесь построить нечеткий поиск с использованием этих необработанных алгоритмов, вы можете попробовать поиск MySQL FULLTEXT и Sphinx. Обе эти технологии хорошо справляются с оценкой фраз и прилично останавливают слова. Sphinx также имеет некоторую поддержку для таблиц синонимов, которая помогает справиться с обычной ошибкой.
Другие решения
Других решений пока нет …