Парсинг почтовых адресов из строки на C#

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

Все бы хорошо, только засада в том, что исходные адреса клиентов были забиты в виде простой строки типа «Китежград, ул.Волшебная 22 дом кв.15». То есть, с одной стороны, о почтовых индексах никто слыхом не слыхивал, с другой же, текстовое поле ввода предлагает широкий простор для самовыражения и народно-прикладного творчества.

Ничтоже сумняшеся я полез искать решение сей проблемы в сети, рассудив, что подобная ситуация должна быть весьма распространенной и кем-то однозначно побежденной. Так и оказалось, правда, вместо исходников или просто скомпиленных либ на меня жадно пялились онлайн-сервисы, предлагающие с использованием их API парсить почтовые адреса за вполне реальную мзду (минимальный прайс, который мне удалось найти, составлял 10 копеек за адрес).
Так как отдавать добровольно доходы какой-то сторонней организации мне не нравилось, да и к тому времени появился некий азарт, захотелось сколхозить решение самостоятельно, по возможности минимальными усилиями. Облегчало задачу то, что заказчику не требовалась высокая точность парсинга – наличие ошибок любого рода не приводило бы к фатальным проблемам.

Для начала посмотрел в сторону Томита-парсера, но после знакомства с многостраничным конфигом примера, позволяющего по тексту определить, в каком городе кто живет (http://api.yandex.ru/tomita/doc/dg/concept/example.xml), оптимизма несколько поубавилось, но укрепилось желание написать какой-нибудь свой велосипед.

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

1. Адрес всегда написан без опечаток: «проспект Арфографии» пусть останется на совести вводящего.
2. Запись адреса ведется от максимально общего элемента (область) до максимально частного (номер квартиры).
3. С учетом пункта 2, забиваем болт на слова-подсказки типа «область», «улица», «проспект», «дом». Так что если в городе есть и проспект Телепузиков, и улица имени их же, то уловить столь тонкую грань мы не сможем. С учетом редкости подобной ситуации и наличием права на ошибку – вполне себе рабочий вариант.

Далее я озадачился поиском источника данных, из которого смог бы черпать сведения по почтовым индексам. Как оказалось, на сей день КЛАДР – это уже вчерашний день, ФИАС рулит (http://fias.nalog.ru). Загрузив оффлайновую копию этой базы, я принялся изучать предоставляемые ею возможности.

Особо заинтересовали меня там две таблицы: ADDROBJ – в ней хранится древовидный список всех адресных объектов, начиная с субъекта РФ и заканчивая улицей, и HOUSE<номер региона> – где хранятся номера домов с привязкой к записям в ADDROBJ вместе с их индексами. Хранящейся в этих двух таблицах информации достаточно для достижения обеих целей: проверки правильности парсинга адреса (если удалось найти адрес в базе данных, значит, мы его распознали верно), а так же для определения почтового индекса.

В голове начал вырисовываться алгоритм:

1. Разделяем строку почтового адреса на адресные элементы. Под адресным элементом подразумеваю то, запись о чем можно найти в виде строки таблицы ФИАС-а: район, город, улица, дом, а так же номер квартиры.
   1. К безусловным разделителям адресных элементов относятся точки, запятые, точки с запятой, слэши.
   2. К условным разделителям относится дефис/тире, если адресный элемент после дефиса является числом. Например в «переулок Депрессии, 38а-117» дефис является разделителем, а в «г. Усть-Зажопинск» – нет.
   3. Пробел может являться разделителем, а может и не быть им. Так в «Восьмого марта д.15» пробел между «Восьмого» и «марта», очевидно, не должен делить элементы, а между «марта» и «д.» – должен. Самый простой вариант в лоб – составить все возможные варианты разделения адресных элементов пробелами и продолжать дальнейшую работу алгоритма с каждым из них в отдельности.
2. Такие адресные элементы, как «улица» («ул»), «область» («обл») и так далее полностью выкусываются.
3. Начиная с самого первого элемента, все они последовательно прогоняются по базе ФИАС.
   1. Если элемент находится в базе, то запоминается его GUID и LEVEL (уровень в иерархии), при этом следующий элемент ищем с бОльшим значением LEVEL и фиксированным PARENTGUID равным GUID предыдущего найденного элемента.
   2. Если не найдено элемента по заданному PARENTGUID, пытаемся построить цепочку, включающую промежуточные элементы.
   3. Первоначальный поиск ведется в таблице ADDROBJ, как только ищем следующий после улицы элемент (LEVEL улицы равен 7), переключаемся на таблицу домов HOUSEXX.
   4. Если адресный элемент не найден, просто игнорируем его.
4. Побеждает вариант (а их по итогам шага 1.3. может быть несколько), у которого получилось самая длинная распознанная цепочка.
5. Для порядку она достраивается по таблице ADDROBJ до самого верха. Это нужно потому, что, например, в исходной адресной строке не было указано области и района, а сразу город.
6. Дальше немного схитрим. Номером квартиры считается последний адресный элемент (если он не был распознан как номер дома), а корпусом, строением, литерой и всем прочим – адресные элементы между распознанным номером дома и номером квартиры. Можно было бы построить более детальный анализ – таблица HOUSEXX это позволяет – но мне показалось это излишним хотя бы потому, что вряд ли почтовые индексы будут различны для домов «113» и «113 ст.1 корп 4 лит.Ж».

Алгоритм получился эмпирическим, наивным, предусматривающим не все возможные ситуации… Но для ограничений по скорости реализации и обширным правам на ошибку – он выглядел вполне удовлетворительным. Сочинить и реализовать его удалось примерно за 1 вечер.

Для привычки и удобства работы перегнал таблицы ADDROBJ и HOUSEXX из DBF в MS SQL (как их можно легко отконвертировать, прочел здесь: http://blogs.technet.com/b/isv_team/archive/2012/05/14/3497825.aspx).

В результате получился класс AddressParser, забирающий на входе строку адреса и выдающий в ответ экземпляр класса Address. В конструктор AddressParser можно подавать собственную реализацию IKnwonAddressComparator, если текущая реализация, заточенная на MS SQL чем-то не устраивает.

По скорости парсинга получилось что-то около 2-5 адресов в секунду. Плохо, но все лучше, чем ручками. Основная проблема: серьезное количество вариантов для проверки, генерируемое пунктом 1.3. По-хорошему, этот момент стоит полностью переписать, используя базу адресов уже на этом этапе для проверки существования адресных элементов. В качестве промежуточного варианта можно ограничить количество вариантов неким значением.

По случайной выборке качество парсинга составило 62% на реальных данных. Для оценки считалось, что адрес может либо быть полностью распознан (вплоть до квартиры), либо нет. Никаких полутонов.

Распределение по ошибкам получилось следующее:

• 37% — опечатки. Как правило, банальные пропуски-добавления букв: «Киирова», «Москв»…
• 21% — использование сокращений: «К.Маркса», «Р.Люксембург»…
• 42% — отсутствие домов в базе ФИАС, и, в результате, невозможность определить индекс и завалидировать всю цепочку. Весьма неожиданная для меня причина, хотя многие пишут, что ФИАС все еще сыроват для промышленного применения

Каике выводы можно сделать?

Если нужно, как и мне, невысокое качество парсинга и низкая скорость – можно использовать.

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

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

Но все это – уже совсем другая история.

Исходные коды можно загрузить отсюда: https://yadi.sk/d/muzi9b6qZ8DWh
Тестовую MS SQL базу с домами по 38 и 78 регионам можно взять здесь: https://yadi.sk/d/ERXyDXv7Z8Dab

Автор: t13s

Источник