Метафон против Левенштейна против Soundex против Hamming

Question

Я хочу реализовать Fuzzy Search с использованием php 7 и MySQL 5.7. Я сделал несколько поисков в Google, и я нашел, что эти алгоритмы используются для этой цели: Metaphone, Levenshtein, Soundex и Hamming.

Я хочу search for song titles в моем столе. Таким образом, пользователь может искать названия, имена артистов или их обоих с ошибкой, также как и YouTube для ex.

Каков наилучший алгоритм, используемый для этой цели, и как может быть реализована в PHP/MySQL

Answer 1

SOUNDEX() представляет собой простой алгоритм с началом двадцатого века, настроенным, чтобы помочь искать собственные имена в американском английском. Он был создан для операторов справочной службы Bell System. Он предназначен для создания множества ложных срабатываний, из которых человек может выбрать вероятные удары. Это, вероятно, непригодно для вашей цели, потому что ваши слова не являются в основном собственными именами.

Метафон и двойной метафон являются уточнениями на SOUNDEX. Они работают на более широком спектре слов.

Они работают лучше всего по слову, а не по фразам, таким как названия песен. Если вы реализуете какие-либо из них, вам нужно будет внедрить словосочетание и какую-то схему подсчета. Хорошей новостью является то, что они подходят для индексирования и работают на основе звуков слов.

Levenshtein distance работает над словами или фразами и работает над написанием, а не звуками. Это не подходит для индексированного поиска, потому что эти расстояния работают по-разному. По моему опыту сложно оценивать расстояния Левенштейна, потому что более длинные фразы имеют гораздо больше способов отличаться от других длинных фраз, чем короткие.

Прежде чем вы погрузитесь в попытку построить нечеткий поиск, используя эти необработанные алгоритмы, вы можете попробовать MySQL FULLTEXT search и Sphinx. Обе эти технологии отлично справляются с фразовыми записями и останавливают слова. Sphinx также имеет некоторый suppport для таблиц синонимов, который помогает обрабатывать распространенную орфографическую ошибку.