Дело началось с того, что одна небольшая английская компания решила рассылать рекламные листовки своим существующим и потенциальным клиентам.Обнаружилась проблема: есть отдельная внутренняя база клиентов, делавших заказы по телефону; отдельная база веб-клиентов, делавших заказы на сайте; и несколько баз «потенциальных клиентов» от разных информаторов.
Тысячи клиентов попали сразу в несколько баз, или даже несколько раз в одну базу.
Если клиент, «засветившийся» пять раз, получит пять одинаковых рекламных листовок с немного отличающимся написанием имени или адреса, то эффект от такой кампании получится противоположный — не говоря уже о бессмысленных расходах на лишние листовки.
Как же отсеять повторы в списке рассылки?
Среди всех данных о клиенте самое однозначное, что его определяет — это почтовый индекс (postcode). Этого мало, но это хорошая отправная точка.
Почтовые индексы
Индексы британской Королевской почты (Royal Mail) существенно отличаются от принятых в большинстве стран числовых почтовых индексов:
- используются буквенно-цифровые индексы, длиной от 5 до 7 символов, с пробелом посередине, — например, NW1 6XE для знаменитого адреса «221B Baker Street, London»;
- одному индексу соответствует в среднем 15 получателей (delivery points) — это примерно одна сторона улицы от перекрёстка до перекрёстка;
- почтовые индексы широко используется для геолокации, например на Google Maps: maps.google.com/maps?q=NW1+6XE позиционирует карту сразу на нужный квартал; в крупных городах, для удобства ориентирования, почтовый округ подписывают на домах вместе с названием улицы;
- индекс имеет иерархическую структуру: область (area; часть графства), округ (district; город или часть города), сектор, юнит. В нашем примере область NW соответствует северо-западному Лондону, округ NW1 — части Вестминстера и части Камдена. Пример из менее густонаселённой области: область EX (Эксетер) соответствует северной половине Девоншира, а округ EX20 — паре городов North Tawton и Okehampton и их окрестностям.
- Как можно видеть, разбиение почтовых получателей на области никак не согласуется с административным делением: многие почтовые области пересекают границы графств, а некоторые — и границы Англии. Единственное условие, по которому проводилось разбиение — примерно равное число получателей в каждой почтовой области.
Такое «расширение» индекса аналогично американскому ZIP+4; отличие состоит в том, что британские DPS не афишируются широкой публике, и большинство жителей понятия не имеют, что такое DPS, и уж тем более — какой DPS у их почтового ящика.
Единственное афишируемое применение DPS — сниженные тарифы для массовых рассылок, когда на каждом конверте отпечатан штрих-код, включающий индекс и DPS.
Мы решили, что пара «индес+DPS» устраивает нас как однозначный идентификатор адреса: хотя теоретически несколько клиентов могут иметь общий почтовый ящик (предположим, они снимают по полквартиры), а крупные клиенты могут иметь по нескольку корпусов и по отдельному почтовому ящику в каждом корпусе, — но принцип «один почтовый ящик — одна рекламная листовка» подкупает своей прозрачностью.
План действий был определён: для каждого адреса определим DPS, и если две записи совпадают по индексу и по DPS — значит, это один и тот же адрес.
Почтовые адреса
Привыкшим к жёстко структурированным советским почтовым адресам «город-улица-дом-квартира» может быть непонятно: зачем заморачиваться с DPS? Почему бы не искать повторы непосредственно в адресах?Дело в том, что британские почтовые адреса имеют очень свободную структуру, делающую невозможным их сравнение «в лоб»:
- у дома может быть несколько номеров (например, «15-17 Railway Road»); может вовсе не быть номера (например, «Safari House, Hospital Lane»);
- улица в адресе может не быть обозначена — только здание и населённый пункт; например, «Former St Mary's Church, Tremadog»;
- может быть обозначена улица и «подулица», например «Second Drive, Dawlish Road, Teignmouth» — в отличие от неё, есть и «Second Drive, Landscore Road, Teignmouth»;
- может обозначаться район города; в разных районах могут быть улицы с одинаковыми названиями. Поскольку явных границ между районами нет, каждый выбирает по собственному разумению, какой район указывать в своём адресе, и указывать ли вообще.
- почта не рекомендует указывать в адресе графство, но большинство всё равно указывают. Поскольку крупные города не подчиняются графствам, некоторые жители указывают название города дважды: один раз в качестве населённого пункта, второй раз в качестве графства.
- особая путаница с Лондоном: его могут упоминать и как «Inner London, London»; и как «London, South London»; и ещё многими способами — притом, что по почтовым требованиям большинству жителей столицы достаточно написать просто London, и указать улицу — как в примере с домом Холмса.
Почтовая база
Royal Mail официально (и незадёшево) предлагает базу всех существующих почтовых адресов — Postcode Address File (PAF). Для каждого адреса приведено «стандартное» написание, индекс и DPS. (Покупка PAF — единственный легальный способ определить DPS по адресу.) В виде заархивированного плейнтекста вся база занимает 300МБ.
«Стандартное» написание адреса поделено на логические поля: название организации, дома, улицы, населённого пункта.
Каждое из этих полей делится дальше: название организации может включать название отдела; название дома — номер или название квартиры; и так далее.
Для примера, вот три записи из PAF, относящиеся к адресам на одной улице:
| Отдел Организация |
Microwhite |
||
| Часть дома Номер дома Название дома |
Flat 3 Westwood Farm House |
Flat 16 |
76A |
| Название подулицы Тип подулицы Название улицы Тип улицы |
Main Street |
Main Street |
Main Street |
| Подрайон Район / пригород Город |
Keevil Trowbridge |
Keevil Trowbridge |
Keevil Trowbridge |
| Индекс DPS |
BA14 6LU 2P |
BA14 6LU 2W |
BA14 6ND 1J |
Распознавание адресов
Итак, у нас есть адрес клиента с индексом, и нам нужно определить его DPS. Лобовой подход — перечислить все адреса, соответствующие данному индексу, и выбрать «самый похожий» — был отвергнут из-за неизбежности «ложных срабатываний». Адреса, соответствующие одному индексу, различаются скорее всего номером или названием дома; а это именно та часть адреса, в которой альтернативные формы могут иметь мало общего одна с другой. Кроме того, нет никакой гарантии, что индекс в базе записан верно.Я решил вместо этого анализировать адрес «снизу вверх», повторяя логику чтения адреса почтальоном: сначала распознать город, затем улицу, наконец дом, и в конце концов сравнить индекс с записанным. Если индекс совпал — это довольно убедительное свидетельство того, что адрес распознан правильно.
Исходные данные в базах клиентов заполнялись в четыре поля: адрес, город, графство и индекс. Поскольку полный адрес разбивался на эти четыре поля вручную, то соответствие содержимого назначению полей было довольно неточным; длинные адреса часто заполнялись в два первых поля, вытесняя название города в поле «графство»; короткие адреса — наоборот, указывались вместе с городом в первом поле, при этом графство попадало в поле «город», а поле «графство» оставалось пустым. Всё это вызвало затруднения при распознавании адресов: непонятно, какую часть адреса сравнивать со списком городов, какую — со списком улиц, и т.д.
Другая сложность состояла в многочисленных опечатках и разночтениях в адресах. (Британская топонимика во многих вселяет ужас: «пишется Ливерпуль, а читается Манчестер»; едва ли вообще возможно записать адрес на слух по телефону без единой ошибки.) Чтобы учесть это, требовался алгоритм нечёткого сравнения строк. Гугль навёл меня на библиотеку SimMetrics для MS SQL, выпущенную Шеффилдским университетом. Испробовав несколько метрик на реальных примерах адресов, я остановил свой выбор на метрике Jaro-Winkler. Она похожа по своей идее на расстояние Левенштейна, но даёт больший вес символам в начале строк, чем в конце. Оказалось, что большинство опечаток действительно допускались во второй половине названия; в первых же двух буквах названий опечаток практически не было.
Общая архитектура моего распознавателя — каскад табличных UDF-функций, каждая из которых «откусывает» от конца адреса свой кусок, пытается его распознать, и фильтрует входные строки либо добавляет новые варианты их разбора. Первая функция рассматривает все подходящие графства, вторая — все подходящие города в этих графствах, и так далее. Получается, в ходе распознавания рассматриваются все (тысячи) возможные трактовки частично прочитанного адреса. Возможно, было бы эффективнее задействовать нечто вроде «метода ветвей и границ»: рассматривать каждый раз только самую вероятную частичную трактовку, и прекращать анализ, как только найдена подходящая полная трактовка. Я решил, что такая реализация не отвечала бы «духу» T-SQL, ориентированного на однообразную обработку массивов данных; кроме того, реализация в виде каскада независимых функций облегчает тестирование и повторное использование кода.
Распознавание графства
Итак, начинаем с конца адреса, с названия графства. По почтовым правилам, указание графства в адресе необязательно, и его при распознавании адреса можно игнорировать. Ищем в поле «графство» название графства, если находим — откусываем и возвращаем остаток. Если не находим — возможны два варианта: либо графство не указано, и нужно вернуть всю строку в качестве остатка, чтобы следующая функция нашла в ней название города; либо указано название несуществующего графства (мне встречались «South Buckinghamshire», «Central London» и даже «England»), и тогда всю строку нужно откусить — город будем искать в следующей.Пара дополнительных тонкостей — что встретиться может как полное, так и сокращённое название графства; и что если графство совпадает по названию с городом, то его не нужно откусывать — этот город нам потребуется на втором этапе.
CREATE FUNCTION Address_GetCounty(@address varchar(30))
RETURNS TABLE
AS RETURN
select distinct county, isnull(data.leftover, deflt.leftover) leftover, sim from (
select max(county) county, max(leftover) leftover, max(sim) sim from (
select top 1 county, leftover, sim
from (
select county, leftover, length, sim,
row_number() over (partition by county order by sim desc) as rn
from (
select county.name as county, left(@address,len(@address)-l.v) as leftover, l.v as length,
dbo.maxf(dbo.JaroWinkler(county.name,upper(right(@address,l.v))),
dbo.JaroWinkler(upper(county.abbrev),upper(right(@address,l.v)))) as sim
from PAF.dbo.Counties_ExceptPosttowns county, dbo.Generate(len(@address)) l
where left(right(@address,l.v),1) like '[A-Za-z]' --word boundary
and (left(right(@address,l.v+1),1) not like '[A-Za-z]' or l.v=len(@address))
) data
) data
where rn=1 and sim > 0.92
order by length desc, sim desc
union select null, null, null
) data
) data, (select @address leftover union select '') deflt
Функция Generate(n) возвращает натуральные числа от 1 до N; возможно, в современных версиях MS SQL уже есть встроенный способ сгенерировать такую таблицу.
Порог 0.92 для подобия строки образцу выбран опытным путём. Важно, что выбирается не самый «точно подходящий» вариант, а самый длинный из всех «примерно подходящих». Например, хвост строчки «Souuth Gloucestershire» точно соответствует образцу «Gloucestershire», но нам нужно откусить не его, а более длинное и менее точное соответствие образцу — «South Gloucestershire».
Распознавание населённого пункта
Второй этап — распознавание города в поле «город» и нераспознанном остатке поля «графство». Поскольку городов в Британии тысячи, то нечёткое сравнение каждого хвоста строки с каждым названием города занимает неоправданно долго. Чтобы оптимизировать поиск, мы сначала пытаемся найти точное соответствие (используя индекс), и только если точное соответствие не найдётся — выполняем нечёткий поиск. У такого подхода есть и недостаток — в случаях, подобных «Souuth Gloucestershire», найдено будет точное соответствие, а не желанное более длинное неточное. Ещё пара тонкостей: могло оказаться, что графство указано дважды (например, в форме «West Yorkshire, Yorkshire») — такое бывало, когда адрес короткий, а вводившему его хотелось заполнить все строки. Поэтому распознавание адреса начинаем с того, что пытаемся откусить ещё одно название графства, если оно достаточно точно совпадает с образцом. Другая тонкость — кроме официального списка «почтовых городов», в адресах допускаются «псевдонимы»; их Royal Mail публикует в отдельной базе Alias, которую можно докупить впридачу к PAF. (Например, вместо нормативной формы «Baker Street, London» допустимо написать «Baker Street, Westminster».) Наконец, при сравнении названий городов за один символ считаем пробел и дефис: англичанин с равной вероятностью напишет «Bradford on Avon» или «Bradford-on-Avon», но лишь один вариант написания считается нормативным.
CREATE FUNCTION Address_GetPosttownId(@address varchar(60))
RETURNS @res TABLE(local_id int, posttown varchar(30), leftover varchar(60), sim float, byalias bit)
AS BEGIN
--chip away double county, on a very good match
SELECT @address=leftover FROM Address_GetCounty(@address) WHERE sim>0.95;
INSERT INTO @res
select distinct isnull(Localities.local_id,alias.local_id) as local_id,
name.posttown, leftover, sim, byalias from (
select top 1 posttown, left(@address,len(@address)-l.v) as leftover, 1 as sim, byalias
from (select 0 as byalias, posttown from PAF.dbo.Localities
union select 1 as byalias, name from PAF.dbo.LocalityIndex) names, dbo.Generate(len(@address)) l
where left(right(@address,l.v),1) like '[A-Za-z]' --word boundary
and (left(right(@address,l.v+1),1) not like '[A-Za-z]' or l.v=len(@address))
and posttown=upper(right(@address,l.v))
order by l.v /*length*/ desc
) name
left join PAF.dbo.Localities on name.posttown=Localities.posttown
left join PAF.dbo.LocalityAliases alias on name.posttown=alias.name
IF @@rowcount!=0 RETURN;
INSERT INTO @res
select distinct isnull(Localities.local_id,alias.local_id) as local_id,
name.posttown, leftover, sim, byalias from (
select top 1 posttown, leftover, sim, byalias
from (
select posttown, leftover, length, sim, byalias,
row_number() over (partition by posttown order by sim desc) as rn
from (
select posttown, left(@address,len(@address)-l.v) as leftover, l.v as length, 0 as byalias,
dbo.JaroWinkler(replace(posttown,'-',' '),replace(upper(right(@address,l.v)),'-',' ')) as sim
from (select 0 as byalias, posttown from PAF.dbo.Localities
union select 1 as byalias, name from PAF.dbo.LocalityIndex) names, dbo.Generate(len(@address)) l
where left(right(@address,l.v),1) like '[A-Za-z]' --word boundary
and (left(right(@address,l.v+1),1) not like '[A-Za-z]' or l.v=len(@address))
) data
) data
where rn=1 and sim > 0.92
order by length desc, sim desc
) name
left join PAF.dbo.Localities on name.posttown=Localities.posttown
left join PAF.dbo.LocalityAliases alias on name.posttown=alias.name
RETURN
END
Следующая проблема, с которой я столкнулся, — в некоторых адресах указывалось сразу два почтовых города: более мелкий и более крупный; — хотя у обоих было по собственному почтовому округу: например, «Hessle, Hull». (Хессл относится к округу HU13, а к Халлу — округа от HU1 до HU12.) В этих случаях второй город надо просто игнорировать.
Иногда же почтовый город в адресе вовсе не указывался: только название района. Тогда возвращаем в качестве остатка весь переданный адрес.
CREATE FUNCTION dbo.Address_GetPosttownId_2(@address varchar(160), @town varchar(60))
RETURNS @res TABLE(local_id int, posttown varchar(30), leftover varchar(160), sim float, byalias bit)
AS BEGIN
insert into @res
select local_id, posttown, @address+' '+leftover, sim, byalias
from Address_GetPosttownId(@town);
-- multiple posttowns in address?
insert into @res
select distinct local_id, posttown, new.leftover, sim*.95, byalias
from (select distinct leftover from @res) lo
cross apply Address_GetPosttownId(dbo.rtrimna(leftover)) new
-- also try without a posttown (rare)
INSERT INTO @res VALUES(null, null, @address+' '+@town, .8, 0)
RETURN
END
Завершает распознавание населённого пункта поиск названия района/пригорода в поле «адрес» и остатке поля «город». Код там получился достаточно длинный, поэтому лишь перескажу его логику. Если почтовый город до сих пор неизвестен, пытаемся искать подходящий район во всей базе; если известен — только среди районов этого города. Если город найден по псевдониму, или у него есть безымянные районы — то имя района может быть и пустым: возвращаем весь полученный адрес в качестве остатка. Как и прежде, пришлось предусмотреть часто встречающуюся в адресах неточность — указание названия района там, где по почтовым правилам указывать его не нужно. Поэтому, если передан город с безымянными районами, и хвост адреса похож на один из его именованных районов — откусим от адреса название района, но вернём идентификатор безымянного. Признаюсь, что мой код совершенно игнорирует названия подрайонов: в реальных адресах они достаточно редки.
Распознавание улицы
Следующий этап — распознавание улицы. Ищем среди всех улиц найденного населённого пункта сначала точно совпадающую с хвостом остатка адреса, затем — примерно совпадающую. Если не удалось найти даже примерно совпадающую, и поиск вёлся в безымянном районе — попробуем поискать во всех районах того же города: возможно, в адресе забыли указать район, который по почтовым правилам необходим. Если похожей улицы не нашлось ни в одном районе, проверим ещё одну возможность, прежде чем сдаться окончательно: возможно, в выбранном районе есть адреса без улицы. Такие адреса достаточно редки, поэтому проверяем их в последнюю очередь. Псевдонимы улиц из базы Alias не проверяем вовсе: они оказываются ещё более редки.CREATE FUNCTION Address_GetThoroughfare (@local_id int, @address varchar(160))
RETURNS @res TABLE(local_id int, thfare varchar(30), thfare_id int, thdesc_id int, leftover varchar(160), sim float)
AS
BEGIN
INSERT INTO @res
select top 1 @local_id, thfare, thfare_id, thdesc_id, leftover, 1
from (
select distinct thfare, thfare_id, thdesc_id,
left(@address,len(@address)-l.v) as leftover, l.v as length
from PAF.dbo.ThoroughfareIndex, dbo.Generate(len(@address)) l
where left(right(@address,l.v),1) like '[0-9A-Za-z]' --word boundary
and (left(right(@address,l.v+1),1) not like '[0-9A-Za-z]' or l.v=len(@address))
and local_id=@local_id
and thfare=upper(right(@address,l.v))
) data
order by length desc;
IF @@rowcount!=0 RETURN;
INSERT INTO @res
select top 1 @local_id, thfare, thfare_id, thdesc_id, leftover, sim
from (
select thfare, thfare_id, thdesc_id, leftover, length, sim,
row_number() over (partition by thfare order by sim desc) as rn
from (
select distinct thfare, thfare_id, thdesc_id,
left(@address,len(@address)-l.v) as leftover, l.v as length,
dbo.JaroWinkler(thfare,upper(right(@address,l.v))) as sim
from PAF.dbo.ThoroughfareIndex, dbo.Generate(len(@address)) l
where left(right(@address,l.v),1) like '[0-9A-Za-z]' --word boundary
and (left(right(@address,l.v+1),1) not like '[0-9A-Za-z]' or l.v=len(@address))
and local_id=@local_id
) data
) data
where rn=1 and sim > 0.92
order by length desc, sim desc;
IF @@rowcount!=0 RETURN;
--try dependents
INSERT INTO @res
select dep.local_id, thfare, thfare_id, thdesc_id, leftover, sim
from PAF.dbo.Localities parent join PAF.dbo.Localities dep
on parent.posttown=dep.posttown and dep.dependent1 is not null
cross apply Address_GetThoroughfare(dep.local_id, @address)
where parent.local_id=@local_id and parent.dependent1 is null
IF @@rowcount!=0 RETURN;
--still no luck?
if exists (select 1 from PAF.dbo.Addresses_ByThoroughfare(@local_id, null, null))
INSERT INTO @res
VALUES (@local_id, null, null, null, @address, .8);
RETURN
END
Затем аналогичным образом, только без поиска в других районах, пытаемся распознать подулицу. Большинство адресов — без подулицы, поэтому теперь безымянный вариант рассматривается всегда, а не в последнюю очередь. Код функции Address_GetThoroughfare_dependent я не привожу.
Важный дополнительный бонус от использования метрики Jaro-Winkler — то, что не потребовалось составлять список сокращений для названий типов улиц (Rd=Road, Ln=Lane, Ct=Court и т.д.): выбранная метрика очень слабо падает, когда буквы пропущены в самом конце названия.
Распознавание адресата
Заключительный этап — распознавание получателя почты, включая искомый DPS, в остатке поля «адрес». Для большинства компаний название компании — необходимый элемент почтового адреса, поэтому сейчас добавим его к адресу. Логика распознавания адресата — самая запутанная часть во всём коде. Первым делом, стираем из полученного адреса слова «the»: разница в их расстановке — самое часто встречающееся расхождение между названиями домов и компаний в PAF и в реальных адресах. Пробуем найти хвост адреса среди названий домов, а также среди их частей: если в PAF определён адрес «15-17 Railway Road», то будем сравнивать хвост со строками «15-17», «15», «17». При сравнении с названиями домов отбрасываем также начальное «Flat»: в PAF оно обычно прописано перед номером квартиры, в реальных адресах — зачастую нет.
Если ни на одно из названий домов хвост не похож, пробуем найти его среди названий компаний: довольно часто название компании является «неявным» названием дома. Для сравнения названий компаний порог метрики пришлось снизить до 0.85 — расхождения между написанием названия в PAF и в адресе оказывались настолько велики.
Последнее сравнение, на случай, если нет совпадения ни с названиями домов, ни с названиями компаний — с названиями частей дома: иногда, когда собственные названия есть и у дома, и у пристройки, — в адресе указывали только название пристройки.
И вновь признаюсь, что псевдонимы домов из базы Alias не рассматривались: оказалось, что в адресах практически всегда используются «основные» названия домов.
Объединяем написанные функции в один большой запрос:
CREATE FUNCTION Address_MatchDPS (@CUNAME varchar(40), @AD_ADDRESS varchar(160),
@AD_ADDRESS_USER1 varchar(30), @AD_ADDRESS_USER2 varchar(30),
@AD_POSTCODE varchar(12))
RETURNS TABLE
AS RETURN
select distinct postcode, dps, oname
from Address_GetCounty(dbo.rtrimna(@AD_ADDRESS_USER2))
cross apply Address_GetPosttownId_2(@AD_ADDRESS, dbo.rtrimna(@AD_ADDRESS_USER1+' '+leftover)) address
cross apply Address_GetPosttownId_dependent(local_id, byalias, dbo.rtrimna(address.leftover)) dep
cross apply Address_GetThoroughfare(dep.local_id, dbo.rtrimna(dep.leftover)) tf
cross apply Address_GetThoroughfare_dependent(tf.local_id, thfare_id, thdesc_id, dbo.rtrimna(tf.leftover)) dtf
cross apply Address_GetBuilding(tf.local_id, thfare_id, thdesc_id, dbo.rtrimna(@CUNAME+' '+dtf.leftover)) bu
where postcode=isnull(@AD_POSTCODE,postcode) --AD_POSTCODE=NULL disables check
По данным клиента он находит подходящие адреса в PAF, и возвращает найденные индексы, DPS, и названия компаний. Если для одного клиента найдётся несколько записей, то вызывающая сторона попытается отфильтровать их по имени компании. (Ведь если в адресе было и название дома, и название компании, то Address_GetBuilding сравнивала только название дома; а в том же доме могли располагаться и другие компании.)
select distinct в Address_MatchDPS необходим потому, что один и тот же почтовый ящик мог быть найден различными способами — например, отбрасывая разные элементы исходного адреса.
Получившаяся в итоге функция работала со скоростью порядка 500 адресов в час, причём основное время работы, по-видимому, относилось к вызовам функции JaroWinkler; на четырёхпроцессорном сервере запуск четырёх экземпляров скрипта позволил учетверить производительность. Успешно распознались около 60% адресов; среди оставшихся были как «слишком нестандартные» формы, так и просто неверные или неполные, либо с ошибочным индексом. Теперь сотрудникам небольшой английской компании предстоить просмотреть все нераспознанные адреса вручную, и исправить неточности: база точных адресов всех клиентов стоит затраченных усилий.
