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

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

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

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

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

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