Алгоритм привязки строк к КЛАДР (original) (raw)

Рассмотрим подробнее условие предыдущей задачи: нужно разработать алгоритм привязки адресной информации, набранной пользователями вручную как попало - к фиксированному классификатору адресов КЛАДР.

Для того, чтобы вы лучше представили себе качество исходных данных, приведу пример из строчек, которым я нашел соответствие вручную:

Итак, каким же образом столь корявой, хаотичной, иногда избыточной, иногда недостаточной информации можно поставить в соответствие единственную правильную строчку из справочника? Вот такой алгоритм напрашивается изначально:

Алгоритм 1.

0. Приводим все строчки к одинаковому регистру букв (строчному и заглавному).

1. Сначала надо разобраться со знаками препинания. Как показывает практика, запятые и точки в адресах ставятся как попало, зачастую они заменяют и друг дружку, и пробел. Например "Г.ЛИПЕЦК,УЛ. НЕДЕЛИНА". То же самое с некоторой натяжкой можно сказать и про дефис. Однако, если мы просто удалим точки и запятые из строк - слова сольются и у нас получится "ГЛИПЕЦКУЛ НЕДЕЛИНА" - поэтому вместо удаления, заменяем их на пробелы: "Г ЛИПЕЦК УЛ__НЕДЕЛИНА" А чтобы после такой замены не было разночтений, заменям в строке все сдвоенные пробелы на одинарные: "Г ЛИПЕЦК УЛ НЕДЕЛИНА".

2. Теперь надо очистить строки от мусора - то есть, от тех элементов, которые будут мешаться сравнению. В первую очередь, это адресные идентификаторы "с", "село", "г", "ул" - и другие. Они мешаются, потому что мы никогда не сможем упорядочить, чтобы "ул" стояло перед своим названием, в не после него. Тот же самый "район" можно написать как "район", "р-он" или "р-н". Каким же образом можно выделить из строк "мешающиеся" элементы?

Вариант 2.1 - завести перечень адресных сокращений, и удалять совпадающие с ними части строк. Правда, как этот перечень составить? Например, официальный классификатор, поставляющийся вместе с КЛАДРом содержит только единственный вариант написания слова "район": "р-н".

Тут видятся два варианта - либо вычислить частоту вхождения тех или иных слов в адресные строки, либо составить классификатор на основе собственных эмпирических данных (то есть просмотреть глазами список и выписать встречающиеся сокращения на бумажку). Полученный список можно хранить в виде отдельной таблицы, а можно встроить в процедуру обработки строк.

Замечу, что просто так "вслепую" удалять сокращения из строк нельзя - надо производить удаление только целых слов, в том числе расположенных в начале или в конце строки - иначе вы рискуете лишиться всех букв "г" и "с", встречавшихся в адресе.

Вариант 2.2 - удалить все слова меньшие определенной длины. Этот вариант хотя и проще (не нужно возиться со справочниками) - но здесь теряется слишком много полезной информации, и остаётся слишком много мусора. Даже если мы удалим все слова, длиной меньше пяти символов, мы напрочь потеряем "ул. 9 мая", зато оставим слова "район" и "поселок".

3. В каждой строке КЛАДРа присутствует индекс (например "398001"), а в исходной адресной информации индекс отсутствует. Значит, перед сравнением строк индекс нужно удалить. Зато в исходной информации присутствуют номера домов (например "55" или "32А"), которых, естественно нет в КЛАДРе. Значит, номера домов тоже нужно удалить. Напрашивается решение - удалить все слова, начинающиеся с цифры.

Правда, это может сделать для нас одинаковыми улицы "ул. 1-я садовая" и "ул. 2-я садовая". Или улицы "30 лет октября" и "40 лет октября" - да, да, в одном городе! :) Будем считать это погрешностью алгоритма.

4. Но и это еще не всё. К сожалению, то что принято считать номером дома, не обязательно начинается с цифры. В примерах мы видим, что в качестве номеров домов могут выступать надписи "Здание магазина" или "Район цемзавода". Почему они считаются номерами домов? Потому что про них ничего не в КЛАДРе. Текст, который идёт до них - задает общеизвестный населенный пункт, территорию или улицу, а правая часть надписи лишь расшифровывает, уточняет адрес. Иными словами, текст адреса может содержать справа сколь угодно большой объем дополнительной информации, не привязанной к КЛАДРу.

