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

Question

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

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

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

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

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

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

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

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

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

Answer 1

Вы можете начать с использования 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 г.) .

Answer 2

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

Answer 3

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

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

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

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

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

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

Удачи !!

Answer 4

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

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

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

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

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

Answer 5

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

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

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

• Обычный строчный индекс для слова + клавиша
• Индекс от 2-го до 5-го символа + клавиша

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

  Альтернативно, создайте индекс SOUNDEX () для столбца слова.

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

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

Answer 6

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

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