Как сделать нечеткое совпадение названий компаний в MYSQL с PHP для автоматического завершения?
Мои пользователи будут импортировать через вырезать и вставить большую строку, которая будет содержать названия компаний.
У меня есть существующая и растущая база данных MYSQL названий компаний, каждая с уникальным company_id.
Я хочу иметь возможность проанализировать строку и назначить каждому из введенных пользователем имен компаний нечеткое соответствие.
Прямо сейчас, просто делая прямой матч строки, также медленно. ** Будет ли индексация Soundex быстрее? Как я могу дать пользователю некоторые варианты, как они есть печатать на машинке? **
Например, кто-то пишет:
Microsoft -> Microsoft
Bare Essentials -> Bare Escentuals
Polycom, Inc. -> Polycom
Я нашел следующие темы, которые кажутся похожими на этот вопрос, но плакат не одобрил, и я не уверен, применим ли их вариант использования:
Как найти наилучшее нечеткое соответствие для строки в большой базе данных строк
7 ответов:
Вы можете начать с использования
SOUNDEX(), это, вероятно, подойдет для того, что вам нужно (я представляю окно самовнушения уже существующих альтернатив для того, что пользователь вводит).Недостатками
SOUNDEX()являются:Его неспособность различать более длинные строки. Учитываются только первые несколько символов, более длинные строки, расходящиеся в конце, генерируют одно и то же значение SOUNDEX
- дело в том, что первая буква должна быть одной и той же, иначе вы не найдете матч легко. SQL Server имеет функцию DIFFERENCE (), чтобы сказать вам, насколько два значения SOUNDEX отличаются друг от друга, но я думаю, что MySQL не имеет ничего подобного встроенного.
- для MySQL, по крайней мере согласно docs, SOUNDEX разбивается для ввода unicode
Пример:
SELECT SOUNDEX('Microsoft') SELECT SOUNDEX('Microsift') SELECT SOUNDEX('Microsift Corporation') SELECT SOUNDEX('Microsift Subsidary') /* all of these return 'M262' */Для более продвинутых нужд, я думаю, вам нужно посмотреть на Левенштейновское расстояние (также называемое "edit distance") двух строк и работать с порогом. Это более сложно (=медленнее) решение, но оно позволяет обеспечить большую гибкость.
Главный недостаток состоит в том, что для вычисления расстояния между ними нужны обе строки. С помощью SOUNDEX вы можете хранить предварительно вычисленный SOUNDEX в вашей таблице и сравнивать/сортировать / группировать / фильтровать его. С расстоянием Левенштейна вы можете обнаружить, что разница между "Microsoft" и "Nzcrosoft" составляет всего 2, но потребуется гораздо больше времени, чтобы прийти к этому результату.В любом случае, пример функции расстояния Левенштейна для MySQL можно найти по адресу codejanitor.com: расстояние Левенштейна как хранимая функция MySQL (февраль. 10, 2007) .
SOUNDEX-это нормальный алгоритм для этого, но в последнее время появились достижения в этой области. Был создан еще один алгоритм, названный Метафоной, и позже он был переработан в двойной алгоритм Метафоны. Я лично использовал Java apache commons реализацию double metaphone, и она настраиваема и точна.
У них есть реализации на многих других языках на странице Википедии для этого тоже. На этот вопрос был дан ответ, но если вы найдете какой-либо из выявленные проблемы с SOUNDEX, появляющиеся в вашем приложении, приятно знать, что есть варианты. Иногда он может генерировать один и тот же код для двух действительно разных слов. Двойная метафона была создана, чтобы помочь решить эту проблему.
Украдено из Википедии: http://en.wikipedia.org/wiki/Soundex
Как ответ на недостатки в Алгоритм Soundex, Лоуренс Филипс разработал алгоритм Metaphone для та же цель. Филипс позже разработал усовершенствование для Metaphone, которую он называл двойной Метафоной. Двойная метафона включает в себя многое больший набор правил кодирования, чем его предшественник, обрабатывает подмножество нелатинские символы, и возвращает a первичное и вторичное кодирование для учет различных произношений одного-единственного слова в английском языке.
В нижней части страницы double metaphone у них есть его реализации для всех видов языков программирования: http://en.wikipedia.org/wiki/Double-Metaphone
Реализация Python & MySQL: https://github.com/AtomBoy/double-metaphone
Во-первых, я хотел бы добавить, что вы должны быть очень осторожны при использовании любой формы алгоритма фонетического/нечеткого сопоставления, так как этот вид логики именно такой, нечеткий или, проще говоря, потенциально неточный. Особенно верно, когда используется для сопоставления названий компаний.
Хороший подход заключается в том, чтобы искать подтверждения из других данных, таких как адресная информация, почтовые индексы, номера телефонов, географические координаты и т.д. Это поможет подтвердить вероятность того, что ваши данные будут точно соответствие.Существует целый ряд вопросов, связанных с сопоставлением данных B2B, слишком много, чтобы быть рассмотренными здесь, я написал больше о сопоставлении названия компании в моем блоге, но в целом ключевые вопросы таковы:
- смотреть на всю строку бесполезно как на самую важную часть. название компании не обязательно находится в начале названия компании Имя. то есть "Проктор энд Гэмбл Компани" или " Федерал США Резерв "
- аббревиатуры являются общим местом в Названия компаний: HP, GM, GE, P&G, D&B и др..
- Некоторые компании намеренно пишут свои названия неправильно, как часть их брендинг и отличить себя от других компаний.
Сопоставление точных данных легко, но сопоставление неточных данных может занять гораздо больше времени, и я бы предложил вам подумать о том, как вы будете проверять неточные соответствия, чтобы гарантировать, что они приемлемого качества.
До того, как мы построили Match2Lists.com - мы привыкли ... тратьте нездоровое количество времени на проверку нечетких совпадений. В Match2Lists мы включили мощный инструмент визуализации, позволяющий нам просматривать неточные матчи, это оказалось реальным изменением игры с точки зрения проверки соответствия, снижая наши затраты и позволяя нам доставлять результаты гораздо быстрее.
Удачи вам!!
Вот ссылка на обсуждение php функций soundex в mysql и php. Я бы начал оттуда, а затем расширил бы ваши другие не очень четко определенные требования.
Ваша ссылка ссылается на методику Левенштейна для сопоставления. Две проблемы. 1. Он больше подходит для измерения разницы между двумя известными словами, а не для поиска. 2. В нем обсуждается решение, предназначенное скорее для обнаружения таких вещей, как ошибки проверки правописания (использование "Levenshtien" для "Levenshtein"). чем орфографические ошибки (где пользователь не знает, как пишется, скажем " Левенштейн "и набирает"Левинштейн". Обычно я связываю это с поиском фразы в книге, а не ключевого значения в базе данных.
EDIT: в ответ на комментарий--
- можете ли вы, по крайней мере, заставить пользователей поместить названия компаний в несколько текстовых полей; 2. или используйте однозначный разделитель имен (скажем, обратную косую черту); 3. опустите статьи ("The") и общие сокращения (или вы можете отфильтровать их); 4. Squoosh пробелы и соответствовать для этого также (так Micro Soft = > microsoft, Bare Essentials => bareessentials); 5. Отфильтровать знаки препинания; 6. Делайте " или " поиск по словам ("голые "или" основные") - люди неизбежно будут иногда оставлять одно или другое.
Тестируйте как сумасшедший и используйте цикл обратной связи от пользователей.
Наилучшей функцией для нечеткого сопоставления является функция Левенштейна. он традиционно используется для проверки орфографии, так что это может быть путь. для этого есть UDF, доступный здесь: http://joshdrew.com/
Недостатком использования Левенштейна является то, что он не очень хорошо масштабируется. лучше всего было бы сбросить всю таблицу в файл пользовательского словаря проверки орфографии и сделать предложение с уровня приложения, а не с уровня базы данных.
Этот ответ приводит к индексированному поиску почти любой сущности с использованием ввода 2 или 3 символов или более.
В принципе, создайте новую таблицу с 2 столбцами, словом и ключом. Запустите процесс в исходной таблице, содержащей столбец для нечеткого поиска. Этот процесс будет извлекать каждое отдельное слово из исходного столбца и записывать эти слова в таблицу слов вместе с исходным ключом. Во время этого процесса обычно встречающиеся слова, такие как "the", " and " и т. д., должны быть отброшены.
Затем мы создадим несколько индексов в таблице word следующим образом...
- нормальный, строчный индекс на word + key
- индекс от 2-го до 5-го символа + ключ
Индекс от 3-го до 6-го символа + ключ
Поочередно создайте индекс SOUNDEX () в столбце word.
Как только это установлено, мы берем любой пользовательский ввод и ищем с помощью обычного слова = input или LIKE input%. Мы никогда не делаем ввод типа%, так как мы всегда ищем для совпадения по любому из первых 3 символов, которые все индексируются.
Если исходная таблица массивна, вы можете разбить таблицу слов на куски алфавита, чтобы гарантировать, что вводимые пользователем данные сразу же сужаются до строк-кандидатов.
Может быть, это слишком поздно, но это может помочь другим. Проверьте эту ссылку out.It использует метрики расстояния Левенштейна, но гораздо быстрее. http://narenonit.blogspot.com/2012/07/fuzzy-matching-autocomplete-library.html
Comments