К сожалению, про КЛАДР можно сказать то же самое: он может содержать дополнительную информацию слева. И дело даже не в индексе и названии области - "399774 Липецкая обл" - их всегда можно искуственно удалить. Дело в названии района. Очень часто при вводе данных руками, районные центры указываются без указания района, к которому они относятся - дескать, что тут непонятного?! Вот и получается: у нас "г. Елец", а в КЛАДРе - "Елецкий р-н, г. Елец". В то же время, информацию о районе удалять из адресной строки нельзя. Например, "деревня Ивановка" у нас есть практически в каждом районе области.

5. Таким образом, мы приходим к выводу, что соответствие нужно устанавливать между левой частью строки адреса и правой частью записи КЛАДРа. Например, для адреса "г. Лебедянь ул. Елецкая - Здание магазина", это будет соответствие между строкой "лебедянь елецкая здание магазина" и записью - "липецкая лебедянский лебедянь елецкая". Как сформулировать условие такого соответствия на языке SQL? Оператор LIKE тут не поможет, регулярных выражений в Oracle 8i еще нет..

Заметим, что в предыдущем примере запись КЛАДРа "липецкая лебедянский лебедянь", отождествляющая целиком город Лебедянь - тоже удовлетворяет нашему правилу сравнения. Таким образом, нужно вводить некоторую количественную меру совпадения строк - чтобы определить, какая из частично совпавших записей наиболее подходит с анализируемой строке.

Наиболее простым в этом случае будет решение - написать собственную функцию, сравнивающую строчки подобным образом, и в качестве меры похожести использующую количество совпавших символов. Например, для этого можно постепенно отбрасывать символы с конца исходной строки, до тех пор, пока получившаяся строка не будет содержаться в какой-либо записи КЛАДР.

Если таких записей несколько - выберем наиболее короткую. Такое может случиться, если строка задает несуществующую улицу. Например, если в г.Лебедянь нет ул.Ситцевой, то следующие записи КЛАДРа будут иметь одинаковое количество совпавших символов со строкой "лебядянь ситцевая": "липецкая лебедянский лебедянь", "липецкая лебедянский лебедянь елецкая". Выбрать в этом случае нужно запись, отождествляющую г.Лебедянь целиком.

Результаты: разработав и запустив этот алгоритм на 2000 адресных строк, и проведя визуальный контроль результатов, мы получили около 500 ошибок - то есть 25%. Рассмотрев подробнее характерные примеры, приведенные в начале статьи, видим:

Как видно, основной недостаток алгоритма - то, что каждое следующее слово для него менее значимо, чем предыдущее. Кроме того, алгоритм игнорирует различия между служебными словами КЛАДРа: "проспект Победы" и "площадь Победы" для него одно и то же. Постараемся учесть все эти недостатки во втором варианте алгоритма.

Алгоритм 2.

0-1. Эти начальные шаги обработки строк аналогичны алгоритму 1.

2. На этот раз мы не будем удалять служебные слова КЛАДРа из строк - напротив, они помогут нам отличать площадь от проспекта. Мы вообще не будем никаким специфическим образом "чистить" информацию. Алгоритм будет довольно универсальным, и может быть применим для поиска соответствия любых строк.

Если к недостаткам прошлого алгоритма можно было отнести то, что ему требовался список служебных слов КЛАДРа для исключения их из строк - то этому алгоритму такой список не нужен. Зато нам понадобятся две временные таблички, в которые мы будем разбирать на слова анализируемые строки адреса и записи КЛАДРа. Итак:

3. Разбираем анализируемую строку и каждую запись КЛАДРа на слова. Каждое слово заносим в соответствующую таблицу. При этом в поле OBJ - заносим числовой код, позволяющий однозначно идентифицировать запись КЛАДРа. Как видно из первичного ключа, если в строке два раза встречается одно и то же слово, оно должно быть занесено в таблицу лишь однажды. Само слово (приведенное к одному регистру) заносится в колонку WORD.

В колонку LEN заносится длина слова (предполагается, что взять длину из таблицы быстрее, чем вычислять её по строке). В колонку CNT заносим номер символа, означающий позицию в разбираемой строке, на которой заканчивается текущее слово. Эти данные пригодятся позже - когда нужно будет выделить правую часть строки, для которой не было найдено соответствия в КЛАДРе - в качестве поля "Номер дома".

4. Самое "загадочное" поле - SOUND. Это некий четырехсимвольный хэш слова, построенный по алгоритму Soundex, впервые предложенному Робертом Расселом и Маргарет Обелл в 1918(!) году (подробнее - здесь). Ключевая особенность алгоритма - для созвучных слов он возвращает одинаковые хэши.

