fatum

По идее без базы городов и адресов задачу решить вообще довольно сложно.

Например «Луганск Оборонная 39» мало отличается от обычного текста, если заранее неизвестно что речь о городе и улице.
В то же время гугл находит о каком адресе речь: my.jetscreenshot.com/226/20120819-yhtt-39kb
Вывод: если приложение ненагруженное можно просто покопать api гуглокарт, иначе только свою базу нужно.

Вычленяете регулярками токены, то есть роли слов. У вас будут роли для служебных слова разметки (г., ул., д, корп., кв., плюс варианты) и роли для прочих слов, которые можно подразделить на известные города и типичные улицы (Москва, Ленина, Мира), числа, почтовые индексы и единая роль НЕИЗВЕСТНО для всех прочих слов.

Если в тексте нашлись токены, известный город, улица, или (в зависимости от текста), даже просто число, то это сигнал — возможно, это адрес. Вычленяете список токенов, после чего разбираете уже список. Например, получилось «ИЗВЕСТНЫЙ-ГОРОД УЛ НЕИЗВЕСТНО ЧИСЛО». Скорее всего (99%) за НЕИЗВЕСТНО находится название улицы. Или НЕИЗВЕСТНО НЕИЗВЕСТНО ЧИСЛО ДЕФИС ЧИСЛО — может быть (50%) короткая запись адреса вроде «Тыгдым, Северная, 25-12». Вероятности условные, конечно :) Таких паттернов будет относительно немного, их уже парсить куда проще. В простейшем случае можно завести таблицу распознаваний «ИЗВЕСТНЫЙ-ГОРОД УЛ НЕИЗВЕСТНО ЧИСЛО -> ИЗВЕСТНЫЙ-ГОРОД УЛ НАЗВАНИЕ-УЛИЦЫ ЧИСЛО»

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

Не сочтите за рекламу, просто сам пользуюсь — ahunter.ru

Кто-то плохо знает регулярки ;) Все это вычленяется, включая все разнообразие форматом записи телефонов. Хотя, конечно, не со 100% точностью. Индекс, кстати, бывает вообще словами. Во всяких британиях, например. А город/улицу/телефон сливать в данные об одном и том же месте, если они находятся в пределах одного или соседних предложений можно, как вариант. В общем тут все сильно завязано на конкретный текст. Универсального ответа нету. Гору не так уж и часто сокращают, но можно и отфильтровать по словарю, хотя опять же зависит от текста/задачи/объема.

И, да, не забудем мы про регулярки ;) Во всех системах обработки естественного языка так или иначе задействованы регулярки. Если есть время, можете попересматривать тот курс по NLP nlp-class.org Все должно прояснится.

>>Не важно, в каком формате и каким образом

Так можно заходить на любой сайт с адресным классификатором (к примеру, объявления о недвижимости) и парсить, парсить…

Если серьезно, то вам нужен доступа к базе адресов одного из украинских картографов. Точно знаю, что Визиком предоставляет API для доступа в свою базу, в том числе и для получения списков городов, а в них улиц, а на улицах дает номера домов — maps.visicom.ua/ru/api-docs/vxmlapi/getaddress/getaddress-5