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

StackOverflow https://stackoverflow.com/questions/369755

Вопрос

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

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

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

Прямо сейчас простое сопоставление строк тоже происходит медленно.** Будет ли индексация 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 в своей таблице и сравнивать/сортировать/группировать/фильтровать его.Используя расстояние Левенштейна, вы можете обнаружить, что разница между «Microsoft» и «Nzcrosoft» составляет всего 2, но чтобы прийти к такому результату, потребуется гораздо больше времени.

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

Другие советы

SOUNDEX — подходящий для этого алгоритм, но в последнее время в этой теме были достигнуты успехи.Был создан еще один алгоритм под названием «Метафон», который позже был преобразован в алгоритм «Двойной метафон».Я лично использовал реализацию двойного метафона в Java Apache Commons, и она настраиваема и точна.

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

Украдено из википедии: http://en.wikipedia.org/wiki/Soundex

В ответ на недостатки в алгоритме Soundex, Лоуренс Филипс разработал алгоритм метафона для той же цели.Позже Филипс развил улучшение метафона, которое он назвал двойным метафоном.Двойной метафон включает в себя гораздо больший набор правил кодирования, чем его предшественник, обрабатывает подмножество нелатиновых символов и возвращает первичное и вторичное кодирование, чтобы объяснить различные произношения одного слова на английском языке.

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

Реализация Python и MySQL: https://github.com/AtomBoy/двойной метафон

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

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

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

  • Глядя на всю строку бесполезно, поскольку самая важная часть названия компании не обязательно в начале названия компании.то есть«Компания Proctor and Gamble» или «Федеральная резервная система США»
  • Аббревиатуры являются обычным явлением в названиях компаний, т.е.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.Выполняйте поиск по словам с помощью «ИЛИ» («голое» ИЛИ «основное») — люди иногда неизбежно упускают одно или другое.

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

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

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

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

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

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

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

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top