Вопрос: Как выполнить нормализацию адресов?

Лучший ответ: После того, как открыли для себя сервис https://dadata.ru/, вообще перестали тратить время и деньги на собственные костыли из граблей. Сервис просто огонь.
Для нас онлайн режим и скорость обработки не критична, поэтому мы даже уложились в бесплатный пробный тариф.
Вроде бы у них были решения по установке их ПО в закрытом контуре, а это не что иное, как нужный вам оффлайн. Правда тут уже бесплатно не прокатит точно.

До дадаты этот вопрос решался жутким нагромождением фильтров, регекспов с заменами и человеко-машинного совокупления.
Общая схема годится не только для адресов, а вообще любых грязных данных:
1. Входной датасет сохраняем в CSV и НИКОГДА не меняем.
2. Обработка многоступенчатая. Каждая ступень состоит из фильтра и модификатора. Фильтр решает применим ли модификатор к каждой записи. Модификатор применяет свою модификацию если фильтр разрешил.
3. Отладочный выхлоп, который показывает и позволяет быстро просмотреть полностью внесённые изменения.
4. Каждая ступень должна делать минимальное однотипное улучшение максимально большого числа строк. Цель - каждой ступенью уменьшать разнообразие проблем, увеличивать регулярность, стандартизировать.
5. При огромных входных датасетах можно сохранять промежуточный выхлоп, но в общем очистка должна выглядеть как пайп их последовательных ступеней обработки. 
- Очень часто бывает, что какая-то ступень незаметно ломает данные, а понимаешь это уже поздно, когда последующие ступени реализованы и отлажены, и сильно опираются на результат ломающей. Благодаря ступенчатости и иммутабельности процесса всегда можно зипнуть текущее состояние с любым предыдущим шагом и очередным фильтром заменить необходимые куски.
- Часто бывает, что какая-то из ступеней улучшив отдельные записи убирает характерные признаки для фильтрации элемнтов для другой ступени. Благодаря такому инкрементальному процессу можно переставлять ступени местами.
- При внесении ступенью изменения в запись. ступень должна оставлять свою сигнатуру в отдельном столбце. Удобно для поиска проблем.

Расскажите подробнее почему не рассматривается онлайн. Заинтриговали.

Худший ответ: Методом последовательных проходов.

1. Делаете опорный список городов/поселков/хуторов и тп (я опирался на OKTMO из Общероссийского классификатора территорий)
Определяетесь как распознавать преффиксы населённых пунктов: жд. ст / пос. / пгт. / д. / с. / х. (они есть в ОКТМО)

2. Собираете опорный список правильных названий улиц по каждому городу
Улицы надо нормализовать по единому принципу:
Кооперативный 5-й проезд
или
5-й Кооперативный проезд

определяетесь с сокращениями
пер. -> переулок
пр. -> проезд или проспект

делаете первый проход с вашими паттернами, если правильно определились город и улица - заносите их (и оставшийся номер дома) в БД.

3. Убираете правильно определившиеся из исходной базы.
Смотрите, что осталось, правите паттерны под оставшиеся и делаете следующий проход.

Оставшиеся в сухом остатке - под ручной разбор. Готовьтесь столкнуться с тем, что некоторых улиц/переулков нет на картах Яндекса/Гугла, а на самом деле они есть. Я такие сомнительные названия улиц помечал в БД флагом Trusted=0 чтобы разобраться с ними потом.

Ели опираться на карты openstreet/Яндекс/Google - у них некоторые улицы называются немного по-разному:
Улица 850 лет Москвы
850-летия Москвы
но карты вам всё-равно потребуются, ибо иметь адреса без привязки к гео-координатам - мало проку.

PS: С номерами домов по-любому будет полная засада - 40/1 может быть и 40 к1 и 40 копр.1