Сложные решения простых задач. Структуризация почтового адреса

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

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

Также как и для любой иной задачи, прежде чем её решать, необходимо понять области применения решения. Например, если задача только определения по адресу региона до определённого уровня (города, территории) — то это довольно просто, достаточно извлечь индекс и найти соответствия ключевых слов верхним срезам из ОКАТО, другое дело когда необходимо не просто разобрать адрес, а представить его в виде осмысленной структуры связанной с региональными классификаторами именно этот случай я приведу здесь в пример.

1. Первый и чуть ли не самый главный шаг — это накопление исследовательской выборки. Правило тут очень простое — чем больше данных накоплено, тем больше шансов охватить все возможные случаи причём важно чтобы накопленная выборка включала данные в разном качестве, разных форматах и так далее. Собрав хотя бы несколько десятков тысяч адресов можно приступать к их анализу.

2. Составление перечня составных частей объета.

Любой сложный объект, сложная запись — это всегда совокупность из нескольких более простых структур данных, его составных частей. В случае адреса можно говорить о таких составных частях как: почтовый индекс, страна, регион, город, район, поселение (село, поселок и т.д.), улица, дом, корпус, строение, офис, кабинет и ещё несколько более редких составных частей, а также случаи с абонентскими почтовыми ящиками. В зависимости от используемого языка разработки каждая часть может быть описана как — программный класс, класс RDF или структура данных. Для каждой из составных частей определяются её размерность, тип данных, связанные ключевые слова и возможность корректировки и проверки по внешним классификаторам — о чём далее.

3. Подбор и использование внешних классификаторов.

Как только перечень составных частей сформирован время занятся подбором эталонных справочников по которым можно проверить из значение. Правило больше данных — лучше результаты работает тут на 100%. Чем больше разных связанных справочников мы можем подключить тем лучше будут конечные результаты. Так, в случае адресов у нас есть следующие справочники:

  • Почтовые индексы;
  • ОКАТО;
  • КЛАДР;
  • Геоклассификационные справочники ГИС систем;
  • плюс ещё ряд малоизвестных.

Из всех перечисленных наиболее полным по России является КЛАДР, в нём присутствует детализация вплоть до улиц и существует возможность связать с ним все остальные. Эта провязка — однакратная, но важная часть работы. Справочники необходимо связывать обязательно даже если окажется что это пригодится не сразу, тем не менее это пригодится позже.

Классификаторы не только связываются между собой, но и с объектами составных частей адреса. Так индекс — связан со справочником почтовых индексов, регион, город, поселение, улица — связаны с КЛАДР.

4. Формирование шаблонов и справочника ключевых слов

Шаблон — это повторяющийся тип структуры данных в рамках данного типа объекта, адреса. При этом шаблон может присутствовать как у всего объекта по совокупности составляющих его частей, так и присутствуют структурные шаблоны. О том что такое структурные шаблоны необходимо упомянуть подробнее. Структурный шаблон — это шаблон обрамления, формы представления значимой части составной части объекта. Для текста и для составных частей адреса, в частности, структурный шаблон означает совокупность знаков пунктуации и якорных, поддерживающих ключевых слов уточняющих данную составную часть.

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

  • «г. {city_name}»
  • «город {city_name}»
  • «{city_name}»

а района:

  • «р-н {area_name}»
  • «район {area_name}»
  • «{area_name} район»
  • «{area_name} р-н»

Можно обратить внимание что число шаблонов для записи различных составных частей будет весьма ограниченным что связано с ограниченностью ключевых слов по которым мы уточняем данную составную часть. Поэтому для полноты и точности формирования шаблонов все ключевых слова не относящиеся к проверяемым по словарям — формируются в специальный справочник. Опять же в зависимости от выбранного языка разработки этот справочник может быть справочником структур, программных объектов или RDF классов. Важно то что каждое подобное ключевое слово должно в обязательном порядке иметь ссылку на составную часть которую оно характеризует, а также соответствующую форму представления.

Финальный набор шаблонов будет нечто вроде «{keyword:area_abbr} {part:area_name}» или «{keyword:city} {part:city}».

Примечание: В данном случае описание шаблонов приводится в несколько упрощённом виде, в реальных системах они ближе к регулярным выражениям.

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

Шаблоны полной записи адреса являются двойными.

В первом приближении — это вариаций наличия составных частей, например, «{segment:index}, {segment:city}, {segment:abonent}» описание шаблона типового почтового адреса абоненского почтового ящика в г. Москве.

