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