Как сделать нечеткое совпадение почтовых адресов?

Question

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

Пока я нашел разные решения, но я думаю, что они довольно старые и не очень эффективные. Я уверен, что существуют лучшие методы, так что если у вас есть ссылки для чтения, я уверен, что эта тема может заинтересовать несколько человек.

Решения, которые я нашел (примеры в R):

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

  agrep("acusait", c("accusait", "abusait"), max = 2, value = TRUE)## [1] "accusait" "abusait"

• Сравнение фонем

  library(RecordLinkage)soundex(x<-c('accusait','acusait','abusait'))## [1] "A223" "A223" "A123"

• Использование корректора орфографии (в конечном итоге байесовского типа, как у Питера Норвига), но, по-моему, не очень эффективно для адресов.

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

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

Answer 1

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

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

Вот краткое описание того, как это делается на C++.

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

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

Что-то, что я не попробовал, является частичным бюджетом. Например, предположим, что типичное изменение уменьшает бюджет на 2, а не на 1, а бюджет уходит на 0, 2, 4 и т. Д. Тогда некоторые изменения можно считать "более дешевыми". Например, замена гласных может только уменьшить бюджет на 1, поэтому для стоимости одной замены согласных можно сделать две замены гласных.

Если слово не написано с ошибкой, время, которое оно занимает, пропорционально количеству букв в слове. В общем, время, которое требуется, является экспоненциальным по количеству изменений в слове.

Если вы работаете в R (как я делал в приведенном выше примере), я бы попросил его обратиться к программе на C++, потому что для этого вам нужна скорость скомпилированного языка.

Answer 2

Расширение того, что должен был сказать Майк, и использование строки соответствия библиотеки stringdist в R, чтобы соответствовать вектору адресов, допущенных ошибками в функции геокодирования ARCGIS:

rows<-length(unmatched$addresses)
#vector to put our matched addresses in
matched_add<-rep(NA, rows)
score<-rep(NA, rows)

#for instructional purposes only, you should use sapply to apply functions to vectors

 for (u in c(1:rows)){
     #gives you the position of the closest match in an address vector

     pos<-amatch(unmatched$address[u],index$address, maxDist = Inf)
     matched_add[u]<-index$address[pos]

     #stringsim here will give you the score to go back and adjust your
     #parameters

     score[u]<-stringsim(unmatched$address[u],index$address[pos])
} 

В Stringdist есть несколько методов, которые вы можете использовать для поиска приближенных совпадений, включая Левенштейна (method="lv"). Вы, вероятно, захотите поработать с ними, чтобы соответствовать вашему набору данных настолько хорошо, насколько это возможно.