@RodionGork read-only
Пользователь
4 сентября 2013 в 13:02

Разработка → Разбор адресов «нечёткими регулярными выражениями» из песочницы

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

На деревню дедушке


Сколько существует способов написать адрес — в смысле, географический?

Даже если упростить задачу и отбросить всякие мелочи вроде номера дома, строения, участка, квартиры и т.п. — и работать в пределах одного города — сколько вариантов можно придумать для написания названий улиц, площадей, проездов, проулков и т.п.?

Возьмём простой пример:
улица Цветочная — может быть обозначена с сокращением, как «ул. Цветочная» и «Цветочная ул.» — кроме того «ул.» можно пропустить (если Цветочной площади в городе нет), а «Цветочная» можно написать с ошибками «Цвяточная» или «Цвиточная», равно как и «Цветошная» — всё это будет выглядеть недурно!

Пример посложнее:
2-я Конно-армейская улица — здесь душе поэта есть где разгуляться. Номер можно выразить как «2-ая» или просто «2», а можно даже прописью «Вторая» или с сокращением «Втор.» — дефис же между «конной» и «армейской» будет встречаться примерно у 50% опрошенных. До кучи выяснится что «конно-армейская» кому-то показалась длинной и сократилась до «2 Конноарм. ул.»

Другие интересные примеры связаны с именами «ул. Матроса Железняка» (или просто «Железняка»?), «пр. Мориса Тореза» (или «Мариса Тереза»?) а также совсем эпические случаи «ул. 3-я линия второй половины», «дорога на деревню Рыбацкое», «ул. Левый берег реки Ижоры» — прошу простить если и сам я их не осилил написать правильно по памяти.

Это ж счастье для бизнеса


Теперь представьте. что вы разрабатываете приложение, которое в том числе должно «причёсывать» (т.е. приводить к унифицированному виду) всю эту географию. Я столкнулся с этим в 2011 году — программа должна была обрабатывать объявления содержащие адреса перед их выходом в печать.

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

Кроме того, Цветочных улиц, например, я насчитал в Санкт-Петербурге штук шесть, в разных районах. А потому приведение улиц в порядок требовалось для того, чтобы проверить есть ли она в указанном районе, и если нет, поискать по близлежащим — не промахнулись ли.

До попадания этой задачи в мои руки старое приложение пользовалось для той же цели услугами специального человека — оператора — который за несколько часов пропускал через себя около 30000 строк и поправлял их по своему усмотрению. Это было не очень удобно по ряду причин. В том числе потому, что оператор имел забавную привычку — отправлять 90% незнакомых ему улиц в Колпино. В результате чего, проверяя сохранённые файлы словарей, в Колпинском районе я обнаружил больше улиц, чем во всех остальных районах вместе взятых.

… и для программиста тоже счастье


Почему предыдущая версия приложения пользовалась услугами оператора?

Нетрудно догадаться, что программная обработка адресов требует каких-то неочевидных ухищрений. Среди занятных предложений которые я услышал от начальников и коллег были:
  • нужен ANTLR — пришлось объяснять что он для машинных языков и как раз не допускает излишних вольностей, весёлых опечаток и т.п.;
  • юзай регэкспы — предложение написать регэксп для всевозможных опечаток в топониме «улица Цветочная» показало автору этой затеи всю её несостоятельность;
  • Нейронные сети — автор такой светлой идеи не смог, к сожалению, объяснить каким именно образом предлагается применить нейронную сеть. По моей оценке, если сделать её выходами все возможные топонимы города, а входами — каждый символ (или каждый бит) входной строки, то наверное идея потерпела бы успех — только для тренировки её потребовалось бы какое-то невообразимое количество вариантов (ну и времени).


Эксперименты и подходы


Отчаявшись найти подходящий совет, я стал экспериментировать. Прочёл в википедии об алгоритмах нечёткого сравнения строк. Попробовал. Действительно, для сравнения слова со словом это вполне недурно.

Но как быть с «ул. Дворцовая» и «пл. Дворцовая» — здесь замена «у» на «п» это не опечатка, хотя с точки зрения алгоритма вес её такой же как если «Дворцовую» на «Дверцовую» заменить.

