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

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

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

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

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

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

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

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

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

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

Вы можете начать с использования 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 в своей таблице и сравнить с ним / sort / group / filter. С расстоянием Левенштейна вы можете обнаружить, что разница между «Microsoft» и «Nzcrosoft» составляет всего 2, но для этого потребуется гораздо больше времени.

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

SOUNDEX – алгоритм OK для этого, но последние достижения в этой области были достигнуты. Другой алгоритм был создан под названием «Метафон», и позже он был пересмотрен в алгоритме Double Metaphone. Я лично использовал java apache commons для реализации двойного метафона, и он настраивается и точен.

У них есть варианты реализации на многих других языках на странице википедии. На этот вопрос был дан ответ, но если вы найдете какие-либо из выявленных проблем с SOUNDEX, появляющимися в вашем приложении, приятно знать, что есть варианты. Иногда он может генерировать один и тот же код для двух разных слов. Двойной метафон был создан, чтобы помочь решить эту проблему.

Украден из википедии: http://ru.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

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

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

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

  • Рассмотрение всей строки бесполезно, так как самая важная часть названия компании не обязательно в начале названия компании. т.е. «Проктор и Гэмбл Компани» или «Федеральная резервная система Соединенных Штатов»,
  • Сокращения являются обычным местом в названиях компаний, то есть HP, GM, GE, P & G, D & B и т. Д.
  • Некоторые компании преднамеренно неправильно написали свои имена в рамках своего бренда и отличились от других компаний.

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

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

Удачи!!

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

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

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

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

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

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

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

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

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

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

  • Обычный, строчный индекс слова + ключ
  • Индекс на 2-й и 5-й символах +
  • Индекс с 3-го по 6-й символ + ключ

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

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

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

Может быть, слишком поздно, но это может помочь другим. Проверьте эту ссылку. Он использует метрики расстояния levenshtein, но намного быстрее. http://narenonit.blogspot.com/2012/07/fuzzy-matching-autocomplete-library.html

  • Почему strncpy небезопасен?
  • В чем разница между «текстом» и новой строкой («текст»)?
  • Соответствие строк с помощью шаблона
  • Преобразование String в Uri
  • Как я могу конкатенировать несколько необязательных строк в swift 3.0?
  • Преобразование XML-fragmentа String в узел документа в Java
  • байты строки в java?
  • Шестнадцатеричная строка в байтовый массив в C
  • Макрос для конкатенации двух строк в C
  • Как добавить индексы в таблицы MySQL?
  • C #: class для декодирования кодировки с кодовым кодированием?
  • Давайте будем гением компьютера.