У меня есть простая база данных контактов, но у меня возникают проблемы с входом пользователей в дубликаты данных. Я реализовал простое сравнение данных, но, к сожалению, дублированные данные, которые вводятся, не совсем то же самое. Например, имена неправильно написаны или один человек будет помещен в "Билл Смит", а другой - "Уильям Смит" для одного и того же человека.
Итак, есть ли какой-то алгоритм, который может дать процент от того, насколько аналогична запись для другого?
Итак, есть какой-то алгоритм что может дать процент за то, как аналогичная запись в другую?
Алгоритмы как расстояния Soundex и Edit (как показано в предыдущем сообщении) могут решить некоторые из ваших проблем. Однако, если вы серьезно относитесь к очистке данных, этого будет недостаточно. Как утверждали другие, "Билл" звучит не так, как "Уильям".
Лучшее решение, которое я нашел, - использовать алгоритм сокращения и таблицу, чтобы уменьшить имена для этого имени.
В свою обычную таблицу адресов добавьте корневые версии имен, например Person (Имя, RootFirstName, Surname, Rootsurname....)
Теперь создайте таблицу сопоставления. FirstNameMappings (первичное имя KEY, имя корня)
Заполните таблицу сопоставления: Вставьте IGNORE (выберите Firstname, "UNDEFINED" из Person) в FirstNameMappings
Это добавит все первые имена, которые вы используете в своей таблице, вместе с RootName из "UNDEFINED"
Теперь, к сожалению, вам придется пройти через все уникальные имена и сопоставить их с RootName. Например, "Билл", "Биллл" и "Уилл" должны быть переведены на "Уильяма", Это очень трудоемко, но если качество данных действительно важно для вас, я считаю это одним из лучших способов.
Теперь используйте вновь созданную таблицу сопоставления для обновления поля "Rootfirstname" в таблице Person. Повторите для фамилии и адреса. Как только это будет сделано, вы сможете обнаружить дубликаты, не испытывая орфографических ошибок.
Вы можете сравнить имена с расстояние Левенштейна. Если имена совпадают, расстояние равно 0, иначе оно задается минимальным количеством операций, необходимых для преобразования одной строки в другую.
Я предполагаю, что эта проблема хорошо понята, но что происходит со мной в первом чтении:
Используйте свою существующую базу данных, чтобы получить хорошее первое предположение для порога и исправить, когда вы накапливаете опыт.
Вы можете предпочесть довольно сильное отклонение от ложных срабатываний, по крайней мере, сначала.
В то время как у меня нет алгоритма для вас, моим первым действием было бы взглянуть на процесс, связанный с вводом нового контакта. Возможно, у пользователей нет простого способа найти контакт, который они ищут. Как и в случае новой формы вопроса "Переполнение стека", вы можете предлагать контакты, которые уже существуют на новом экране контакта.
Если у вас есть доступ к SSIS, проверьте преобразование Fuzzy grouping и Fuzzy.
http://www.sqlteam.com/article/using-fuzzy-lookup-transformations-in-sql-server-integration-services
Если у вас есть большая база данных со строковыми полями, вы можете очень быстро найти много дубликатов, используя алгоритм simhash.
Это может быть или не быть связанным, но незначительные орфографические ошибки могут быть обнаружены Soundex search, например, это позволит вам рассмотреть Бритни Спирс, Бритни Спирс и Бритни Спирс в качестве дубликатов.
Сокращения ников, однако, трудно рассматривать как дубликаты, и я сомневаюсь, что это разумно. Будут связаны несколько человек по имени Билл Смит и Уильям Смит, и вам придется повторять это с Чарльзом → Чак, Робертом → Бобем и т.д.
Кроме того, если вы рассматриваете, скажем, мусульманских пользователей, проблемы становятся более трудными (например, слишком много мусульман, которые называются Мухаммед/Мохаммад).
В FullContact.com есть API, который может решить это для вас, см. их документацию здесь: http://www.fullcontact.com/developer/docs/?category=name.
У них есть API для нормализации имен (Bill in William), Name Deducer (для сырого текста) и сходства имен (сравнение двух имен).
В настоящий момент все API-интерфейсы бесплатны, это может быть хороший способ начать работу.
Я не уверен, что он будет хорошо работать для проблемы с именами и прозвищами, но наиболее распространенным алгоритмом в этом виде области будет расстояние редактирования/Левенштейн расстояние. Это в основном подсчет количества изменений, дополнений и абзацев, необходимых для превращения одного элемента в другой.
Для имен, я не уверен, что вы когда-либо добьетесь хороших результатов с помощью чисто алгоритмического подхода. Что вам действительно нужно - это масса данных. Возьмем, к примеру, насколько лучше правильные предложения Google, чем в обычном настольном приложении. Это связано с тем, что Google может обрабатывать миллиарды веб-запросов и смотреть, какие запросы ведут друг к другу, какие "вы имели в виду" ссылки на самом деле получают клики и т.д.
Есть несколько компаний, которые специализируются на проблеме сопоставления имен (в основном для приложений национальной безопасности и мошенничества). Тот, который я помню, Search Software America, похоже, был выкуплен этими парнями http://www.informatica.com/products_services/identity_resolution/Pages/index.aspx, но я подозреваю, что любой из этих видов решения могут оказаться весьма дорогостоящими для приложений контактов.
Вы также можете посмотреть вероятностное соответствие.
Для тех, кто бродит по сети и заканчивает здесь, могу ли я предложить вам попробовать созданное мной дополнение Google Sheet под названием Flookup. Это особенно хорошо с именами и имеет несколько других замечательных функций, которые я опишу ниже:
rank из Flookup, чтобы дать алгоритму команду вернуть 1-е, 2-е, 3-е или n-е наилучшее совпадение. Это полезно, если у вас есть дополнительная информация, которую вы можете использовать для идентификации нужного вам "Джона Смита".John Smith & Apartment A или John Smith & Apartment B в качестве параметра поиска, чтобы помочь различать два имени.Я надеюсь, что вы найдете Flookup столь же полезным, как и другие.