Что ж, разобъём строку на слова (по пробелам например) и посчитаем для них опечатки отдельно, а после определим нечто вроде среднего значения, либо будем брать в качестве оценки ошибки максимальное из ошибок в каждом слове.

Эта идея работала уже интереснее. Однако проблему сокращений, перестановки слов, пропуска опциональных слов (как в «улице Александра Матросова» — вполне могут «Александра»-то пропустить) — она всё ещё не решала.

Недолго думая я взялся творить «мета-язык» для описания этих правил. То что получилось я назвал «Библиотекой разбора нечётких регулярных выражений для Java».

Кроме функционала «сверки» с заданным выражением оказалось удобно иметь возможность прописывать прямо в выражении правила замены каких-либо частей.

Краткое описание


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

(=улица, Цветочная)

Символ "=" означает что слова должны присутствовать либо в заданном порядке, либо в обратном — т.е. данное выражение соответствует либо «улице Цветочной» либо «Цветочной улице».

И да, допустимое количество опечаток задаётся пороговым значением при создании объекта для сравнения, по умолчанию оно например 75%, что позволит пропустить и «Цвяточную» и даже «улитсу Цвитошную».

(Барак,(? Хуссейн), Обама,(? Второй))

Слова через запятую в скобках без какого либо специального символа означают, что ожидается цепочка слов именно в таком порядке. А вот выражения взятые в скобки со знаком "?" означают опциональные части, т.е. если они отсутствуют — они пропускаются и на подсчёт ошибки не влияют. В данном случае «Барак Хуссейн Обама», «Барак Обама Второй» и даже «Баррак Абама» будут отлично распознаны.

(^ (Владимир, Ленин), (Никита, Хрущев), (Карл, Маркс))

Символ "^" означает выбор одного из перечисленных подвыражений — в данном случае выражение можно сравнить с любым из трёх перечисленных деятелей, в то время как «Владимир Маркс» и «Никита Ленин» не пройдут.

Есть и другие выражения — для сверки с диапазонами чисел (к ним нечёткое сравнение применять было бы неудобно), для сверки с чётким регэкспом (неожиданно? но бывает полезно) — есть и возможность сверять с сокращениями (с помощью символа "*"), можно захватывать именованные группы чтобы дальше сверять с ними или использовать их в заменах — всё это я описал в документации.

Функционал замен становится актуален для больших выражений, краткий актуальный пример привести сложно но попробуем:

[^ ((^Влад*, Владимир, В)|Вова)~A|Дорогой_$A, ((^Ал*, Александр, Саша)|Саша)~B|Противный_$B ]~C|Здравствуй_$C

Выглядит громоздко, но суть проста — имя «Владимир» в разных начертаниях заменится на «Здравствуй Дорогой Вова», разные же версии Александра будут приветствованы иначе. Фрагменты, для которых замена не задана, должны заменяться на сам паттерн (поэтому например «Влодимер» был бы заменён на «Владимир» если бы не замена «Вова»).

Заключение


Составленные мною выражения для улиц 18 районов города (всего 18 выражений) уложились в файл объёмом 130 килобайт (впрочем, включая отступы и прочие элементы форматирования), работа по созданию словаря заняла у меня недели две. Позже нечто аналогичное пришлось создать и для перечня населённых пунктов области. Надеюсь меня можно извинить что я не пытаюсь постить здесь этот спам — вместо него я добавлю ниже выражение, использованное для разбора наименований стран.

У библиотеки дела идут шатко-валко. Задачу она решает достаточно узкую (для многих других задач из области natural language processing она не подходит). За пару лет я вижу около 1000 скачиваний. С письмами и вопросами обратились человек пять. Тут полезно отметить что для английского языка нечёткое сравнение в том же виде как для русского менее эффективно (оно эффективно для опечаток, но не для ошибок связанных с произношением, т.к. в английском слова часто пишутся слишком иначе чем произносятся)

Планировалось переписать примитивный алгоритм — у него есть неприятный недостаток с концевыми опциональными элементами из-за которого сейчас нельзя выражения склеивать программно — но я ушёл на новое место работы и эта задача (выпуск версии 2.0) ушла в глубокое «todo», как и желание мавенизировать и может отрефакторить проект (проект родился в самом начале моей java-карьеры). Если найдутся желающие продолжить это дело в соответствии с собственными вкусами — буду только рад!

