Как сделать нечеткое совпадение названий компаний в MYSQL с PHP для автозаполнения?
Мои пользователи будут импортировать через вырезать и вставить большую строку, которая будет содержать названия компаний.
У меня есть существующая и растущая база данных MYSQL с названиями компаний, каждое с уникальным идентификатором компании.
Я хочу иметь возможность анализировать строку и присваивать каждому введенному пользователем названию компании нечеткое совпадение.
Прямо сейчас, просто прямое совпадение строк, тоже медленно. ** Будет ли индексирование Soundex быстрее? Как я могу дать пользователю некоторые параметры, когда они набирают текст? **
Например, кто-то пишет:
Microsoft -> Microsoft Голые Essentials -> Голые Escentuals Polycom, Inc. -> Polycom
Я нашел следующие темы, которые кажутся похожими на этот вопрос, но постер не одобрен, и я не уверен, применим ли их вариант использования:
Как найти лучшее нечеткое соответствие для строки в большой базе данных строк
10 ответов
Вы можете начать с использования SOUNDEX() это, вероятно, подойдет для того, что вам нужно (я представляю себе окно с автоматическими предложениями уже существующих альтернатив тому, что печатает пользователь).
Недостатки SOUNDEX() являются:
- его неспособность различать более длинные строки. Учитываются только первые несколько символов, более длинные строки, которые расходятся в конце, генерируют одно и то же значение SOUNDEX.
- факт, что первая буква должна быть одинаковой, иначе совпадение не будет найдено. В SQL Server есть функция DIFFERENCE(), которая сообщает вам, на сколько два значения SOUNDEX разделены, но я думаю, что в MySQL нет ничего подобного.
- для MySQL, по крайней мере, в соответствии с документами, SOUNDEX не работает для ввода Unicode
Пример:
SELECT SOUNDEX('Microsoft')
SELECT SOUNDEX('Microsift')
SELECT SOUNDEX('Microsift Corporation')
SELECT SOUNDEX('Microsift Subsidary')
/* all of these return 'M262' */
Для более сложных задач, я думаю, вам нужно взглянуть на расстояние Левенштейна (также называемое "редактировать расстояние") двух строк и работать с порогом. Это более сложное (= более медленное) решение, но оно обеспечивает большую гибкость.
Основным недостатком является то, что вам нужны обе строки для расчета расстояния между ними. С помощью SOUNDEX вы можете сохранить предварительно рассчитанный SOUNDEX в своей таблице и сравнить / отсортировать / сгруппировать / отфильтровать. С расстоянием Левенштейна вы можете обнаружить, что разница между "Microsoft" и "Nzcrosoft" составляет всего 2, но для достижения этого результата потребуется гораздо больше времени.
В любом случае пример функции расстояния Левенштейна для MySQL можно найти по адресу codejanitor.com: Расстояние Левенштейна как хранимая функция MySQL (10 февраля 2007 г.).
SOUNDEX - хороший алгоритм для этого, но в этой области были достигнуты последние достижения. Был создан еще один алгоритм, называемый метафоном, и позднее он был пересмотрен на алгоритм двойного метафона. Я лично использовал реализацию двойного метафона в java apache commons, и он настраиваемый и точный.
У них также есть реализации на многих других языках на странице википедии. На этот вопрос ответили, но если вы обнаружите какие-либо выявленные проблемы с SOUNDEX, появляющиеся в вашем приложении, приятно знать, что есть варианты. Иногда он может генерировать один и тот же код для двух действительно разных слов. Двойной метафон был создан, чтобы помочь решить эту проблему.
Украдено из википедии: http://en.wikipedia.org/wiki/Soundex
В ответ на недостатки алгоритма Soundex Лоуренс Филипс разработал алгоритм Metaphone для той же цели. Позже Philips разработал усовершенствование Metaphone, которое он назвал Double-Metaphone. Double-Metaphone включает в себя гораздо больший набор правил кодирования, чем его предшественник, обрабатывает подмножество нелатинских символов и возвращает первичную и вторичную кодировку для учета различного произношения одного слова в английском языке.
Внизу страницы с двойным метафоном у них есть реализации для всех видов языков программирования: http://en.wikipedia.org/wiki/Double-Metaphone
Реализация Python и MySQL: https://github.com/AtomBoy/double-metaphone
Во-первых, я хотел бы добавить, что вы должны быть очень осторожны при использовании любой формы алгоритма фонетического / нечеткого сопоставления, так как этот тип логики является именно Fuzzy или, проще говоря; потенциально неточно. Особенно актуально при использовании для сопоставления названий компаний.
Хороший подход заключается в поиске подтверждения на основе других данных, таких как информация об адресе, почтовые индексы, номера телефонов, географические координаты и т. Д. Это поможет подтвердить вероятность того, что ваши данные будут точно сопоставлены.
Существует целый ряд проблем, связанных с сопоставлением данных В2В, и их слишком много, чтобы их можно было здесь рассмотреть. Я написал больше о сопоставлении названий компаний в своем блоге, но вкратце:
- Просмотр всей строки бесполезен, так как наиболее важная часть названия компании не обязательно находится в начале названия компании. то есть "Компания" Проктор энд Гэмбл "или" Федеральный резерв США "
- Сокращения обычно встречаются в названиях компаний, таких как HP, GM, GE, P&G, D&B и т. Д.
- Некоторые компании намеренно пишут свои имена неправильно в рамках своего брендинга и дифференцируют себя от других компаний.
Сопоставление точных данных легко, но сопоставление неточных данных может занять гораздо больше времени, и я бы посоветовал вам подумать о том, как вы будете проверять неточные совпадения, чтобы обеспечить их приемлемое качество.
До того, как мы создали Match2Lists.com, мы тратили нездоровое количество времени на проверку нечетких совпадений. В Match2Lists мы включили мощный инструмент визуализации, позволяющий нам просматривать неточные совпадения, что оказалось реальным изменением игры с точки зрения проверки соответствия, уменьшив наши затраты и позволив нам гораздо быстрее доставлять результаты.
Удачи!!
Вот ссылка на обсуждение php функций soundex в mysql и php. Я бы начал с этого, а затем расширил бы ваши другие не столь четко определенные требования.
Ваша ссылка ссылается на методологию сопоставления Левенштейна. Две проблемы. 1. Это больше подходит для измерения разницы между двумя известными словами, а не для поиска. 2. Обсуждается решение, разработанное для обнаружения таких вещей, как проверка ошибок (с использованием "Левенштиен" для "Левенштейн"), а не ошибок правописания (когда пользователь не знает, как пишется, скажем "Левенштейн", и вводит слова "Левинштейн"). Я обычно связываю это с поиском фразы в книге, а не со значением ключа в базе данных.
РЕДАКТИРОВАТЬ: В ответ на комментарий--
- Можете ли вы, по крайней мере, заставить пользователей разместить названия компаний в нескольких текстовых полях; 2. или используйте однозначный разделитель имен (скажем, обратный слеш); 3. опустить статьи ("The") и общие сокращения (или вы можете отфильтровать их); 4. Сократите пробелы и сравните их для этого (так, Micro Soft => Microsoft, Bare Essentials => bareessentials); 5. Отфильтруйте пунктуацию; 6. Выполняйте поиск "ИЛИ" по словам ("голые" ИЛИ "предметы первой необходимости") - люди неизбежно иногда пропускают одно или другое.
Тестируйте как сумасшедший и используйте обратную связь от пользователей.
Хотя вопрос касается того, как выполнять нечеткий поиск в MySQL, я бы порекомендовал рассмотреть возможность использования для этого отдельного механизма нечеткого поиска (также устойчивого к опечаткам). Вот некоторые поисковые системы, которые следует учитывать:
- ElasticSearch (с открытым исходным кодом, имеет множество функций и поэтому сложен в эксплуатации)
- Algolia (проприетарный, но с отличной документацией и очень простой в установке и запуске)
- Typesense (с открытым исходным кодом, предоставляет ту же функцию нечеткого поиска по мере ввода, что и Algolia)
Этот ответ приводит к индексированному поиску практически любого объекта, используя ввод из 2 или 3 символов или более.
По сути, создайте новую таблицу с 2 столбцами, словом и ключом. Запустите процесс на исходной таблице, содержащей столбец для нечеткого поиска. Этот процесс извлечет каждое отдельное слово из исходного столбца и запишет эти слова в таблицу слов вместе с исходным ключом. Во время этого процесса часто встречающиеся слова, такие как "the", "and" и т. Д. Должны быть отброшены.
Затем мы создаем несколько индексов в таблице слов следующим образом...
- Обычный строчный индекс для слова + клавиша
- Индекс от 2 до 5 символов + клавиша
Индекс от 3-го до 6-го символа + ключ
В качестве альтернативы создайте индекс SOUNDEX() для столбца слова.
Как только это будет сделано, мы берем любой пользовательский ввод и осуществляем поиск с использованием обычного word = input или LIKE input%. Мы никогда не вводим LIKE %, так как мы всегда ищем совпадения для любого из первых 3 символов, которые все проиндексированы.
Если ваша исходная таблица массивна, вы можете разбить таблицу слов на куски алфавита, чтобы обеспечить немедленное сужение ввода пользователя до строк-кандидатов.
Проверьте , если это прописано неправильно , прежде чем запрос с использованием доверенной и хорошо испытанных заклинаниями библиотеки проверки на стороне сервера, то сделайте простой запрос для исходного текста , а первым предложили правильное написание (если проверка орфографии определяется была опечатка).
Вы можете создавать собственные словари для любой библиотеки проверки орфографии, которую стоит использовать, что может потребоваться для сопоставления более неясных названий компаний.
Гораздо быстрее сопоставить две простые строки, чем вычислить расстояние Левенштейна для всей таблицы. MySQL не очень подходит для этого.
Недавно я столкнулся с подобной проблемой и потратил много времени на то, чтобы возиться с алгоритмами, поэтому мне очень жаль, что было больше людей, предостерегающих от того, чтобы делать это в MySQL.
Лучшая функция для нечеткого сопоставления - Левенштейн. это традиционно используется для проверки орфографии, так что это может быть путь. для этого есть UDF: http://joshdrew.com/
Недостатком использования Левенштейна является то, что он не очень хорошо масштабируется. лучшей идеей может быть выгрузка всей таблицы в файл пользовательского словаря для проверки орфографии и выполнение предложения на уровне вашего приложения вместо уровня базы данных.
Может быть, уже слишком поздно, но это может помочь другим. Проверьте эту ссылку. Он использует метрики расстояния Левенштейна, но гораздо быстрее. http://narenonit.blogspot.com/2012/07/fuzzy-matching-autocomplete-library.html
Возможно, предлагалось ранее, но почему бы не выгрузить данные в Excel и использовать плагин Fuzzy Match Excel. Это даст оценку от 0 до 1 (1 - 100%).
Я сделал это для данных делового партнера (компании), которые хранились в базе данных. Загрузите последние данные Регистрационной палаты Великобритании и сравните их.
Для данных ROW это более сложно, поскольку нам приходилось выполнять более ручной процесс.