Для неструктурированных адресов можно наверное попробовать так:
— нормализовать по регистру
— разделить на токены (последовательности непрерывных символов: «ул.», «ленина», «123», «А», «8»);
— отсортировать лексикографически
— вычислить над сравниваемыми адресами редакционное расстояние
habrahabr.ru/blogs/algorithm/117063/ (считая весь список токенов «строкой», а «буквами» в ней — выделенные токены).
Например, после сортировки
«123», «8», «а», «ленина», «ул»
сравниваем с «москва, ленина, 123, 8»
«123», «8», «ленина», «москва»
редакционное расстояние — 2
сравниваем с «москва, ленина, 123-А, 8»
«123», «8», «а», «ленина», «москва»
редакционное расстояние — 1
Весьма желательно уметь убирать из анализа или приравнивать при сравнении константы «ул.», «улица», «пл.», «пр-д», «проезд», «г.».