Алгоритм почти для подобного поиска значений

I сделал такой проект в прошлом столетии. По сути, это была консолидация двух клиентских файлов после слияния с именами и адресами из трех разных источников.

Во-первых, как предлагалось на многих плакатах, преобразуйте все общеупотребительные слова, сокращения и орфографические ошибки в общую форму «Apt.» «Квартира» пр. До «Апт».

Затем просмотрите имя и определите первую букву имени плюс первую фамилию. (Не так просто, рассмотрите "доктора медицины. Сэр Генри де Баскервиль Смайт"), но не волнуйтесь, если есть совпадения, просто возьмите и то, и другое! Так что, если вам повезет, вы получите HBASKERVILLE и HSMYTHE. Теперь избавьтесь от всех гласных, поскольку именно здесь встречается большинство вариантов написания, и теперь у вас есть HBSKRVLL HSMTH.

Вы также можете получить эти строки из «Х. Баскервилля», «Сэра Генри Баскервилля Смита» и, к сожалению, «Гарольда Смита», но здесь мы говорим о нечетком сопоставлении!

Выполните аналогичное упражнение на полях улицы, квартиры и почтового индекса. Но не выбрасывайте исходные данные!

Теперь вы перейдете к интересному моменту: сначала вы сравниваете каждую из исходных строк и даете, скажем, 50 баллов за каждую строку, которая точно соответствует.Затем просмотрите «нормализованные» строки и дайте, скажем, 20 баллов за каждую, которая точно соответствует. Затем просмотрите все строки и дайте, скажем, 5 баллов за каждые четыре символа или более общих подстрок. Для каждой сравниваемой пары вы получите некоторые из них с оценками> 150, которые вы можете рассматривать как определенное соответствие, некоторые с оценками менее 50, которые вы можете считать несоответствующими, и некоторые промежуточные, которые имеют некоторую вероятность совпадения.

Вам потребуется дополнительная настройка, чтобы улучшить это, добавив различные правила, такие как «вычесть 20 очков за фамилию« кузнец »». Вам действительно нужно продолжать работать и настраивать, пока вы не будете довольны полученными совпадениями, но, как только вы посмотрите на результаты, вы довольно хорошо почувствуете, какой результат считать «совпадением», а от каких ложных срабатываний нужно избавиться. из.

Вы можете бросить все адреса в веб-сервис, например, Google Maps (не знаю, подходит ли этот сервис) и посмотреть, получат ли они одинаковые GPS-координаты.

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

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

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

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

После последовательной предварительной обработки входных данных n-граммы должны найти похожие адреса.

Основная проблема, которую я вижу здесь, заключается в точном определении равенства. Даже если кто-то напишет Jon. и другой Jone. - вы никогда не сможете сказать, одинаковы ли они. (Jon-Jonethan, Joneson, Jonedoe - все равно;)

Я работаю в фирме, где нам приходится решать именно эту проблему - боюсь, я должен сказать вам, что подобная проверка списков адресов для навигационных систем делается "вручную" большую часть времени. Сокращения иногда зависят от контекста, и есть другие вещи, которые затрудняют эту работу. Конечно, замена строк и т.д. делается с помощью python - но сказать вам СМЫСЛ такого сокращения можно только с помощью скрипта в нескольких случаях. ("St." -> может быть и "Saint" и "Street". Как решить? Невозможно... это работа человека).

Еще одна большая проблема, как вы сказали: "Существует ли улица "DJones" или человек? Или и то и другое? Кто из них здесь имеется в виду? Является ли этот DJones тем же самым, что и доктор Джонс или тем же самым, что и Дон Джонс? Это невозможно решить!

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

Я бы попробовал сделать следующее:

• разбить адрес на несколько слов, одновременно избавившись от знаков препинания
• проверить все слова на наличие шаблонов, которые обычно пишутся по-разному, и заменить их общим названием (например, заменить apartment, ap., ... на apt, заменить Doctor на Dr, ...)
• поместите все слова обратно в одну строку, отсортированную по алфавиту
• сравните все адреса, используя алгоритм нечеткого сравнения строк, например, Левенштейна
• настройте параметры алгоритма Левенштейна (например, вы хотите разрешить больше различий в длинных строках)
• наконец, проведите ручную проверку строк

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

Одним из методов может быть применение алгоритма расстояния Левенштейна к полям адреса. Это позволит сравнить строки на предмет сходства.

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

Есть возможность иметь таблицу словаря в базе данных, которая сопоставляет все варианты с «правильная» версия слова:

*Value* | *Meaning*
Apt.    | Apartment
Ap.     | Apartment
St.     | Street

Затем вы просматриваете каждое слово в словаре, прежде чем сравнивать.

Редактировать: только этот слишком наивен, чтобы быть практичным (см. Комментарий).

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

3 Jane Dr. -> Dr (in 3rd position (or last)) means Drive
Dr. Jones St -> Dr (in 1st position) means Doctor

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

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

Кажется, что для этого должны существовать коммерческие продукты.

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

У вас есть поле почтового индекса!!!

Так почему бы вам просто не купить таблицу почтовых индексов для вашей страны и использовать ее для очистки информации об улицах/городах/регионах/провинциях?

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

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

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

EDIT: (возможно, мне следует уточнить, что я предполагал, что имена исполнителей будут повторяться чаще, чем названия песен)

Я предполагаю, что время отклика не критично и что проблема заключается в поиске существующего адреса в базе данных, а не в объединении дубликатов. Я также предполагаю, что база данных содержит большое количество адресов (скажем, 3 миллиона), а не такое количество, которое можно экономично очистить вручную или с помощью Amazon's Mechanical Turk.

Предварительные вычисления - определение фрагментов адресов с высоким информационным содержанием.

1. Определите все уникальные слова, используемые в каждом поле базы данных, и подсчитайте их количество.
2. Исключите очень распространенные слова и аббревиатуры. (Street, st., appt, apt, etc.)

Когда адрес вводится,

1. Определите наиболее уникальное слово и выполните поиск (Street LIKE '%Jones%') для существующих адресов, содержащих эти слова.
2. Используйте предварительно вычисленную статистику для оценки количества адресов в наборе результатов
3. Если предполагаемый набор результатов слишком велик, выберите второе по уникальности слово и объедините его в поиске (Street LIKE '%Jones%' AND Town LIKE '%Anytown%')
4. Если предполагаемый набор результатов слишком мал, выберите второе по уникальности слово и объедините его в поиске (Street LIKE '%Aardvark%' OR Town LIKE '%Anytown')
5. если фактический набор результатов слишком большой/маленький, повторите запрос, добавляя дополнительные термины, как и раньше.

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

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

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

(Также рассмотрите вариант с латеральным мышлением: не могли бы вы найти брокерскую компанию, занимающуюся рассылкой списков по почте, которая очистит для вас базу данных? Возможно, они даже будут готовы заплатить вам за использование адресов)

Не рассматривали ли вы для этого SQL Server Integration Services? Компонент Fuzzy Lookup позволяет находить "близкие совпадения": http://msdn.microsoft.com/en-us/library/ms137786.aspx

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

Здесь приведен пример сопоставления адресов: http://msdn.microsoft.com/en-us/magazine/cc163731.aspx

Я нашел отличную статью.

Добавив некоторые библиотеки DLL в качестве пользовательских функций sql , мы можем использовать алгоритмы сравнения строк с помощью библиотеки SimMetrics .

Проверьте

http://anastasiosyal.com/archive/2009/01/11/18.aspx