Ссылки


Fuzzy RegExps for Java — cобственно моя библиотека.

Javadocs — документация и подробное описание языка «нечётких регэкспов»

TRE — другая библиотека регэкспов (на C) с возможностью нечёткого сравнения — я не придумал как её применить, версии для Java у неё нет да и возможности замен которая мне была нужна; ошибки сравнения в ней тоже оцениваются иначе, тем не менее может быть полезной в других задачах.

Дамеро-Левенштейн — популярный несложный алгоритм нечёткого сравнения который я применил внутри, для сравнения единичных слов входящих в выражения.

Обещанный пример



Пример выражения, «причёсывающего» страны — он использовался для объявлений о недвижимости за пределами России. Я выбрал его поскольку он несколько проще чем выражения для топонимов города и в то же время может быть использован «как есть» для аналогичных целей. (он сокращён чтоб не выглядеть слишком отвратительно, но полная версия доступна здесь).

(^
    Абхазия, Австралия, Австрия, Азербайджан, Албания, Алжир, Ангилья,
    Ангола, Андорра, Аргентина, Армения, Аруба, Афганистан, Багамы,
    Бангладеш, Барбадос, Бахрейн, Белиз, Бельгия, Бенин, Бермуды,
//...
    Фиджи, Филиппины, Финляндия, Франция, Хорватия, Чад, Черногория,
    Чехия, Чили, Швейцария, Швеция, Шпицберген, Эквадор, Эритрея, Эстония,
    Эфиопия, Ямайка, Япония,
    [^(Соед*,Шта*,(?Амер*)),Америка,США,USA]|Соединенные_Штаты_Америки,
//...
    [^Коморы,(Комор*,(@ISLAND))]|Коморы,
    [^Конго,Браззавиль,((@REPUB),Конго)]|Республика_Конго,
    [^Заир,ДРК,({^ДР,(Демокр*,(@REPUB))},Конго)]|ДР_Конго,
//...
    [^Бирма,Мьянма]|Мьянма,
    [(@ISLAND),Мэн]|Остров_Мэн,
    [Нагор*,(?-),Кара*,(?@REPUB)]|Нагорно-Карабахская_Республика,
    [^Нидерланды,Голландия]|Нидерланды,
//...
    [Ю*,Осетия]|Южная_Осетия,
    [^ЮАР,{(^Южноафр*,{Ю*,(?-),Афр*}),(@REPUB)}]|Южно-Африканская_Республика,
    [Ю*,Судан]|Южный_Судан
)

