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

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

У меня есть существующая и растущая база данных MYSQL имен компаний, каждая из которых имеет уникальный company_id.

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

Прямо сейчас, просто выполняя прямолинейное совпадение строк, тоже медленно. ** Будет ли индексирование Soundex быстрее? Как я могу дать пользователю некоторые параметры при вводе? **

Например, кто-то пишет:

Microsoft       -> Microsoft
Bare Essentials -> Bare Escentuals
Polycom, Inc.   -> Polycom

Я нашел следующие темы, похожие на этот вопрос, но плакат не одобрен, и я не уверен, применим ли их прецедент:

Как найти лучшее нечеткое соответствие для строки в большой строковой базе данных

Соответствие неточным названиям компаний в Java

Ответы

Ответ 1

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

Недостатками SOUNDEX() являются:

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

Пример:

SELECT SOUNDEX('Microsoft')
SELECT SOUNDEX('Microsift')
SELECT SOUNDEX('Microsift Corporation')
SELECT SOUNDEX('Microsift Subsidary')

/* all of these return 'M262' */

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

Основным недостатком является то, что вам нужны обе строки для расчета расстояния между ними. С помощью SOUNDEX вы можете сохранить предварительно рассчитанный SOUNDEX в своей таблице и сравнить с ним /sort/group/filter. С расстоянием Левенштейна вы можете обнаружить, что разница между "Microsoft" и "Nzcrosoft" составляет всего 2, но для этого потребуется гораздо больше времени.

В любом случае, пример функции расстояния Levenshtein для MySQL можно найти на codejanitor.com: расстояние Levenshtein как хранимая функция MySQL (10 февраля, 2007).

Ответ 2

SOUNDEX - это алгоритм OK для этого, но были последние достижения в этой теме. Другой алгоритм был создан под названием "Метафон", и позже он был пересмотрен в алгоритме Double Metaphone. Я лично использовал 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 p >

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

Ответ 3

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

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

В моем блоге имеется целый ряд вопросов, связанных с сопоставлением данных B2B, слишком много, поэтому я написал больше о Согласовании имен компаний в своем блоге, но в Резюме ключевых вопросов:

  • Взгляд на всю строку бесполезен как самая важная часть Название Компании не обязательно в начале Компании Имя. т.е. "Компания Proctor and Gamble или" Федеральная Резерв '
  • Сокращения являются обычным местом в названиях компаний, то есть HP, GM, GE, P & G, D & B и т.д.
  • Некоторые компании намеренно неправильно написали свои имена в качестве части их брендинг и отличать себя от других компаний.

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

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

Лучшее из удачи!!

Ответ 4

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

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

EDIT: В ответ на комментарий -

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

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

Ответ 5

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

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