Попалась тут задачка на поиск совпадений в строках (адреса)…
Постановка задачи
В рамках работ по «автоматизации процессов комплаенс-контроля» есть тема по поиску и фиксации совпадений по разным признакам между данными клиентов и данными «субъектов списков Росфинмониторинга» (разного рода террористы-экстремисты).
В данном случае — совпадения по адресам. Но не просто «адрес клиента равен адресу субъекта» — это было бы слишком просто, а «все уникальные элементы нормализованного адреса субъекта входят в адрес клиента» (но не наоборот). Порядок следования и наличие повторений элемента в адресе не играют роли.
Нормализация адреса — приведение его к верхнему регистру, удаление лишних пробелов и удаление всяких «город», «г.», «улица», «ул.» и т.п. Т.е. «Российская Федерация, г. Мухосранск, ул. Коммунистический тупик, д. 13, кв. 666» нормализуется в «МУХОСРАНСК КОММУНИСТИЧЕСКИЙ ТУПИК 13 666». «Элементом» адреса является отдельное слово (разделенное пробелами).
Дабы облегчить себе жизнь, есть т.н. «витрины адресов» — три таблицы. В первой содержится идентификатор клиента/субъекта + идентификатор адреса (для субъектов есть еще т.н. «ключевое слово» — элемент адреса субъекта, который реже всего встречается в витрине адресов клиентов). Во второй — набор связей адрес-элемент — идентификатор адреса + идентификатор элемента + номер элемента в строке адреса. И в третьей — список элементов — элемент + идентификатор элемента. Т.о. имеем две «витрины» — адреса клиентов и адреса субъектов.
На промсреде витрина адресов клиентов содержит порядка 96 млн адресов. Витрина адресов субъектов — порядка 8 тыс адресов. Сравнить надо всех со всеми — 768 млрд комбинаций где-то…
Запуск всего этого подразумевается в трех режимах
Полный поиск всех совпадений (самый тяжелый режим — сравниваются все со всеми, благо запускается достаточно редко).
Поиск по дельте «от клиентов» — запускается каждый день с отбором для проверки только тех клиентов, у которых за прошедшие сутки были изменения в адресах.
Поиск по дельте «от субъектов» — запускается после загрузки очередной версии списка росфина
Соответственно, при обработке у нас есть варианты
Появилось новое совпадение — нужно добавить в таблицу
Совпадение уже было, но в нем что-то изменилось (там есть ряд дополнительных признаков — тип адреса и т.п.) — обновляем запись
Совпадение было и ничего не поменялось — ничего не делаем
Совпадение было в таблице, но сейчас его нет — удаляем запись из таблицы
По времени. Заказчик хочет чтобы все это занимало не более 3–4 часов. Т.е. если процесс запущен в 4–5 утра, то к началу рабочего дня (9 утра) все должно уже завершиться.
Реализация
Параллельная обработка
Сразу понятно, что объем данных достаточно велик чтобы обрабатывать все это в один поток. Т.е. надо распараллеливать обработку. Что в наших условиях является стандартным подходом, для которого есть готовые решения, оформленные в виде шаблонов («скелетонов»). Реализуется все это примерно так:
Есть «головное задание» и «задание-обработчик».
Задача головного задания — отбор данных, задача обработчика — обработка одного элемента.
Головное задание при старте запускает нужное количество фоновых заданий-обработчиков, затем делает выборку данных для обработки, объединяет их в пакеты (по 10–100 элементов) и выкладывает на конвейер. В качестве конвейера можно использовать, например, pipe или очередь (про доступные нам системные очереди писал тут). Когда данные закончились, на конвейер выкладываются пустые пакеты (по количество обработчиков), означающие что данных больше нет и можно завершать работу.
Обработчик «подхватывает» с конвейера очередной пакет, обрабатывает все содержащиеся в нем элементы и идет за следующим. И так, пока не придет пустой пакет. Тогда обработчик завершает работу.
Таким образом имеем два комплекса — один работает «от клиентов» — головное задание делает отбор адресов клиентов (все или изменившиеся за последние стуки), обработчик для каждого адреса клиента ищет совпадения с адресами субъектов. Второй работает «от субъектов» — головное задание отбирает адреса субъектов (аналогично — все или загруженные в рамках последнего списка), обработчик ищет совпадения адреса субъекта с адресами клиентов.
Над всем этим небольшая запускалка с указанием режима работы — все, по текущей дате, по последнему списку, которая уже выбирает какой именно комплекс надо запустить (забегая вперед — для режима «все» запускается комплекс «от субъектов» т.к. он работает существенно быстрее).
Общий алгоритм
Головные задания вопросов не вызывают — отбор данных там достаточно простой, кроме того, отбор данных для обработки всегда на порядки быстрее самой их обработки.
Все вопросы возникают по реализации обработчика. Общий алгоритм таков: при получении очередного клиента/субъекта проходим по таблице совпадений и формируем список уже имеющихся совпадений для данного клиента/субъекта. Это список «того, что есть сейчас». Дальше нужно найти совпадения и получить список «того, что должно быть». Имея эти два списка, идем по списку того что есть и для каждой записи ищем соответствие в списке того, что должно быть. Не нашли — удаляем запись из таблицы. Нашли — проверяем требуется ли изменение (если да, то изменяем), после чего удаляем найденную запись из списка того, что должно быть.
После проверки всего списка того, что есть в списке того, что должно быть может остаться какое-то количество записей, для которых не было соответствий в списке того, что есть. Это новые совпадения — они безусловно добавляются в таблицу.
А теперь самое интересное…
Поиск совпадений и формирование списка того, что должно быть
Первая попытка решения была «пристрелочной» — просто перебором и проверкой каждого адреса на совпадение. Чтобы просто понимать с чем имеем дело и какой порядок времени все это занимает. Изначально вообще была всего одна витрина — только по адресам клиентов. Адреса субъектов нормализовались и разбивались на элементы в рантайме.
Потом пришло понимание что нужна витрина и тут. Наличие двух витрин сразу дало возможность отказаться от отдельной процедуры проверки совпадения адреса и вынести это все на уровень SQL запроса который искал пересечения в группах (элементы адреса субъекта — элементы адреса клиента) и отбирал те группы, в которых количество пересечений было равно количеству уникальных элементов в адресе субъекта.
Такие запросы были реализованы как для работы «от клиента», так и для работы «от субъекта». Выглядели страшненько, но работали. Для случая «по дельтам» укладывались в заданное временное окно с хорошим запасом, но была проблема с полной проверкой — «от клиентов» она работала около 2-х суток, «от субъекта» — порядка 10 часов. Ни то, ни другое не устраивало.
На этом этапе уже стало понятно, что работа по дельтам в целом укладывается в заданные условия, но с работой по полной версии нужно что-то решать. И что наиболее перспективной здесь выглядит работа «от субъекта» — во-первых, там меньше данных, во-вторых, алгоритм сравнения ассиметричен —
«все уникальные элементы нормализованного адреса субъекта входят в адрес клиента» (но не наоборот)
И тут вступают в силу особенности языка RPG (о возможностях которого писал тут). В частности — возможность работать с БД средствами прямого доступа (позиционирование по индексу и т.п.). В результате родился такой вот «play-off» алгоритм для каждого адреса субъекта:
Определяем идентификатор элемента витрины адресов клиентов, соответствующего ключевому слову адреса субъекта (1)
Заполняем массив уникальных идентификаторов из витрины адресов клиентов для остальных элементов адреса субъекта (2)
Заполняем массив идентификаторов адресов клиентов, содержащих найденный идентификатор элемента (список тех, кто потенциально может дать совпадение) (2)
В цикле для всех остальных (кроме ключевого слова) уникальных идентификаторов элементов адреса субъекта в витрине адресов клиентов проходим по имеющемуся массиву идентификаторов адресов клиентов и проверяем наличие в индексе пары идентификатор адреса клиента + идентификатор элемента адреса субъекта в витрине адресов клиентов (3). Если пара отсутствует в индексе, идентификатор адреса клиента удаляется из массива.
На выходе из цикла имеем массив идентификаторов адресов клиентов, которые содержат все уникальные элементы адреса субъекта — остальные из него удалены в процессе просеивания. На основе этого массива уже строим список того, что должно быть для последующего сравнения со списком того, что есть в БД.
Пояснения:
(1) — чтение записи по уникальному ключу
(2) — позиционирование на первую запись с заданным значением ключа и дальше в цикле чтение записей до тех пор, пока значение ключа не поменяется.
(3) — проверка наличия в индексе записи для заданного значения ключа без чтения самой записи из таблицы.
Все это выполняется при помощи команд прямого доступа к БД, предоставляемых RPG.
В реальных условиях первичное заполнение массива может дать достаточно большое количество элементов (на тестах на копии промсреды получали 500–600 тысяч) — селективность по элементам адреса не очень хорошая — ладно если там какое-нибудь село Синьял-Котяки (реально есть такое в Удмуртии), а если это, скажем, Екатеринбург, проспект Космонавтов? Сколько клиентов в полуторамиллионном Екатеринбурге? Сколько клиентов живет по всей стране на Космонавтов? Спасает то, что дальше, на каждом «обороте» цикла размер этого списка будет только сокращаться за счет исключения из него элементов.
Очень хорошо то, что самая массовая (по количеству обращений к БД) операция — это (3), которая не требует затрат времени на чтение записи из таблицы, только проверка ее наличия в индексе.
В результате полная проверка «от субъектов» на копии промсреды занимает 15 (пятнадцать! ) минут (вместо 10 часов в варианте с SQL запросом). Что можно считать просто замечательным результатом.
К сожалению, такой play-off алгоритм может быть реализован только для поиска совпадений «от субъекта к клиенту». В обратную сторону все будет сложнее — массив не получится сокращать, он будет расти и придется для каждого совпадения считать количество совпавших элементов и сравнивать с количеством уникальных элементов адреса субъекта для которого найдено совпадение.
В итоге решено оставить проверку «от клиента» как есть, на SQL, и использовать ее только для работе «по дельте» — проверять только тех клиентов, у которых за сутки было изменение адреса. В этом режиме данных для проверки значительно меньше и время работы ее невелико (в пределах часа в среднем). А полную проверку (всех со всеми) и проверку по последнему загруженному списку запускать «от субъектов» (что и прописано в программе-запускалке).
Вот такие вот попадаются задачки…
