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