До сих пор большие дискуссии вызывает применимость алгоритма Soundex для русских слов. Сам алгоритм понимает только буквы латинского алфавита, и рассчитан на английскую фонетику - поэтому, если пытаться применить его к русским словам, в первую очередь необходимо получить их английскую транскрипцию. И чем правильнее это будет сделано, тем правильнее будет обрабатывать эти слова Soundex.

Самым примитивным образом это можно сделать так: TRANSLATE( UPPER(xCurWord), 'ЙЦУКЕНГШЩЗХЪФЫВАПРОЛДЖЭЯЧСМИТЬБЮЁ', 'ICUKENGQQZHWFWVAPROLDJEAQSMITWBUE'); Однако, для более качественной транскрипции рекомендую разработать (и опубликовать ;-) собственную функцию.

Для слов, начинающихся с цифр Soundex возвращает null. Такие результаты записывать в таблицу не будем. Такие образом, мы снова игнорируем слова начинающиеся с цифр - как в пункте 3 предыдущего алгоритма.

Для тестирования созвучности слов с точки зрения алгоритма soundex, проведем следующее испытание:

Как видим, алгоритм прекрасно понял, что "район", "р-н", "р-он" - одно и тоже, но зато "пл", "пр" и "пр-кт" с его точки зрения это три разных слова. Вообще-то он прав, так как "пр" с точки зрения словаря сокращений КЛАДРа - это "проезд", а вовсе не "проспект". Только вот в большинстве наших адресов, и "проезд" и "проспект" обозначаются одинаково "пр". Я еще не встречал, чтобы в городе были проспект и проезд с одинаковыми названиями. А вот одноименные проспект и площадь - встречаются регулярно.

Самым простым решением, в этом случае будет замена слова "пр" на "пр-кт" на этапе 2 (перед помещением во временные таблицы) - как в исходных адресах, так и в записях КЛАДРа. Это избавит программу от путаницы между адресами вида "г. Липецк пл. Победы", "г. Липецк пр. Победы" и "г. Липецк пр-кт. Победы".

Soundex прекрасно справился с орфографической ошибкой в слове "Преображение", не спутал "Добринский" и "Добровский" районы. Зато, по его мнению, улицы "Московская" и "Маяковского" - абсолютно созвучные. Это говорит нам о том, что исключительно на Soundex полагаться нельзя. Из двух созвучных слов - предпочтение нужно отдать слову со схожим написанием.

5. Теперь перейдём непосредственно к алгоритму сравнения строк. Сравнивая две строки адресной информации, преобразованные в пунктах 0-4 данного алгоритма к наборам слов, мы можем получить следующие числовые характеристики похожести/непохожести строк:

5.1 "Количество созвучных слов в строке А и строке Б". Поскольку в одной строчке может быть несколько слов с одинаковым звучанием, чтобы избежать повторения перестановок, определим этот показатель более узким образом: "Количество уникальных созвучий, имеющихся одновременно в строке А и в строке Б".

5.2 Наряду с этой характеристикой, также можно рассмотреть показатель "Суммарная длина слов, уникальные созвучья которых, имеются одновременно в строке А и в строке Б". Длины созвучных слов стоит складывать из поля LEN таблицы TMP_WORDS_KLADR, так как в этой таблице слова более соответствуют эталонным.

5.3 "Количество полностью совпадающих слов между строками А и Б". Тут перестановок быть не может, так как поле "Слово" входит в первичные ключи таблиц, наряду с числовым идентификатором разбираемой строки.

5.4 "Суммарная длина слов, полностью совпавших в строках А и Б". Этот показатель по простоте напоминает числовую характеристику, использовавшуюся в прошлом алгоритме.

5.5 и 5.6 "Общее количество слов в данной записи КЛАДРа." и "Общая длина строки данной записи КЛАДРа" - эти показатели помогут выбрать соответствующую строку, если значения всех остальных их характеристик совпадают.

6. Утверждается, что используя данные 6 показателей, можно построить достаточно эффективный алгоритм сопоставления строк. Я предлагаю применять их в следующем порядке:

6.1 Сначала выбираем записи с максимальной длиной полностью совпавших слов.

6.2 Среди найденных строк, выбираем те, у которых наибольшая длина созвучных слов

6.3 Если в результате опять получилось несколько строк - выбираем строки с наименьшей общей длиной.

6.4 Честно говоря, даже в этом случае у вас может получиться несколько строк - в КЛАДРе встречаются записи с одинаковой улицей и городом, но разными индексами. В этом случае берем первую попавшуюся строку.

