В общем случае задача очень масштабная. Вам нужно определиться, на какие допущения вы можете пойти: что-то пропустить, найти лишее и т.д.
Даже человеку сложно найти адрес во фразе типа "вчера был на цветочной".
Другое дело, если есть за что зацепиться: название улицы пишется с заглавной буквы, есть обозначения типа "ул." или "улица", в адресе обязательно есть номер дома и т.д.
Если такие критерии подходят, то:
1. Ищите цифры.
2. Ищите вхождения "ул", "улица", "пр", "проспект", "площадь".
3. Ищите слова, начинающиеся с заглавной буквы в середине предложения.
Затем выбирайте лексемы возле этих позиций и прогоняйте через Яндекс/2gis/ФИАС. Как фильтровать и обрабатывать результаты - зависит от самих результатов. Не стоит пытаться написать универсальный парсер, надо ориентироваться на особенности материала, с которым вы работаете.
Я недавно решал похожую, но чуть более простую задачу. Была база в Excel, где в одной из колонок записывались адреса клиентов. Но записывались в очень свободной форме, т.е. был мусор типа "красный кирпичный дом", "въезд под шлагбаум", "позвонить Васе, как будем на месте" и т.д. Мусор удалось отфильровать, хотя примерно в 2-3 из 100 записей приходилось работать руками (но это потому что адреса вообще могло не быть, а было "завод Заря" или "кафе у Петровича").
В общем, удачи.