Во втором приближении — это вариации шаблонов составных частей. Например, «{part:index}, {keyword:city} {part:city}, {keyword:mailbox} {part:mailbox}»

Шаблонов в первом приближении относительно немного — пара десятков, а вот во втором приближении их может быть до сотни.

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

5. Аннотирование и сегментация текста адреса.

Адрес, как бы он ни был записан обладает довольно простой структурой как данных так и форм представления. В подавляющем большинстве случаев адрес пишут по нисходящей от старшего объекта в иерархии, до младшего, чаще всего начиная с индекса — который здесь идёт отдельно. Но бывают случаи когда адрес могут записать и в обратном порядке в форме «111111, с. такое-то, район такой-то, регион Вот-такой, улица Подводная, д. 4». А в некоторых случаях и название страны «Россия», «РФ», «Российская федерация» может оказаться в середине адреса или в конце.

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

Эта ситуация решается следующим образом.

Текст адреса анализируется в несколько проходов:

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

II. На втором проходе производится проверка значимых слов по справочникам в соответствии с найденными рядом с ними ключевыми словами и разметкой адреса. Соответствующие области текста аннотируются как найденные и классифицированные.

III. На третьем проходе производится поиск соответствия разметки текста собранным ранее шаблонам и при нахождении соответствий последовательно проверяются шаблоны кандидаты.

IV. На четвёртом проходе анализируются все неразмеченные участки текста, а также проверяется достаточно ли точно удалось произвести структуризацию адреса.

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

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

В общем-же случае это описание довольно простого случая и простого алгоритма — поскольку имеется множество вспомогательных данных и ограниченное число вариаций.

Для других задач как-то: автоматическое распознавание  HTML/PDF/DOC шаблонов, анализ ссылок, классификация и аннотирование текстов, машинный перевод; используются куда как более сложные алгоритмы и решения.

About This Author

  • valerytin

    Реализовал автоматическое преобразование «российский адрес произвольной строкой» ->
    структурированный адрес по КЛАДР. Как итог 1,5 годовой работы — алгоритм, позволяющий портировать
    строки-адреса с вероятностью верного выхода 95-98% (по реальным данным из продакшн-БД)
    в промышленных масштабах (т.е. со скоростью 5-20 строк/сек., в зависимости от полноты и качества
    исходных данных — наличия опечаток, недостатка/избытка уровней/слов, степени противоречивости
    данных и т.п.); готов поспорить и насчет «довольно простой структуры»,
    и по поводу «решаются и без особых сложностей».
    Если интересно, конечно…

  • http://ivan.begtin.name ivbeg

    Всё это, конечно, интересно, но ведь ни Вы ни я не будем раскрывать здесь код алгоритмов для сравнения.

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

  • http://ahunter.ru skv

    Да, готов присоединиться к спору на счет простоты и легкости решения поставленной задачи. Недавно запустил сервис «Охотник за адресами» ahunter.ru, решающий задачу распознавания адреса в сплошном тексте. Не сказал бы, что решение оказалось тривиальным. В процессе решения проблем, всплывающих в процессе разработки, приходилось использовать нетривиальные методы интерполяции функций многих переменных, нейронные сети, деревья решений, а также нечеткую логику.

  • http://ivan.begtin.name ivbeg

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

    Ваш сервис, на мой взгляд, вполне интересен, но шлифовать его ещё необходимо.
    Далее, примеры которые не распознаёт или распознаёт неполностью аш ahunter.ru
    1. 109507, город Москва, абонентский ящик номер 60 — не распознаётся
    2. 363754, Россия, г. Моздок РСО-А — не распознаётся
    3. Уфа, Театральная, д. 5/2, Россия, 450008, — слово «Россия» и индекс выпадают из адреса
    4. 660017, Красноярс, ул. Карла Маркса, 122, оф. 220 — при опечатке вместо города Красноярск указывается село Красноярка Омской области

  • http://ahunter.ru skv

    Ну раз задача решена многими, то, действительно, спорить не будем, тем более что «Охотник» предназначен для вылавливания адресов в сплошных текстах, а не для разбора одной единственной строки.
    На счет шлифовки сервиса согласен, для этого он в общем-то и запущен on-line.
    Спасибо за внимание и перечисленные недочеты.
    Относительно Вашей статьи могу добавить следующее. Самым рутинным делом является синтез шаблонов, поэтому в больших системах этот процесс стараются максимально автомазирировать, например, используя методы индуктивного машинного обучения.

Яндекс.Метрика