Комментарии 33
человек-остров испортил пример :)
Спасибо.
Знаком с этим не по наслышке, нужно было привязать адреса из древней БД к КЛАДру, в исходной базе они были просто в виде строк. Разумеется, вбивались как кому захочется. Исправить ситуацию за вменяемые сроки автоматически не удалось.
Но начальство быстро нашло выход: мобилизовало персонал, была создана удобная форма для привязки, и ручками её, ручками…
Знаком с этим не по наслышке, нужно было привязать адреса из древней БД к КЛАДру, в исходной базе они были просто в виде строк. Разумеется, вбивались как кому захочется. Исправить ситуацию за вменяемые сроки автоматически не удалось.
Но начальство быстро нашло выход: мобилизовало персонал, была создана удобная форма для привязки, и ручками её, ручками…
Я больше скажу. В одной конторе, попытки заставить бухгалтеров выбирать тип организации «АО», «ЗАО», а название вбивать без кавычек, привели к эпикфейлу.
Нет, тип они дисциплинировано выбирали. А вот название вводили с кавычками и ОООми. Попытки отрезать ООО и кавычки в поле ввода привели к тому, что хитрые бухгалтера стали вбивать так: 000 ``Одно такое``. В общем, нормальным решением оказалось отдать им поле на обругание, и сделать скрытое поле в котором лежало название обрезанное после ввода простым регэкспом.
Лет 15 прошло, но думаю бухгалтера до сих пор считают, что программа правильно печатает бланки ищет и сортирует по имени фирмы, потому что они правильно вводят название со всеми АОЗТ и кавычками.
По теме же топика — очень круто.
Нет, тип они дисциплинировано выбирали. А вот название вводили с кавычками и ОООми. Попытки отрезать ООО и кавычки в поле ввода привели к тому, что хитрые бухгалтера стали вбивать так: 000 ``Одно такое``. В общем, нормальным решением оказалось отдать им поле на обругание, и сделать скрытое поле в котором лежало название обрезанное после ввода простым регэкспом.
Лет 15 прошло, но думаю бухгалтера до сих пор считают, что программа правильно печатает бланки ищет и сортирует по имени фирмы, потому что они правильно вводят название со всеми АОЗТ и кавычками.
По теме же топика — очень круто.
Я делал похожую задачу для сравнения фио клиентов в CRM на Java.
Использовал metaphone с корреляционным сравнением.
Вычисляется один раз ключ для клиента и хранится в базе, потом при вводе еще раз вычисляется ключ и находится по нему документ клиента.
И да, лучше всего сделать больше полей ввода данных.
Использовал metaphone с корреляционным сравнением.
Вычисляется один раз ключ для клиента и хранится в базе, потом при вводе еще раз вычисляется ключ и находится по нему документ клиента.
И да, лучше всего сделать больше полей ввода данных.
Эх, если бы это еще было скрещено с базой Open Street Map для автоматической генерации таких выражений :)
А я, пожалуй, могу представить как можно автоматически генерировать названия для 95% или даже 98% улиц/переулков/проулков/закоулков — имхо, кстати, для этого как раз обычные регэкспы помогут… Эта задача выглядит проще в предположении что в исходной базе все улицы будут написаны «корректно» — соответственно проверять опечатки не нужно…
Конечно стопроцентно победить изворотливость умов людских (в нашем случае клиентов) вряд ли возможно — но оставшиеся топонимы (не причесывающиеся) можно отбрасывать на ручную верификацию… (это как раз будет касаться всяких там «левых берегов реки ижоры»)
В моём случае бОльшая сложность возникла из-за необходимости разделить выражения по районам. Это был эпик фейл — ни одной приличной базы где улицы были бы разнесены по районам я не нашёл, в связи с чем проверял их то на гугл-мэпе, то на яндекс-мэпе вручную. Бр-р-р. Ну правда когда оно стало само районы выдавать по улице — было приятно…
Конечно стопроцентно победить изворотливость умов людских (в нашем случае клиентов) вряд ли возможно — но оставшиеся топонимы (не причесывающиеся) можно отбрасывать на ручную верификацию… (это как раз будет касаться всяких там «левых берегов реки ижоры»)
В моём случае бОльшая сложность возникла из-за необходимости разделить выражения по районам. Это был эпик фейл — ни одной приличной базы где улицы были бы разнесены по районам я не нашёл, в связи с чем проверял их то на гугл-мэпе, то на яндекс-мэпе вручную. Бр-р-р. Ну правда когда оно стало само районы выдавать по улице — было приятно…
Эта задача выглядит проще в предположении что в исходной базе все улицы будут написаны «корректно» — соответственно проверять опечатки не нужно…
С учётом комментария ниже, более-менее так оно и есть. Из OSM можно выгрузить все названия по любому региону, если хочется дополнительных гарантий по отсутствию ошибок, можно взять только те из них что есть у меня в словаре, например. Альтернативно можно сделать то же самое, например, с КЛАДР.
Главный причёсыватель адресов российской части OpenStreetMap очень хочет высказаться по теме и просит инвайт. Его почта: amdmi3@amdmi3.ru
Извините, получилось много для комментария, но на статью, на мой взгляд, не тянет.
Я решал похожую задачу для 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/)
Я решал похожую задачу для 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/)
Насчёт того что на статью не тянет — напрасно по-моему. Материал интересный и как видите актуальный для многих. Может вам стоит найти силы, дооформить примерами какими-то и запостить?
Осмелюсь всё-таки обратить внимание что речь шла не об обычных (perl-ового типа) выражениях — обычные всё-таки катастрофически не подходят для нашей с вами цели. Здесь же всё не так страшно было как с обычными (они примитивнее по синтаксису) поэтому писать и читать их немножечко проще — а пользы больше. :)
В целом безусловно правда в вашем замечании есть — например когда я использовал тот же подход для разбора станций метро и железной дороги я с восторгом обнаружил что разница между «Московская» и «Маяковская» находится в пределах допустимой погрешности с точки зрения анализатора — и прилось его сделать чуть умнее.
С другой стороны мой вариант — составление «словаря нечётких выражений» позволил мне провернуть огромный пласт работы в достаточно небольшое время (кроме улиц я разбирал и населённые пункты, и станции, и страны, и типы строений, и типы входов/въездов, типы недвижимости и даже разновидности санузлов). Человек который пришёл после меня на проект первые две недели жаловался что он ничего не понимает — а потом начал использовать механизм сам (для каких-то полей коммерческой недвижимости) и восторгался им целый год несмотря на указанные недостатки библиотеки…
Естественно всё-таки я исходил из того что я допускаю некоторый (мелкий) процент ошибок в случаях когда люди слишком криво пишут названия — и кроме того чуть больший процент нераспознанных улиц которые отдаются на проверку оператору.
В моём случае это было обосновано потому что старая версия (с ручной проверкой) обрабатывалась уже в последний момент перед подачей объявлений в печать — а новая делала всё автоматически, сразу по присылке данных — и можно было клиенту отправить на проверку то что получилось, пометив где строки «причесались» хорошо, а в которых есть сомнения.
В общем, посыл такой: осторожнее с регулярками.
Осмелюсь всё-таки обратить внимание что речь шла не об обычных (perl-ового типа) выражениях — обычные всё-таки катастрофически не подходят для нашей с вами цели. Здесь же всё не так страшно было как с обычными (они примитивнее по синтаксису) поэтому писать и читать их немножечко проще — а пользы больше. :)
В целом безусловно правда в вашем замечании есть — например когда я использовал тот же подход для разбора станций метро и железной дороги я с восторгом обнаружил что разница между «Московская» и «Маяковская» находится в пределах допустимой погрешности с точки зрения анализатора — и прилось его сделать чуть умнее.
С другой стороны мой вариант — составление «словаря нечётких выражений» позволил мне провернуть огромный пласт работы в достаточно небольшое время (кроме улиц я разбирал и населённые пункты, и станции, и страны, и типы строений, и типы входов/въездов, типы недвижимости и даже разновидности санузлов). Человек который пришёл после меня на проект первые две недели жаловался что он ничего не понимает — а потом начал использовать механизм сам (для каких-то полей коммерческой недвижимости) и восторгался им целый год несмотря на указанные недостатки библиотеки…
Естественно всё-таки я исходил из того что я допускаю некоторый (мелкий) процент ошибок в случаях когда люди слишком криво пишут названия — и кроме того чуть больший процент нераспознанных улиц которые отдаются на проверку оператору.
В моём случае это было обосновано потому что старая версия (с ручной проверкой) обрабатывалась уже в последний момент перед подачей объявлений в печать — а новая делала всё автоматически, сразу по присылке данных — и можно было клиенту отправить на проверку то что получилось, пометив где строки «причесались» хорошо, а в которых есть сомнения.
Осмелюсь всё-таки обратить внимание что речь шла не об обычных (perl-ового типа) выражениях — обычные всё-таки катастрофически не подходят для нашей с вами цели.
В данном случае синтаксис не принципиален.
разница между «Московская» и «Маяковская» находится в пределах допустимой погрешности с точки зрения анализатора — и прилось его сделать чуть умнее
Насколько умнее? Вот только из того что у меня есть в словаре с левенштейновским расстоянием 1 в нём же находятся совпадения для 5.5% названий. Для чего-то больше десятка, выглядит это примерно так: pastebin.com/Y8PX8f6p. Вы же пишете что у вас сравнение с пороговым значением в 75%, предполагаю что это левенштейновское расстояние в 1/4 длины строки, значит для средней улицы — 3. Для 3 уже 22% совпадений с несколькими улицами. В таких условиях неправильные совпадения весьма вероятны и в любом случае их надо сначала оценить количественно, иначе когда-нибудь обнаружится что хотя задача сопоставления/распознавания решена, сопоставилось/распозналось совсем не то что хотелось. Для вашей задачи, кстати, такие оценки есть?
В данном случае синтаксис не принципиален.
Ну поскольку я пробовал задачу решать разными способами, имею некоторые основания полагать что… хм… не сам синтаксис, но принцип сопоставления с выражением (выражаемый синтаксисом) имеет значение.
Вы же пишете что у вас сравнение с пороговым значением в 75%
75% там дефолтовое значение, для улиц действительно меньше было (точно не вспомню, нужно код идти смотреть).
Оценки я проводил — но ведь они привязаны были к тем данным что к нам от клиентов приходили, я не думаю что это очень адекватно: около 1.5% не проходили проверку, 0.02% давали ложные сопоставления.
Эти 0.02% можно было бы исправить (как в случае с Московской-Маяковской) если бы разначать заменам некоторых символов величину ошибки меньше 1 (скажем «е»/«и», «а»/«о») внутри функции нечёткого сравнения — но это решили отложить на «после запуска» — и по крайней мере я этот импрувмент так и не ввёл.
Конечно для каких-то случаев и такой процент ошибки недопустимо высок (да и выражения писать — и потом ещё проверять! — тоже работа) — однако в нашем случае это было определённо лучше нежели доверить работу по верификации объявлений оператору :)
UPD: насчёт «умнее» я имел в виду что сначала было совсем тупо — было подозрение что сравнение будет не быстро рабоать — и программа выбирала первое же значение которое давало совпадение выше порога. С одной стороны оказалось что это оч плохо, с другой что сравнение идёт достаточно шустро и можно педантично выбирать оптимальный вариант. Ничего особенного… :)
Ну поскольку я пробовал задачу решать разными способами, имею некоторые основания полагать что… хм… не сам синтаксис, но принцип сопоставления с выражением (выражаемый синтаксисом) имеет значение.
Принцип сопоставления во всех случаях конечный автомат, нет? Но понятно что синтаксический сахар типа (= ) и замены внутри регулярки делает всё намного проще.
0.02% давали ложные сопоставления
Это действительно неплохо. Забыл спросить, а какой объём (уникальных и всего названий)?
Ну да, там реализация конечного автомата, хотя достаточно неуклюжая на мой теперешний вкус. :)
Насчёт 0.02% я не могу точно сказать насколько это «неплохо». Проблема оценки в том что для неё я использовал меньше миллиона строк — и это были строки просто взятые из того что в течение последних месяцев присылали клиенты. (т.е. не удивлюсь если какие-то очень редко встречающиеся топонимы не были проверены)
Если бы я сам настойчиво сел по списку для каждой улицы выдумывать возможные варианты опечаток — думаю раз в пять-десять больше бы эта величина была.
Но конечно после этого я бы мог «тюнинговать» словарь (хотя возможно некоторые выражения стали бы сильно неуклюжими).
Вообще пожалуй любопытно было бы потестить на каких-нибудь «более других» данных :)
Топонимов около 2000 в СПб, кажется, если вопрос об этом.
Насчёт 0.02% я не могу точно сказать насколько это «неплохо». Проблема оценки в том что для неё я использовал меньше миллиона строк — и это были строки просто взятые из того что в течение последних месяцев присылали клиенты. (т.е. не удивлюсь если какие-то очень редко встречающиеся топонимы не были проверены)
Если бы я сам настойчиво сел по списку для каждой улицы выдумывать возможные варианты опечаток — думаю раз в пять-десять больше бы эта величина была.
Но конечно после этого я бы мог «тюнинговать» словарь (хотя возможно некоторые выражения стали бы сильно неуклюжими).
Вообще пожалуй любопытно было бы потестить на каких-нибудь «более других» данных :)
Топонимов около 2000 в СПб, кажется, если вопрос об этом.
Ну тогда понятно — у нас-то их 56k, словарь 37k, вероятность ошибки растёт как n*m, а ошибки неприемлемы.
Я плохо знаком с реализуемым вами процессом для пользователей (точнее не знаком) поэтому не могу оценить — например, возможно ли в вашем случае уточнение с помощью названия города или нет…
И выражение «ошибки неприемлемы» я честно говоря не до конца понимаю. Есть технологический параметр — цена ошибки… Вы наверное не имеете в виду что в вашем случае он бесконечный? Или я наверное не до конца понимаю какую задачу вы решаете.
В нашем случае например речь идёт о том что либо человек публикует некорректное объявление (и теряет на его стоимости — ну впоследствии жалуется и ошибка исправляется) — либо система пропускает адрес публикация которого карается штрафом (но поскольку эти адреса на конкретных улицах, а не для всех улиц вероятность ошибки одинакова — величина тоже получается ещё меньше).
Исходя из этих соображений и решили мириться.
Правда был ещё такой критерий — сложность добавления новых топонимов в список (фактически на это требуется программист). Я думаю в вашем случае этой проблемы нет, если я верно понял…
И выражение «ошибки неприемлемы» я честно говоря не до конца понимаю. Есть технологический параметр — цена ошибки… Вы наверное не имеете в виду что в вашем случае он бесконечный? Или я наверное не до конца понимаю какую задачу вы решаете.
В нашем случае например речь идёт о том что либо человек публикует некорректное объявление (и теряет на его стоимости — ну впоследствии жалуется и ошибка исправляется) — либо система пропускает адрес публикация которого карается штрафом (но поскольку эти адреса на конкретных улицах, а не для всех улиц вероятность ошибки одинакова — величина тоже получается ещё меньше).
Исходя из этих соображений и решили мириться.
Правда был ещё такой критерий — сложность добавления новых топонимов в список (фактически на это требуется программист). Я думаю в вашем случае этой проблемы нет, если я верно понял…
Я плохо знаком с реализуемым вами процессом для пользователей (точнее не знаком) поэтому не могу оценить — например, возможно ли в вашем случае уточнение с помощью названия города или нет…
Нет — пришлось бы делать разные словари для разных городов, причём словари по большей части бы пересекались. Есть возможность вынести общую часть в отдельный файл и подключать его в частных, но это лишние хлопоты.
И выражение «ошибки неприемлемы» я честно говоря не до конца понимаю. Есть технологический параметр — цена ошибки… Вы наверное не имеете в виду что в вашем случае он бесконечный? Или я наверное не до конца понимаю какую задачу вы решаете.
Привожу написание названий улиц в базе OSM к одному виду, исправляя попутно ошибки. В OpenStreetMap очень ценят работу участников проекта, поэтому испортить добавленное кем-нибудь название — немыслимо, поэтому да — цена весьма высока.
Правда был ещё такой критерий — сложность добавления новых топонимов в список (фактически на это требуется программист). Я думаю в вашем случае этой проблемы нет, если я верно понял…
Нет, там просто текстовый словарь с названием улицы на строчку. Да, я лично тоже думаю что написать 7 раз «N-й Нижний переулок» проще чем набирать скобки для диапазона. Словарь также удобнее грепать и обрабатывать другими способами.
Кстати, числа у вас учитываются? В том смысле что для них никакое fuzzy сравнение желательно не применять.
Да, там есть такая штуковина для разбора номеров именно. С указанным диапазоном сверяет. Я сам очень быстро обнаружил что она нужна :)
Вот ниже она во фрагменте из Выборгского района для 1-6 и 8 верхних переулков заюзана.
Вот ниже она во фрагменте из Выборгского района для 1-6 и 8 верхних переулков заюзана.
//...
{= [^ Беловодский, Евпаторский, Зеленков, Крапивный, Лагерный, Ловизский, Нейшлотский,
Павский, Рабочий, Рощинский, Санаторный, Сахарный, Сосновый, Учебный, Центральный,
Школьный,
[(^(#1:6),8)~N,(?[(?-),й]),верхн*]|$N_Верхний,
[^Новосил*, [Ново,(?-),сильц*]]|Новосильцевский
]~U,
[?(@PEREULOK)] }
|$U_пер.,
//...
Оформите статью пожалуйста (Добавьте иллюстраций если это возможно, разбейте текст на заголовки для лучшей читаемости, добавьте куски кода). На хабре куча топиков и похуже вашего комментария.
Я тоже за отдельный топик., если не сложно, конечно.
А сколько, в среднем, времени занимает причесывание одного адреса? Очень здорово было бы вставить такой функционал в Nominatim.
Там, по сути, всего лишь пара десятков строковых операций на выделение статусной части, при использовании словаря поиск по std::map на каждую категорию классификации (точное совпадение, если не найдено каноническая форма, если не найдено ...). Только нечёткий поиск требует перебора словаря, но по крайней мере из данных OSM по России до него доходит меньше 2% названий. В реальности у меня куда большую часть времени съедает парсинг OSM XML (так как я ещё не сделал поддержку OSM PBF), а на чистых текстовых данных на моём i7 в один поток обрабатывает 200000 названий/сек (проверял на самом же словаре, т.е. тут до нечёткого поиска дело не доходит никогда, всегда срабатывает точное совпадение).
Для Nominatim подход со словарём точно не подойдёт, а причёсывание статусной части — настолько тривиальная операция что проще реализовать её там с нуля, возможно в виде более подходящем для всех языков мира. У меня, впрочем, сложилось впечатление что главная проблема nominatim — неумение правильно интерпретировать запрос, и на данный момент поиск на openstreetmap.ru (внутри использует движок полнотекстового поиска sphinx) выглядит намного более работоспособным (там, насколько я знаю, данные никак не обрабатываются, но запрос разбирается достаточно умно).
Для Nominatim подход со словарём точно не подойдёт, а причёсывание статусной части — настолько тривиальная операция что проще реализовать её там с нуля, возможно в виде более подходящем для всех языков мира. У меня, впрочем, сложилось впечатление что главная проблема nominatim — неумение правильно интерпретировать запрос, и на данный момент поиск на openstreetmap.ru (внутри использует движок полнотекстового поиска sphinx) выглядит намного более работоспособным (там, насколько я знаю, данные никак не обрабатываются, но запрос разбирается достаточно умно).
приятно уху Питерские места.
спасибо за материал и ссылку на библиотеку TREE
буду думать, как ее применить :)
спасибо за материал и ссылку на библиотеку TREE
буду думать, как ее применить :)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Разбор адресов «нечёткими регулярными выражениями»