Как написать алгоритм по генерации полного и правильного названия улицы, площади тд?

Можно попробовать операться на флексии в названии объекта. Для их выделения придется набросать какую-то библиотеку, а за основу взять любой стеммер. Если делаете на js то есть яндексовский стеммер быстрый и простой.
Лучше всего опираться на аффикс-стеммер.
Когда у вас будет суффикс слова потребуется выделить из него окончание. Это уже совсем просто, а если у вас аффикс-стеммер, то окончание где-то в нем уже будет выделно.
Ну а дальше правило частично подбирается из вашего же примера - окончание "ая" для объектов женского рода - тип добавляем в конце. Окончание "ого" для объектов мужского рода - тип в начале.
В названии содержится слово "имени" или "им." тогда тип ставится перед ним.
И так далее - вам будет нужна таблица окончание/тип объекта и на пересечениях положение типа относительно названия.
Это будет основной способ.
+ будет предварительный - если название из двух или трех слов и содержит слово "имени".
+ таблица особых случаев через которую вы зададите немногие исключения (которые вероятно будут).

Интересно, есть ли такой алгоритм, чтобы вытащить правильное (человекопонятное) написание улицы?

Алгоритма нет и быть не может.
Указанные вами случаи это привычные устоявшиеся словосочетания. Так просто привыкли говорить.
Алгоритм не может как то определить кто к чему привык.
Поэтому нужна база с устоявшимися выражениями и поиск по базе.