7. Попробуем обосновать выбранный алгоритм. В первую очередь сомнение вызывает вопрос, какой критерий использовать первым: наибольшую длину совпавших или созвучных слов? У меня получались примерно одинаковые результаты в обоих вариантах работы.

Если слова созвучны - это еще не значит, что они одинаковые (см. пример ул. Московская/Маяковского). А вот если слова совпадают - значит они совпадают. Правда, если слова не совпадают, это ещё не значит что они разные. ;) Будем исходить из принципа гарантированного результата, и ориентироваться в первую очередь именно на длину совпавших слов. А лишь среди них - выбирать наибольшее число созвучных.

Замечу, что вместо "количества" я везде использую "длину". Сейчас я приведу пример, почему это предпочтительнее: рассмотрим строку "Добринский район с. Алексеевка ул. Ленина". Но в КЛАДРе в селе Алексеевка нет улиц, есть только запись соответствующая всему селу: "Добринский район с. Алексеевка". Зато улица Ленина есть в селе Добринка: "Добринский район с. Добринка ул. Ленина":

Как видно из таблицы, критерий суммарной длины совпавших слов, в этом случае более достоверен, чем их количество. В этом случае мы не считаем все слова "равноценными", а на числовую характеристику совпадения влияет "вес" каждого совпавшего слова.

Финальный отбор по наименьшей общей длине строки нужен для отбразывания излишней детализации. Например, если в г. Лебедянь нет ул. Ситцевой (и нет созвучной ей улицы), то из двух записей "Лебедянский район г. Лебедянь" и "Лебедянский район г. Лебедянь ул. Елецкая" будет выбрана именно первая:

8. В общем виде для работы с табличками TMP_WORDS_SRC и TMP_WORDS_KLADR, sql запрос сопоставляющий строки выглядит следующим образом. В качестве результатов он выдает z_eq - код разбираемой строки, k_eq - код соответствующей ей строки КЛАДРа, len_sovp_eq - суммарная длина полностью совпавших слов, len_sovp_ne - суммарная длина созвучных слов, len_total - общая длина выбранной записи КЛАДРа.

Выбор наиболее подходящей записи осуществляется благодаря аналитическим функциям ранжирования, доступным в Oracle 8i. Без них осуществить выборку совпавших строк в одном sql-запросе было бы существенно тяжелее.

select * from ( select z_eq, k_eq, len_sovp_eq, len_sovp_ne, len_total, RANK() OVER(PARTITION BY z_eq ORDER BY len_sovp_eq DESC, len_sovp_ne DESC, len_total ASC, k_eq ASC) rank from ( select words_od_zd_eq.z_eq, words_od_zd_eq.k_eq, words_od_zd_eq.count_sovp_eq, words_od_zd_eq.len_sovp_eq, words_od_zd_ne.count_sovp_ne, words_od_zd_ne.len_sovp_ne, total_words_kladr.count_total, total_words_kladr.len_total from -- вычисляем общие характеристики каждой записи КЛАДРа ( select k.obj, count() count_total, sum(len) len_total from tmp_words_kladr k group by k.obj ) total_words_kladr, -- проверяем все пары слов на созвучность ( select z_ne, k_ne, count() count_sovp_ne, sum(len) len_sovp_ne from ( select z.obj z_ne, k.obj k_ne, max(k.len) len from tmp_words_src z, tmp_words_kladr k where z.sound=k.sound group by z.obj, k.obj, k.sound ) group by z_ne, k_ne ) words_od_zd_ne, -- проверяем все пары слов на равенство ( select z.obj z_eq, k.obj k_eq, count(*) count_sovp_eq, sum(k.len) len_sovp_eq from tmp_words_src z, tmp_words_kladr k where z.word=k.word group by z.obj, k.obj ) words_od_zd_eq where total_words_kladr.obj = words_od_zd_ne.k_ne and words_od_zd_eq.k_eq = words_od_zd_ne.k_ne and words_od_zd_eq.z_eq = words_od_zd_ne.z_ne ) ) where rank=1

Применение данного алгоритма на практике показало довольно низкий процент ошибок: из 2000 записей, ручной корректировке подверглись не более 60 штук, что составляет всего лишь 3% от всей выборки.

• На придумывание и программирование обоих алгоритмов у меня ушла одна ночь.
• На применение второго алгоритма на практике, и чистку данных - еще одна ночь.
• На то, чтобы написать эту статью - потребовалось три ночи. ;-)