Распознавание почтовых адресов

    Дело началось с того, что одна небольшая английская компания решила рассылать рекламные листовки своим существующим и потенциальным клиентам.
    Обнаружилась проблема: есть отдельная внутренняя база клиентов, делавших заказы по телефону; отдельная база веб-клиентов, делавших заказы на сайте; и несколько баз «потенциальных клиентов» от разных информаторов.
    Тысячи клиентов попали сразу в несколько баз, или даже несколько раз в одну базу.
    Если клиент, «засветившийся» пять раз, получит пять одинаковых рекламных листовок с немного отличающимся написанием имени или адреса, то эффект от такой кампании получится противоположный — не говоря уже о бессмысленных расходах на лишние листовки.
    Как же отсеять повторы в списке рассылки?

    Среди всех данных о клиенте самое однозначное, что его определяет — это почтовый индекс (postcode). Этого мало, но это хорошая отправная точка.

    Почтовые индексы


    Индексы британской Королевской почты (Royal Mail) существенно отличаются от принятых в большинстве стран числовых почтовых индексов:
    1. используются буквенно-цифровые индексы, длиной от 5 до 7 символов, с пробелом посередине, — например, NW1 6XE для знаменитого адреса «221B Baker Street, London»;
    2. одному индексу соответствует в среднем 15 получателей (delivery points) — это примерно одна сторона улицы от перекрёстка до перекрёстка;
    3. почтовые индексы широко используется для геолокации, например на Google Maps: maps.google.com/maps?q=NW1+6XE позиционирует карту сразу на нужный квартал; в крупных городах, для удобства ориентирования, почтовый округ подписывают на домах вместе с названием улицы;
    4. индекс имеет иерархическую структуру: область (area; часть графства), округ (district; город или часть города), сектор, юнит. В нашем примере область NW соответствует северо-западному Лондону, округ NW1 — части Вестминстера и части Камдена. Пример из менее густонаселённой области: область EX (Эксетер) соответствует северной половине Девоншира, а округ EX20 — паре городов North Tawton и Okehampton и их окрестностям.
    5. Как можно видеть, разбиение почтовых получателей на области никак не согласуется с административным делением: многие почтовые области пересекают границы графств, а некоторые — и границы Англии. Единственное условие, по которому проводилось разбиение — примерно равное число получателей в каждой почтовой области.
    Каждому получателю присвоен двухсимвольный DPS (delivery point suffix) — вместе с индексом он однозначно определяет почтовый ящик, в который осуществляется доставка почты. Например, дом Шерлока Холмса получил почтовый ящик NW1 6XE 1F.
    Такое «расширение» индекса аналогично американскому ZIP+4; отличие состоит в том, что британские DPS не афишируются широкой публике, и большинство жителей понятия не имеют, что такое DPS, и уж тем более — какой DPS у их почтового ящика.
    Единственное афишируемое применение DPS — сниженные тарифы для массовых рассылок, когда на каждом конверте отпечатан штрих-код, включающий индекс и DPS.

    Мы решили, что пара «индес+DPS» устраивает нас как однозначный идентификатор адреса: хотя теоретически несколько клиентов могут иметь общий почтовый ящик (предположим, они снимают по полквартиры), а крупные клиенты могут иметь по нескольку корпусов и по отдельному почтовому ящику в каждом корпусе, — но принцип «один почтовый ящик — одна рекламная листовка» подкупает своей прозрачностью.

    План действий был определён: для каждого адреса определим DPS, и если две записи совпадают по индексу и по DPS — значит, это один и тот же адрес.

    Почтовые адреса

    Привыкшим к жёстко структурированным советским почтовым адресам «город-улица-дом-квартира» может быть непонятно: зачем заморачиваться с DPS? Почему бы не искать повторы непосредственно в адресах?

    Дело в том, что британские почтовые адреса имеют очень свободную структуру, делающую невозможным их сравнение «в лоб»:
    1. у дома может быть несколько номеров (например, «15-17 Railway Road»); может вовсе не быть номера (например, «Safari House, Hospital Lane»);
    2. улица в адресе может не быть обозначена — только здание и населённый пункт; например, «Former St Mary's Church, Tremadog»;
    3. может быть обозначена улица и «подулица», например «Second Drive, Dawlish Road, Teignmouth» — в отличие от неё, есть и «Second Drive, Landscore Road, Teignmouth»;
    4. может обозначаться район города; в разных районах могут быть улицы с одинаковыми названиями. Поскольку явных границ между районами нет, каждый выбирает по собственному разумению, какой район указывать в своём адресе, и указывать ли вообще.
    5. почта не рекомендует указывать в адресе графство, но большинство всё равно указывают. Поскольку крупные города не подчиняются графствам, некоторые жители указывают название города дважды: один раз в качестве населённого пункта, второй раз в качестве графства.
    6. особая путаница с Лондоном: его могут упоминать и как «Inner London, London»; и как «London, South London»; и ещё многими способами — притом, что по почтовым требованиям большинству жителей столицы достаточно написать просто London, и указать улицу — как в примере с домом Холмса.
    Согласитесь, что автоматически определить тождественность «221B Baker Street, London NW1 6XE» и «Sherlock Holmes Museum, Baker St, Westminster, Greater London NW1 6XE» — непосильная задача. А ведь тот же дом мог быть указан и в составе «многодомного» адреса, например 219-221B

    Почтовая база


    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
    Этот пример дополнительно иллюстрирует иерархию почтовых индексов: почтовая область BA включает город Бат и часть графств Сомерсет и Уилтшир; округ BA14 — город Троубридж и окрестные посёлки; сектор BA14 6 — десяток деревень к востоку от Троубриджа, и в их числе Кивил.

    Распознавание адресов

    Итак, у нас есть адрес клиента с индексом, и нам нужно определить его 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% адресов; среди оставшихся были как «слишком нестандартные» формы, так и просто неверные или неполные, либо с ошибочным индексом. Теперь сотрудникам небольшой английской компании предстоить просмотреть все нераспознанные адреса вручную, и исправить неточности: база точных адресов всех клиентов стоит затраченных усилий.
    Share post

    Comments 57

      –2
      Согласитесь, что автоматически определить тождественность «221B Baker Street, London NW1 6XE» и «Sherlock Holmes Museum, Baker St, Westminster, Greater London NW1 6XE» — непосильная задача.

      Не соглашусь, неудачный пример.
        +4
        Хм… Не могу с вами согласится. Здесь скорее всего, вы говорите об этом со стороны простого человека, у которого в мозгу прокручивается достаточно много информации и поэтому вам легко определить что Музей Шерлока Холмса и Бэйкер стрит 221Б тождественны.
          +1
          Я не буду сравнивать Музей Шерлоко Холмса с 221Б
          используются буквенно-цифровые индексы, длиной от 5 до 7 символов, с пробелом посередине, — например, NW1 6XE для знаменитого адреса «221B Baker Street, London»;

          Ищем буквенно-цифровой индекс длинной от 5 до 7 символов с пробелом посередине и сравниваем.

          Иной вопрос, что задача полностью это адрес + номер ящика (получателя) или без индекса вообще.

            +7
            Дело в том, что NW1 6XE — это не только музей Холмса, а ещё штук двадцать домов на той же улице.
              –5
              Я бы написал,
              Согласитесь, что определить тождественность delivery points (dps) для адресов «221B Baker Street, London NW1 6XE» и «Sherlock Holmes Museum, Baker St, Westminster, Greater London NW1 6XE» — непосильная задача.
        +1
        Несмотря на уникальную систему индексов, барда и правда ещё тот. А всё пресловутый английский консерватизм и упрямство. Удивлён почему до сих пор не заставили всех дописывать DPS к индексу. 2 лишние буквы никого не обременят, а мороки на порядок меньше.
          +1
          Почему-то посетила мысль — вот что бывает если заранее не позаботиться о структуре и информативности базы.
            +1
            Да, ввели postcode не так давно (в 1959 году), чтобы не задумываться об этом.
            +5
            Ну вот есть у нас в России индекс, город, улица, дом, квартира. Всем все понятно, никакой неоднозначности и «свободной структуры», а почта и даже элементарные извещения как не ходили так и не ходят :(
              +3
              Может разница в приставке — «Royal» и «пролетарская» унитарное предприятие… Такое и отношение.
                0
                По-моему, это просто английская чопорность, а не royal :).
                  0
                  А вот мне кажется, что это ой как взаимосвязано. Если задуматься, то нафиг эта королева им сдалась? Толку от неё — ноль. Ан-нет, почему-то держатся. Стиль жизни определяет сознание и наоборот. Они конечно не фанатично преданы двору, как скажем в Таиланде, скорее с юмором, но это тоже важная черта, и без неё всё бы было по-другому.
                0
                Вовсе не везде у нас есть улицы. Кое-где вместо улиц всякие блоки, или вообще адреса типа «145-18». Или «Дом 15/2 строение 3». Или один адрес, а по нему несколько зданий.
                  0
                  В некоторых городах даже один дом может иметь два разных адреса. Например, г. Волжский в Волгоградской области. Там есть два способа адресации: обычный (ул. Советская, д. 21) и через микрорайоны (м/р 17, д. 35)- и это может быть один и тот же дом. Адреса взяты с потолка, для примера.
                    0
                    Да, кстати, у нас на угловых домах бывает два адреса. Новосибирск.
                      0
                      Возьмите Зеленоград — во всем городе нет улиц=)
                        0
                        Там же еще и корпусов по 1000:(
                          0
                          да это страшный сон почтальонов
                  0
                  Не всё так просто, есть ещё абонентские ящики, спецучреждения, воинские части, шахты...
                  195220 Санкт-Петербург, а/я 159
                  Карелия УМ-220/7 г. Сегежа
                  Алтайский край ИЗ-17/1 г. Барнаул
                  Коми К-231/1 Крутоборка
                  Кемеровская обл. УН-1612/43 шахта Ягуновская
                  в/ч 42664, город Знаменск Астраханской обл.
                    0
                    с ящиками всё просто — письмо остается на почте, попадает только в определенный ящик.
                    с учреждениями — приходит письмо в приемную (смотря кто занимается этими делами) учреждения — и далее следует внутри организации до получателя.

                    А извещения приходится забирать самому на почте — приносят, но кто-то обязательно в ящике покопошится :(
                    +1
                    Я одно время жил по адресу без улицы и подъезда, да ещё и в 401 корпусе :), а сейчас живу по адресу без улицы.
                      0
                      Ну как, почитайте у Лебедева, есть города, где нумерация не по дому, а по подъездам (Калининград), адреса не по улицам, а по микрорайонам или жилым комплексам (вплоть до того, что житель и не знает названия своей улицы).
                      +1
                      Привыкшим к жёстко структурированным советским почтовым адресам «город-улица-дом-квартира» может быть непонятно: зачем заморачиваться с DPS?

                      Единственный, на мой взгляд, и наиболее адекватный вариант работы с базой российских адресов — это сопоставление их КЛАДРом. В случае же произвольного написания адреса, никакая изначально понятная структура не поможет выявить совпадающие адреса, особенно если учесть ошибки в написании.
                        +3
                        Вы зря, поможет. В бывшем непосредственный участник такого проекта. Очень и очень интересная тема.
                        Начинал работать программистом в небольшой конторке, которая реализовала похожий механизм для Почты России.

                        Неопределенностей в российской системе, поверьте, предостаточно. Характер этих неопределенностей от английских (ужас, простихоссподи), несомненно, отличается, но своих перлов хватает.
                        При мне (7 лет назад, помоему) ребята добились верности распознавания порядка 60% на наборах от 100К записей. Сейчас, насколько я слышал, уже больше 80-90%. Выше показателей добиться сложно уже алгоритмически, сажают людей.

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

                        Сейчас система успешно внедрена и работает в промышленных масштабах, на ее основе строятся еще всякие приблуды, но подробности мне неведомы уже…
                          0
                          КЛАДР, кстати, та еще помойка:) Пока писали эту систему пинали людей, за него отвечающих, дабы самые безумные уже косяки исправлялись хотябы. Правда это давно было, может и изменилось уже чего.
                            +1
                            Знаете, есть такая поговорка: «Безобразно, но однообразно» ;) Это про КЛАДР. Налоговая сейчас с КЛАДРом работает, по крайней мере его заставляют использовать при подготовке отчетности.

                            А что касается распознавания адресов, спорить не буду, если база уже есть, с ней нужно что-то делать и 60% и более — хороший результат. Главное, чтобы затраты на приобретение готовой системы или написание собственной окупались.
                              +1
                              :) налоговые это одни из главных клиентов у них сейчас, помоему. И уже не 60%.

                              А баз этих стоооооолько… Начиная от 100-200 убитых енотов за 100К нерелевантных невыверенных записей, заканчивая 1-2К за 30К высококачественных узкоспециализированных. Соответственно, даже если отвлечься от «великой цели помощи госконторам», заработать на таком решении несложно.

                              Никогда бы не подумал, что существует такое количество тем/людей, так или иначе нуждающихся в таких системах. В свое время я сильно и долго удивлялся осознавая какое широкое поле возможностей (как технических, так и финансовых) лежит прямо перед глазами. Но, впрочем, это верно для любой области.
                            0
                            Если честно, написал коммент не прочитав топик до конца, может оттого он и получился неоднозначным. Идея была в том, что данные в базу вводить нужно по КЛАДРу (или по любой другой полной базе адресов, КЛАДР как пример) с поверкой. Это будет значительно дешевле ;)
                              0
                              Это верно только если система узкоспециальная.

                              Потом этот список устаревает практически ежедневно, поддерживать его постоянно в актуальном состоянии задача неподъемная (если говорим хотя бы о среднем городе с 500К жителей) совершенно однозначно.

                                0
                                Не совсем понял суть коммента? Тот же пресловутый КЛАДР постоянно обновляется. Накатывай обновления и порядок. Или я не о том?
                                  0
                                  Лушче бы он, мля, не обновлялся вообще. Качество и количество «левака» с обновлением возрастает незначительно, но допиливать и перепиливать систему к этим «улучшениям» приходилось долго и муторно.
                                    0
                                    понятно ;) Т. е. я правильно Вас понял, что несмотря на то, что налоговая требует использовать КЛАДР при составлении отчетности, они потом ее (отчетность) прогоняют через систему распознавания чтобы получить «правильные» адреса?
                                      0
                                      Вполне вероятно.
                                      Я, скажем так, не уверен на 100%, что они именно по такой схеме работают, но знаю точно, что налоговая пользует вот это решение.
                                      На каком этапе не скажу, но приведенная вами схема, хехе, совсем не противоречит тому, что я о них слышал;)

                                        +1
                                        Напоминает старую историю одного айтишника, которому, работая в каком-то фонде, после изменения законодательства пришлось решать задачу срочной печати тонн отчетности за несколько лет. Налоговая ни в какую не соглашалась принимать ее в электронном виде. Были закуплены большие и дорогие принтеры, куча бумаги и все это долго печаталось. А после сдачи, к нему же обратился знакомый с просьбой помочь написать систему распознавания бумажной отчетности для налоговой. И он был сильно удивлен, когда увидел чья это отчетность…
                                      0
                                      Кстати, а что за контора не подскажите? Вдруг когда-нибудь пригодиться…
                                        0
                                        Ага, вижу комментом выше. Спасибо! ;)
                                          0
                                          Там кстати снизу ссылочка такая забавная на нечто под названием «ГНИВЦ ФНС России»:)
                                            0
                                            жжоте ;)
                                              0
                                              У них и SAAS по этому делу реализован.
                                              Если мне память не изменяет. Намного удобней его подцепить, а не интегрировать решение.
                                              Одно дело базу прочистить, а другое в процесс встроить
                            0
                            Сколько времени, приблизительно, было потрачено на решение?
                              +1
                              Чуть больше двух недель.
                              Время на решение было жёстко ограничено, поэтому код и получился таким растрёпанным.
                                0
                                Если база продолжает пополняться, имхо, было бы разумно прикрутить распознавание на входе, чтобы сразу править ошибки и в дальнейшем уже не пришлось лопатить все что накопилось. Кстати, а большая база? В том смысле, насколько адекватен выход 60%.
                                  +1
                                  Распознавание на входе тоже прикрутили :)

                                  Адресов — десятки тысяч.
                                  60% — это мало, но коммерческие распознаватели адресов, которые твикали годами, дают лишь около 75%, настолько всё плохо в базе :)
                                    0
                                    Как и в любой другой базе, где нет строгой проверки вводимых данных.

                                    Я уже писал в комменте выше про КЛАДР, только это нужно сразу вводить — на этапе проектирования базы или точнее клиента для нее, т. е. не допускать ввода адреса руками. Видел реализацию в одной компании, ввод адреса мягко говоря не очень удобен, но занимает не настолько много времени, чтобы считать его неприемлемым, а профит получается несравнимо выше затрат: порядок в базе, правильные адреса при рассылке корреспонденции, правильные налоговые выплаты и т. п.
                                      0
                                      Самое интересное начинается когда разговор заходит о «примерно совпадает»… Вот тут уже тааакой простор для фантазии и для игры с весовыми коэффициентами нечеткой логики.
                                      Имхо, самая интересная из задач при построении подобных систем.
                                        0
                                        Адрес доктор и юнисерв тоже не справились с вашей помойкой? =)

                                        Вообще в массовом обслуживании 60-75% не результат, так как ручная обработка 5% стоит столько что процесс удорожает в разы.
                                  +3
                                  Мойст кинулся вниз по лестнице, и Лорд Ветинари действительно оказался в Отделе Слепых Писем с ногами на столе, пачкой писем в руках и улыбкой на лице.

                                  — А, Липовиг, — сказал он, взмахнув неряшливыми конвертами. — Прекрасный материал! Лучше, чем кроссворды! Мне вот этот нравится: «Песивотруши Шопротиф Авдекоря». Я внизу приписал правильный адрес.

                                  Он передал письмо Мойсту. Там было написано «К. Вистлер, Пекарь, Свинарный Холм, дом 3».

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

                                  Терри Пратчетт, «Making Money»

                                  Вот это распознавание :)
                                    0
                                    Только начав читать раздел «Почтовые адреса» я понял, что речь идет не о email'ах :)
                                      0
                                      Еще хотелось бы задать вопрос про так называемую «обратную ошибку»
                                      Не считали?
                                      Суть примерно такая.
                                      Система распознала адрес и говорит — Все ОК — это вот здесь.
                                      При этом на самом деле имелось в виду совсем другое место.
                                      Понятно что для не персонализированной рекламной рассылки это не сильно критично, а вот получить в свой ящик письмо с обращением «Уважаемая мисс Марпл..» Уже ущерб компании.

                                      А если в письме какие то закрытые данные типа выписки со счета или еще что то — то это уже не ущерб, а судебный убыток…
                                        +1
                                        Кстати, так и не увидел, как они разбираются с одинаковыми названиями улиц в одном городе.
                                        Моя первая поездка в Лондон украсилась приключением с поиском моей гостиницы, которая располагалась на London Street — оказывается, улиц с таким названием в Лондоне две — в City of London и в City of Westminster, причём одна в самом центре, а другая — рядом с Гайд-Парком, то есть тоже не на окраине. Таксист привёз меня сначала не на ту улицу, хотя я ему сказал, что мне нужно в Paddington.
                                          0
                                          Может быть таксисты в Лондоне просто берут пример с таксистов Тайланда?;)
                                            0
                                            А что с таксистами в Таиланде?
                                              0
                                              Если не знать точный маршрут визуально (не быть в состоянии проследить насколько верно вас везут) есть очень большая вероятность проехать с таксистом расстояние, в 2-3 раза превыщающие длину оптимального маршрута.
                                              Рекомендуют, хехе, садясь к таксисту сразу доставать GPS и без стеснения тыкать в него при малейшем сомнении в верности выбранного водителем маршрута.
                                            +1
                                            Если под «как они разбираются» вы имеете в виду мой распознаватель, то объясню.
                                            Если в адресе не указано название района, то на этапе распознавания улицы будут найдены оба варианта; затем, возможно, один из них будет отвергнут, если дом с указанным номером существует только на одной из этих улиц.
                                            Если же такой дом существует на обеих улицах, то неверный вариант будет отвергнут позже — при сравнении найденного индекса с заданным в адресе.
                                              0
                                              Я предполагал, что Вы этот случай рассматриваете, просто не описали.
                                              Просто к месту вспомнился казус с таксистом. Индекса у меня, понятное дело, не было, хотя и было название района.
                                                +1
                                                Случай действительно к месту, а вот индексом вы зря в тот раз не поинтересовались: они для того и пишутся на табличках вместе с названием улицы, чтоб гость города мог отличить «London St, EC3R» от «London St, W2»
                                            0
                                            Жил в лондоне. Дом был разделен на 2 квартиры, подвал и первый этаж 15A. Наш второй этаж 15B. Постоянно ходили за почтой к соседям снизу т.к. 15B — почтальоны идентифицировали как 15 basement хотя на дверях было указано (почтовые ящики — отверстие в двери..)

                                            Хотя с другой стороные такой продуманой и понятной структуры транспорта, как в Лондоне я нигде больше не втсречал… Так, что несмотря на консервативность есть там вещи сильно упрощающие жизнь…

                                            Only users with full accounts can post comments. Log in, please.