Как сделать нечеткое совпадение названий компаний в MYSQL с помощью PHP для автозаполнения?

Вы можете начать с использования SOUNDEX(), это, вероятно, подойдет для того, что вам нужно (я представляю автоматический ящик для предложений уже существующих альтернатив тому, что вводит пользователь).

Недостатки SOUNDEX():

• его неспособность различать более длинные струны. Учитываются только первые несколько символов, более длинные строки, которые расходятся в конце, генерируют одно и то же значение SOUNDEX.
• тот факт, что первая буква должна быть такой же, иначе вам будет нелегко найти совпадение. В SQL Server есть функция DIFFERENCE (), которая сообщает вам, насколько различаются два значения SOUNDEX, но я думаю, что в MySQL нет ничего подобного.
• для MySQL, по крайней мере, в соответствии с документами , SOUNDEX не работает при вводе в Юникоде

Пример:

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 для той же цели. Позднее Филипс разработал усовершенствование Metaphone, которое он назвал Double-Metaphone. Double-Metaphone включает гораздо больший набор правил кодирования, чем его предшественник, обрабатывает подмножество нелатинских символов и возвращает первичную и вторичную кодировку для учета различного произношения одного слова на английском языке.

Внизу страницы двойного метафона есть его реализации для всех типов языков программирования: http://en.wikipedia.org/wiki/Double-Metaphone

Реализация Python и MySQL: https://github.com/AtomBoy/double-metaphone

Во-первых, я хотел бы добавить, что вы должны быть очень осторожны при использовании любой формы алгоритма фонетического / нечеткого сопоставления, поскольку этот вид логики именно такой, нечеткий или, проще говоря; потенциально неточно. Особенно актуально при использовании для сопоставления названий компаний.

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

Существует целый ряд проблем, связанных с сопоставлением данных B2B, слишком много для рассмотрения здесь. Я написал больше о Company Name Matching в моем блоге (также обновленная статья), но в целом основные проблемы:

• Просмотр всей строки бесполезен, поскольку наиболее важная часть названия компании не обязательно должна находиться в начале названия компании. то есть "The Proctor and Gamble Company" или "Федеральная резервная система США"
• Аббревиатуры часто используются в названиях компаний, например HP, GM, GE, P&G, D&B и т. Д.
• Некоторые компании намеренно неправильно пишут свои имена в рамках своего брендинга и для того, чтобы отличаться от других компаний.

Сопоставление точных данных легко, но сопоставление неточных данных может занять гораздо больше времени, и я бы посоветовал вам подумать о том, как вы будете проверять неточные совпадения, чтобы гарантировать их приемлемое качество.

До того, как мы создали Match2Lists.com, мы тратили нездоровое количество времени на проверку нечетких совпадений. В Match2Lists мы включили мощный инструмент визуализации, позволяющий проверять неточные совпадения, что, как оказалось, действительно изменило правила игры с точки зрения проверки совпадений, снизив наши затраты и позволив нам получать результаты намного быстрее.

Удачи!!

Вот ссылка на обсуждение php функций soundex в mysql и php. Я бы начал с этого, а затем перешел к другим вашим не очень четко определенным требованиям.

Ваша ссылка ссылается на методологию Левенштейна для сопоставления. Две проблемы. 1. Это больше подходит для измерения разницы между двумя известными словами, а не для поиска. 2. В нем обсуждается решение, разработанное больше для обнаружения таких вещей, как ошибки проверки (с использованием «Левенштейна» вместо «Левенштейна»), а не орфографические ошибки (когда пользователь не знает, как писать, скажем «Левенштейн» и набирает «Левинштейн»). Я обычно связываю это с поиском фразы в книге, а не с ключевым значением в базе данных.

РЕДАКТИРОВАТЬ: в ответ на комментарий -

1. Можете ли вы хотя бы заставить пользователей помещать названия компаний в несколько текстовых полей; 2. или используйте однозначный разделитель имени (например, обратную косую черту); 3. исключить статьи («The») и общие сокращения (или вы можете отфильтровать их); 4. Удалите пробелы и сопоставьте их также (например, Micro Soft => microsoft, Bare Essentials => bareessentials); 5. Отфильтровать знаки препинания; 6. Выполняйте поиск по словам «ИЛИ» («просто» ИЛИ «самое необходимое») - люди иногда неизбежно пропускают одно или другое.

Тестируйте как сумасшедший и используйте обратную связь от пользователей.

Этот ответ приводит к индексированному поиску практически любого объекта с использованием ввода 2 или 3 символов или более.

По сути, создайте новую таблицу с двумя столбцами, словом и ключом. Запустите процесс с исходной таблицей, содержащей столбец для нечеткого поиска. Этот процесс извлечет каждое отдельное слово из исходного столбца и запишет эти слова в таблицу слов вместе с исходным ключом. Во время этого процесса следует отбросить часто встречающиеся слова, такие как «the», «and» и т. Д.

Затем мы создаем несколько индексов в таблице слов следующим образом ...

• Нормальный индекс в нижнем регистре для слова + клавиша
• Индекс со 2-го по 5-й символы + клавиша

• Индекс с 3-го по 6-й символы + клавиша

  В качестве альтернативы создайте индекс SOUNDEX () в столбце слова.

Как только это будет сделано, мы берем любой пользовательский ввод и ищем, используя обычный word = input или LIKE input%. Мы никогда не вводим LIKE%, так как всегда ищем совпадение по любому из первых 3 символов, которые все индексируются.

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

Лучшая функция для нечеткого сопоставления - levenshtein. он традиционно используется программами проверки орфографии, так что это может быть подходящим вариантом. UDF для него доступен здесь: http://joshdrew.com/

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

Хотя вопрос касается того, как выполнять нечеткий поиск в MySQL, я бы порекомендовал рассмотреть возможность использования для этого отдельного механизма нечеткого поиска (также устойчивого к опечаткам). Вот некоторые поисковые системы, которые следует учитывать:

• ElasticSearch (с открытым исходным кодом, имеет множество функций и поэтому сложен в эксплуатации)
• Algolia (проприетарный, но с отличной документацией и очень простой в установке и запуске)
• Typesense (с открытым исходным кодом, предоставляет ту же функцию нечеткого поиска по мере ввода, что и Algolia)