::ISLAND (^остров*,{о,-,в*})
::REPUB (^р,респ,респуб*)
@RodionGork
карма
18,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (33)

  • +1
    человек-остров испортил пример :)
    • 0
      Спасибо. Попытался наступить на горло этим «островитянам» заменив символы @ на @ — если вдруг известен способ лучше, поделитесь пожалуйста :)
  • +6
    Спасибо.
    Знаком с этим не по наслышке, нужно было привязать адреса из древней БД к КЛАДру, в исходной базе они были просто в виде строк. Разумеется, вбивались как кому захочется. Исправить ситуацию за вменяемые сроки автоматически не удалось.
    Но начальство быстро нашло выход: мобилизовало персонал, была создана удобная форма для привязки, и ручками её, ручками…
    • +7
      Я больше скажу. В одной конторе, попытки заставить бухгалтеров выбирать тип организации «АО», «ЗАО», а название вбивать без кавычек, привели к эпикфейлу.

      Нет, тип они дисциплинировано выбирали. А вот название вводили с кавычками и ОООми. Попытки отрезать ООО и кавычки в поле ввода привели к тому, что хитрые бухгалтера стали вбивать так: 000 ``Одно такое``. В общем, нормальным решением оказалось отдать им поле на обругание, и сделать скрытое поле в котором лежало название обрезанное после ввода простым регэкспом.

      Лет 15 прошло, но думаю бухгалтера до сих пор считают, что программа правильно печатает бланки ищет и сортирует по имени фирмы, потому что они правильно вводят название со всеми АОЗТ и кавычками.

      По теме же топика — очень круто.
      • +3
        Надо было поле сделать не скрытым и подписать «Вот так должно быть введено: ».
      • +2
        На событие нажатия кнопки повесить регулярку, и при попытке ввода «ООО» выдавать прямо в строке «А в глаз?» :)
  • 0
    Я делал похожую задачу для сравнения фио клиентов в CRM на Java.
    Использовал metaphone с корреляционным сравнением.
    Вычисляется один раз ключ для клиента и хранится в базе, потом при вводе еще раз вычисляется ключ и находится по нему документ клиента.
    И да, лучше всего сделать больше полей ввода данных.
    • 0
      Для фио как раз мой метод не годится — пришлось бы на каждого человека писать выражение!

      Но к счастью фио и сравнивать легче было (у нас по кр. мере) — просто нечётко по каждому отдельно Ф, И, О проверил и выбрал наилучшее…
  • +2
    Эх, если бы это еще было скрещено с базой Open Street Map для автоматической генерации таких выражений :)
    • 0
      А я, пожалуй, могу представить как можно автоматически генерировать названия для 95% или даже 98% улиц/переулков/проулков/закоулков — имхо, кстати, для этого как раз обычные регэкспы помогут… Эта задача выглядит проще в предположении что в исходной базе все улицы будут написаны «корректно» — соответственно проверять опечатки не нужно…

      Конечно стопроцентно победить изворотливость умов людских (в нашем случае клиентов) вряд ли возможно — но оставшиеся топонимы (не причесывающиеся) можно отбрасывать на ручную верификацию… (это как раз будет касаться всяких там «левых берегов реки ижоры»)

      В моём случае бОльшая сложность возникла из-за необходимости разделить выражения по районам. Это был эпик фейл — ни одной приличной базы где улицы были бы разнесены по районам я не нашёл, в связи с чем проверял их то на гугл-мэпе, то на яндекс-мэпе вручную. Бр-р-р. Ну правда когда оно стало само районы выдавать по улице — было приятно…
      • +1
        Эта задача выглядит проще в предположении что в исходной базе все улицы будут написаны «корректно» — соответственно проверять опечатки не нужно…

        С учётом комментария ниже, более-менее так оно и есть. Из OSM можно выгрузить все названия по любому региону, если хочется дополнительных гарантий по отсутствию ошибок, можно взять только те из них что есть у меня в словаре, например. Альтернативно можно сделать то же самое, например, с КЛАДР.
  • 0
    Главный причёсыватель адресов российской части OpenStreetMap очень хочет высказаться по теме и просит инвайт. Его почта: amdmi3@amdmi3.ru
  • +12
    Извините, получилось много для комментария, но на статью, на мой взгляд, не тянет.

    Я решал похожую задачу для OpenStreetMap. Там есть названия улиц как на собственно улицах так и в адресах, и для некоторых потребителей данных необходимо чтобы они совпадали (они привязывают дома к улице для адресного поиска), для других же это просто полезно (логично видеть в навигаторе списке улиц одну улицу Ленина, а не «улицу Ленина», «Ленина улицу» и «Ул.Ленина», причем у каждой своя часть домов). Так как OpenStretMap это краудсорсинг, в базе присутствовал весь комплект вариантов, поэтому в один прекрасный момент было решено это дело причесать: на основе статей топонимистов было выработано соглашение по названиям названий улиц (в двух словах — «улица Ленина», но «Ленинская улица») и было решено привести данные по всей России ей в соответствие.

    Первая версия причёсывалки, да — работала на регулярках. Название улицы разбиралось на части (статусная — «улица»/«переулок»/«проезд»/..., номерная — «1-й»/«2-я», поясняющая — «верхний»/«нижний»/«новая»/«старая») и собственно название, всё это приводилось к правильному порядку слов и регистру, раскрывались сокращения, сравнивались роды слов, добавлялась буква «ё», затем список замен проверялся в ручную и заливался в базу. Опечатки не поддерживались.

    Этот код проработал с полгода, пока не стало понятно что подход тупиковый, а старая поговорка — «если у вас есть проблема, и вы решаете её регулярками, у вас есть две проблемы» работает на 100%. Надо сказать, что ключевым требованием к системе было отсутствие ложных срабатываний, ибо вносить ошибки в данные было непозволительно, а ошибок было навалом, поскольку регулярки не покрывали того что нужно и покрывали то что не нужно, поддержка их стала адом, списки исключений и исключений из исключений росли как на дрожжах, плюс проверка и исправление сгенерированных списков замен требовали уйму времени. Сайт, показывающий ошибки на карте, так и не было толком анонсирован в паблик во избежание необдуманных правок новичками, а соответствие названий соглашению остановилось где-то на уровне 95%. Приведу лишь один забавный пример из многих неожиданностей с которыми пришлось столкнуться — в ё-фикаторе было правило /озерн/озёрн/, которое добавляло «ё» в Озёрные, Приозёрные и Заозёрные улицы и переулки и всё было замечательно, пока не попалась Бульдозерная улица.

    Потребовался другой подход с более прямолинейной логикой, требующий меньше ручной работы, не допускающий ложных срабатываний, и, соответственно, допускающий исправления вслепую хотя бы части данных, покрывающий больший процент улиц и поддерживающий исправление опечаток. Тогда уже было понятно что возможно это только с использованием большого словаря всех названий улиц. Блок регулярок, по сути, именно к нему и стремится, но не поддерживаем, а если помимо простых строк использовать wildcards ещё и непредсказуем. Что получилось в новом варианте:

    Основа — библиотека на C++, умеющая выделять в названиях статусную часть (и только её), вырезать её, приводить к полной/сокращённой форме и приклеивать обратно к названию с разных сторон.

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

    Но для проверки нужен словарь. Для сопоставления с ним, используется описанная логика, т.е. и словарь и входное название приводятся к одной форме, по ней происходит сравнение, и при совпадении выдаётся вариант из словаря.

    — сначала ищем точное совпадение, чтобы отбросить названия которые уже есть в словаре
    — далее ищем формы, отличающиеся только регистром и написанием статусной части (назовём их неканоническими формами). Предполагается, что к ложным срабатываниям это не приведёт и сгенерированные здесь замены можно заливать без проверки и показывать пользователям. Замены я, тем не менее, всё равно всегда просматриваю, но практика показывает что это работает замечательно. И надо сказать, что самый большой процент несовпадений попадает именно в эту категорию, т.е. большая часть ошибок исправляется, по сути, полностью автоматически.
    — далее ищем формы используя нечёткий поиск и допуская произвольную перестановку слов. Эта категория уже обязательно требует ручной проверки. Для нечёткого поиска была на коленке написана библиотечка, не слишком эффективная но для данной задачи вполне подходящая — она умеет нечёткое сравнение строк с заданным расстоянием Левенштейна. Эффективность этой стадии очень зависит от наполненности словаря, причём нелинейно: когда словарь небольшой, ошибки не находятся. Чем он больше, тем больше начинается ложных срабатываний и предложенных вариантов для каждого (например, «улица Леснова» которой пока нет в словаре → «улица Леонова», «улица Лескова»), и только с наполнением словаря «под завязку» их число снижается. Как правило, для проверки хватает расстояния в единицу.
    — отдельно ищется совпадение входного названия с формой из словаря без статусной части. Это позволяет находить названия типа «Ленина» где статусная часть опущена — с этим, мы, увы, ничего сделать не можем — только показать на карте, это должны исправлять местные мапперы.
    — всё что осталось. Это корректные названия которыми можно пополнить словарь либо названия с двумя и более опечатками, либо мусор типа «тропа в лес».

    Результаты проекта: уже два года я пополняю словарь (довольно неспешно, в основном добавляю новые названия накопившиеся за неделю) и причёсываю базу OSM. На данный момент 98% улиц в российском ОСМ совпадают со словарём (хотя если считать по уникальным названиям, в словаре есть только 77% из них), все известные ошибки типа неканонической формы исправлены, оставшееся (это улицы без статусных частей которые надо исправлять руками в базе, улицы без совпадений которые надо проверять и добавлять в словарь а также предположительно-опечатки, которые по большей части состоят из ложных срабатываний и также должны быть проверены и добавлены в словарь, либо действительных ошибок которые можно исправить) будет постепенно разбираться.

    В общем, посыл такой: осторожнее с регулярками. Забытая ^, лишняя .* захватят гораздо больше чем надо, и поддерживать это крайне сложно. Что не умеет моя реализация — так это сравнить «улица Ленина» и «улица В.И. Ленина». Но решается это по моему опыту только расширением возможностей словаря, а при попытке сделать что-то похожее на /улица.*Ленина/ надо быть готовым к тому что сматчатся «улица Путь Ленина» и «улица Сергея Тюленина».

    Исходники, словарь:
    github.com/AMDmi3/streetmangler
    (C++, биндинги для Perl, Python и Java)

    Мой доклад по теме на Web+Gis 2011 (по большей части повторяет написанное выше):
    www.youtube.com/watch?v=GO_hgOEU8-M
    (слайды: amdmi3.ru/files/webgis2011/)
    • +2
      Насчёт того что на статью не тянет — напрасно по-моему. Материал интересный и как видите актуальный для многих. Может вам стоит найти силы, дооформить примерами какими-то и запостить?

      В общем, посыл такой: осторожнее с регулярками.


      Осмелюсь всё-таки обратить внимание что речь шла не об обычных (perl-ового типа) выражениях — обычные всё-таки катастрофически не подходят для нашей с вами цели. Здесь же всё не так страшно было как с обычными (они примитивнее по синтаксису) поэтому писать и читать их немножечко проще — а пользы больше. :)

      В целом безусловно правда в вашем замечании есть — например когда я использовал тот же подход для разбора станций метро и железной дороги я с восторгом обнаружил что разница между «Московская» и «Маяковская» находится в пределах допустимой погрешности с точки зрения анализатора — и прилось его сделать чуть умнее.

      С другой стороны мой вариант — составление «словаря нечётких выражений» позволил мне провернуть огромный пласт работы в достаточно небольшое время (кроме улиц я разбирал и населённые пункты, и станции, и страны, и типы строений, и типы входов/въездов, типы недвижимости и даже разновидности санузлов). Человек который пришёл после меня на проект первые две недели жаловался что он ничего не понимает — а потом начал использовать механизм сам (для каких-то полей коммерческой недвижимости) и восторгался им целый год несмотря на указанные недостатки библиотеки…

      Естественно всё-таки я исходил из того что я допускаю некоторый (мелкий) процент ошибок в случаях когда люди слишком криво пишут названия — и кроме того чуть больший процент нераспознанных улиц которые отдаются на проверку оператору.

      В моём случае это было обосновано потому что старая версия (с ручной проверкой) обрабатывалась уже в последний момент перед подачей объявлений в печать — а новая делала всё автоматически, сразу по присылке данных — и можно было клиенту отправить на проверку то что получилось, пометив где строки «причесались» хорошо, а в которых есть сомнения.
      • 0
        Осмелюсь всё-таки обратить внимание что речь шла не об обычных (perl-ового типа) выражениях — обычные всё-таки катастрофически не подходят для нашей с вами цели.

        В данном случае синтаксис не принципиален.

        разница между «Московская» и «Маяковская» находится в пределах допустимой погрешности с точки зрения анализатора — и прилось его сделать чуть умнее

        Насколько умнее? Вот только из того что у меня есть в словаре с левенштейновским расстоянием 1 в нём же находятся совпадения для 5.5% названий. Для чего-то больше десятка, выглядит это примерно так: pastebin.com/Y8PX8f6p. Вы же пишете что у вас сравнение с пороговым значением в 75%, предполагаю что это левенштейновское расстояние в 1/4 длины строки, значит для средней улицы — 3. Для 3 уже 22% совпадений с несколькими улицами. В таких условиях неправильные совпадения весьма вероятны и в любом случае их надо сначала оценить количественно, иначе когда-нибудь обнаружится что хотя задача сопоставления/распознавания решена, сопоставилось/распозналось совсем не то что хотелось. Для вашей задачи, кстати, такие оценки есть?
        • 0
          В данном случае синтаксис не принципиален.


          Ну поскольку я пробовал задачу решать разными способами, имею некоторые основания полагать что… хм… не сам синтаксис, но принцип сопоставления с выражением (выражаемый синтаксисом) имеет значение.

          Вы же пишете что у вас сравнение с пороговым значением в 75%


          75% там дефолтовое значение, для улиц действительно меньше было (точно не вспомню, нужно код идти смотреть).

          Оценки я проводил — но ведь они привязаны были к тем данным что к нам от клиентов приходили, я не думаю что это очень адекватно: около 1.5% не проходили проверку, 0.02% давали ложные сопоставления.

          Эти 0.02% можно было бы исправить (как в случае с Московской-Маяковской) если бы разначать заменам некоторых символов величину ошибки меньше 1 (скажем «е»/«и», «а»/«о») внутри функции нечёткого сравнения — но это решили отложить на «после запуска» — и по крайней мере я этот импрувмент так и не ввёл.

          Конечно для каких-то случаев и такой процент ошибки недопустимо высок (да и выражения писать — и потом ещё проверять! — тоже работа) — однако в нашем случае это было определённо лучше нежели доверить работу по верификации объявлений оператору :)
          • 0
            UPD: насчёт «умнее» я имел в виду что сначала было совсем тупо — было подозрение что сравнение будет не быстро рабоать — и программа выбирала первое же значение которое давало совпадение выше порога. С одной стороны оказалось что это оч плохо, с другой что сравнение идёт достаточно шустро и можно педантично выбирать оптимальный вариант. Ничего особенного… :)
          • 0
            Ну поскольку я пробовал задачу решать разными способами, имею некоторые основания полагать что… хм… не сам синтаксис, но принцип сопоставления с выражением (выражаемый синтаксисом) имеет значение.

            Принцип сопоставления во всех случаях конечный автомат, нет? Но понятно что синтаксический сахар типа (= ) и замены внутри регулярки делает всё намного проще.

            0.02% давали ложные сопоставления

            Это действительно неплохо. Забыл спросить, а какой объём (уникальных и всего названий)?
            • 0
              Ну да, там реализация конечного автомата, хотя достаточно неуклюжая на мой теперешний вкус. :)

              Насчёт 0.02% я не могу точно сказать насколько это «неплохо». Проблема оценки в том что для неё я использовал меньше миллиона строк — и это были строки просто взятые из того что в течение последних месяцев присылали клиенты. (т.е. не удивлюсь если какие-то очень редко встречающиеся топонимы не были проверены)

              Если бы я сам настойчиво сел по списку для каждой улицы выдумывать возможные варианты опечаток — думаю раз в пять-десять больше бы эта величина была.

              Но конечно после этого я бы мог «тюнинговать» словарь (хотя возможно некоторые выражения стали бы сильно неуклюжими).

              Вообще пожалуй любопытно было бы потестить на каких-нибудь «более других» данных :)

              Топонимов около 2000 в СПб, кажется, если вопрос об этом.
              • 0
                Ну тогда понятно — у нас-то их 56k, словарь 37k, вероятность ошибки растёт как n*m, а ошибки неприемлемы.
                • 0
                  Я плохо знаком с реализуемым вами процессом для пользователей (точнее не знаком) поэтому не могу оценить — например, возможно ли в вашем случае уточнение с помощью названия города или нет…

                  И выражение «ошибки неприемлемы» я честно говоря не до конца понимаю. Есть технологический параметр — цена ошибки… Вы наверное не имеете в виду что в вашем случае он бесконечный? Или я наверное не до конца понимаю какую задачу вы решаете.

                  В нашем случае например речь идёт о том что либо человек публикует некорректное объявление (и теряет на его стоимости — ну впоследствии жалуется и ошибка исправляется) — либо система пропускает адрес публикация которого карается штрафом (но поскольку эти адреса на конкретных улицах, а не для всех улиц вероятность ошибки одинакова — величина тоже получается ещё меньше).

                  Исходя из этих соображений и решили мириться.

                  Правда был ещё такой критерий — сложность добавления новых топонимов в список (фактически на это требуется программист). Я думаю в вашем случае этой проблемы нет, если я верно понял…
                  • 0
                    Я плохо знаком с реализуемым вами процессом для пользователей (точнее не знаком) поэтому не могу оценить — например, возможно ли в вашем случае уточнение с помощью названия города или нет…

                    Нет — пришлось бы делать разные словари для разных городов, причём словари по большей части бы пересекались. Есть возможность вынести общую часть в отдельный файл и подключать его в частных, но это лишние хлопоты.

                    И выражение «ошибки неприемлемы» я честно говоря не до конца понимаю. Есть технологический параметр — цена ошибки… Вы наверное не имеете в виду что в вашем случае он бесконечный? Или я наверное не до конца понимаю какую задачу вы решаете.

                    Привожу написание названий улиц в базе OSM к одному виду, исправляя попутно ошибки. В OpenStreetMap очень ценят работу участников проекта, поэтому испортить добавленное кем-нибудь название — немыслимо, поэтому да — цена весьма высока.

                    Правда был ещё такой критерий — сложность добавления новых топонимов в список (фактически на это требуется программист). Я думаю в вашем случае этой проблемы нет, если я верно понял…

                    Нет, там просто текстовый словарь с названием улицы на строчку. Да, я лично тоже думаю что написать 7 раз «N-й Нижний переулок» проще чем набирать скобки для диапазона. Словарь также удобнее грепать и обрабатывать другими способами.
      • +1
        Кстати, числа у вас учитываются? В том смысле что для них никакое fuzzy сравнение желательно не применять.
        • 0
          Да, там есть такая штуковина для разбора номеров именно. С указанным диапазоном сверяет. Я сам очень быстро обнаружил что она нужна :)

          Вот ниже она во фрагменте из Выборгского района для 1-6 и 8 верхних переулков заюзана.

          //...
          {=  [^ Беловодский, Евпаторский, Зеленков, Крапивный, Лагерный, Ловизский, Нейшлотский,
                      Павский, Рабочий, Рощинский, Санаторный, Сахарный, Сосновый, Учебный, Центральный,
                      Школьный,
                      [(^(#1:6),8)~N,(?[(?-),й]),верхн*]|$N_Верхний,
          	    [^Новосил*, [Ново,(?-),сильц*]]|Новосильцевский
                  ]~U,
                  [?(@PEREULOK)] }
                  |$U_пер.,
          //...
          
          • 0
            Просто в качестве ещё одного примера, [(^(#1:6),8)~N,(?[(?-),й]),верхн*]|$N_Верхний сделало бы «Верхним» «1-й Верхне-Профинтерновский переулок»
            • 0
              Нет-нет, он будет разбит на три терма а звёздочка «работает» только до конца терма.

              Вот с «Верхнепрофинтерновским» — да, было бы нехорошо — конечно, если бы его не было в словаре.
              • 0
                (в целом я не могу сказать что мне нравится как обработка слов с дефисами у меня получилась)
    • 0
      Оформите статью пожалуйста (Добавьте иллюстраций если это возможно, разбейте текст на заголовки для лучшей читаемости, добавьте куски кода). На хабре куча топиков и похуже вашего комментария.
    • 0
      Я тоже за отдельный топик., если не сложно, конечно.
      • +2
        Ok, сделаем.
    • 0
      А сколько, в среднем, времени занимает причесывание одного адреса? Очень здорово было бы вставить такой функционал в Nominatim.
      • 0
        Там, по сути, всего лишь пара десятков строковых операций на выделение статусной части, при использовании словаря поиск по std::map на каждую категорию классификации (точное совпадение, если не найдено каноническая форма, если не найдено ...). Только нечёткий поиск требует перебора словаря, но по крайней мере из данных OSM по России до него доходит меньше 2% названий. В реальности у меня куда большую часть времени съедает парсинг OSM XML (так как я ещё не сделал поддержку OSM PBF), а на чистых текстовых данных на моём i7 в один поток обрабатывает 200000 названий/сек (проверял на самом же словаре, т.е. тут до нечёткого поиска дело не доходит никогда, всегда срабатывает точное совпадение).

        Для Nominatim подход со словарём точно не подойдёт, а причёсывание статусной части — настолько тривиальная операция что проще реализовать её там с нуля, возможно в виде более подходящем для всех языков мира. У меня, впрочем, сложилось впечатление что главная проблема nominatim — неумение правильно интерпретировать запрос, и на данный момент поиск на openstreetmap.ru (внутри использует движок полнотекстового поиска sphinx) выглядит намного более работоспособным (там, насколько я знаю, данные никак не обрабатываются, но запрос разбирается достаточно умно).
  • 0
    приятно уху Питерские места.

    спасибо за материал и ссылку на библиотеку TREE
    буду думать, как ее применить :)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.