Ну поскольку я пробовал задачу решать разными способами, имею некоторые основания полагать что… хм… не сам синтаксис, но принцип сопоставления с выражением (выражаемый синтаксисом) имеет значение.
Принцип сопоставления во всех случаях конечный автомат, нет? Но понятно что синтаксический сахар типа (= ) и замены внутри регулярки делает всё намного проще.
0.02% давали ложные сопоставления
Это действительно неплохо. Забыл спросить, а какой объём (уникальных и всего названий)?
Осмелюсь всё-таки обратить внимание что речь шла не об обычных (perl-ового типа) выражениях — обычные всё-таки катастрофически не подходят для нашей с вами цели.
В данном случае синтаксис не принципиален.
разница между «Московская» и «Маяковская» находится в пределах допустимой погрешности с точки зрения анализатора — и прилось его сделать чуть умнее
Насколько умнее? Вот только из того что у меня есть в словаре с левенштейновским расстоянием 1 в нём же находятся совпадения для 5.5% названий. Для чего-то больше десятка, выглядит это примерно так: pastebin.com/Y8PX8f6p. Вы же пишете что у вас сравнение с пороговым значением в 75%, предполагаю что это левенштейновское расстояние в 1/4 длины строки, значит для средней улицы — 3. Для 3 уже 22% совпадений с несколькими улицами. В таких условиях неправильные совпадения весьма вероятны и в любом случае их надо сначала оценить количественно, иначе когда-нибудь обнаружится что хотя задача сопоставления/распознавания решена, сопоставилось/распозналось совсем не то что хотелось. Для вашей задачи, кстати, такие оценки есть?
Эта задача выглядит проще в предположении что в исходной базе все улицы будут написаны «корректно» — соответственно проверять опечатки не нужно…
С учётом комментария ниже, более-менее так оно и есть. Из OSM можно выгрузить все названия по любому региону, если хочется дополнительных гарантий по отсутствию ошибок, можно взять только те из них что есть у меня в словаре, например. Альтернативно можно сделать то же самое, например, с КЛАДР.
Извините, получилось много для комментария, но на статью, на мой взгляд, не тянет.
Я решал похожую задачу для OpenStreetMap. Там есть названия улиц как на собственно улицах так и в адресах, и для некоторых потребителей данных необходимо чтобы они совпадали (они привязывают дома к улице для адресного поиска), для других же это просто полезно (логично видеть в навигаторе списке улиц одну улицу Ленина, а не «улицу Ленина», «Ленина улицу» и «Ул.Ленина», причем у каждой своя часть домов). Так как OpenStretMap это краудсорсинг, в базе присутствовал весь комплект вариантов, поэтому в один прекрасный момент было решено это дело причесать: на основе статей топонимистов было выработано соглашение по названиям названий улиц (в двух словах — «улица Ленина», но «Ленинская улица») и было решено привести данные по всей России ей в соответствие.
Первая версия причёсывалки, да — работала на регулярках. Название улицы разбиралось на части (статусная — «улица»/«переулок»/«проезд»/..., номерная — «1-й»/«2-я», поясняющая — «верхний»/«нижний»/«новая»/«старая») и собственно название, всё это приводилось к правильному порядку слов и регистру, раскрывались сокращения, сравнивались роды слов, добавлялась буква «ё», затем список замен проверялся в ручную и заливался в базу. Опечатки не поддерживались.
Этот код проработал с полгода, пока не стало понятно что подход тупиковый, а старая поговорка — «если у вас есть проблема, и вы решаете её регулярками, у вас есть две проблемы» работает на 100%. Надо сказать, что ключевым требованием к системе было отсутствие ложных срабатываний, ибо вносить ошибки в данные было непозволительно, а ошибок было навалом, поскольку регулярки не покрывали того что нужно и покрывали то что не нужно, поддержка их стала адом, списки исключений и исключений из исключений росли как на дрожжах, плюс проверка и исправление сгенерированных списков замен требовали уйму времени. Сайт, показывающий ошибки на карте, так и не было толком анонсирован в паблик во избежание необдуманных правок новичками, а соответствие названий соглашению остановилось где-то на уровне 95%. Приведу лишь один забавный пример из многих неожиданностей с которыми пришлось столкнуться — в ё-фикаторе было правило /озерн/озёрн/, которое добавляло «ё» в Озёрные, Приозёрные и Заозёрные улицы и переулки и всё было замечательно, пока не попалась Бульдозерная улица.
Потребовался другой подход с более прямолинейной логикой, требующий меньше ручной работы, не допускающий ложных срабатываний, и, соответственно, допускающий исправления вслепую хотя бы части данных, покрывающий больший процент улиц и поддерживающий исправление опечаток. Тогда уже было понятно что возможно это только с использованием большого словаря всех названий улиц. Блок регулярок, по сути, именно к нему и стремится, но не поддерживаем, а если помимо простых строк использовать wildcards ещё и непредсказуем. Что получилось в новом варианте:
Основа — библиотека на C++, умеющая выделять в названиях статусную часть (и только её), вырезать её, приводить к полной/сокращённой форме и приклеивать обратно к названию с разных сторон.
Понятно, что это очень просто, но уже, не прибегая к словарю, может привести кучу вариантов типа «улица Ленина», «ул.Ленина», «Ленина, улица» к одному знаменателю, что сильно поможет в сопоставлении нескольких баз (либо одной базы с самой собой, как в случае OSM).
Но для проверки нужен словарь. Для сопоставления с ним, используется описанная логика, т.е. и словарь и входное название приводятся к одной форме, по ней происходит сравнение, и при совпадении выдаётся вариант из словаря.
— сначала ищем точное совпадение, чтобы отбросить названия которые уже есть в словаре
— далее ищем формы, отличающиеся только регистром и написанием статусной части (назовём их неканоническими формами). Предполагается, что к ложным срабатываниям это не приведёт и сгенерированные здесь замены можно заливать без проверки и показывать пользователям. Замены я, тем не менее, всё равно всегда просматриваю, но практика показывает что это работает замечательно. И надо сказать, что самый большой процент несовпадений попадает именно в эту категорию, т.е. большая часть ошибок исправляется, по сути, полностью автоматически.
— далее ищем формы используя нечёткий поиск и допуская произвольную перестановку слов. Эта категория уже обязательно требует ручной проверки. Для нечёткого поиска была на коленке написана библиотечка, не слишком эффективная но для данной задачи вполне подходящая — она умеет нечёткое сравнение строк с заданным расстоянием Левенштейна. Эффективность этой стадии очень зависит от наполненности словаря, причём нелинейно: когда словарь небольшой, ошибки не находятся. Чем он больше, тем больше начинается ложных срабатываний и предложенных вариантов для каждого (например, «улица Леснова» которой пока нет в словаре → «улица Леонова», «улица Лескова»), и только с наполнением словаря «под завязку» их число снижается. Как правило, для проверки хватает расстояния в единицу.
— отдельно ищется совпадение входного названия с формой из словаря без статусной части. Это позволяет находить названия типа «Ленина» где статусная часть опущена — с этим, мы, увы, ничего сделать не можем — только показать на карте, это должны исправлять местные мапперы.
— всё что осталось. Это корректные названия которыми можно пополнить словарь либо названия с двумя и более опечатками, либо мусор типа «тропа в лес».
Результаты проекта: уже два года я пополняю словарь (довольно неспешно, в основном добавляю новые названия накопившиеся за неделю) и причёсываю базу OSM. На данный момент 98% улиц в российском ОСМ совпадают со словарём (хотя если считать по уникальным названиям, в словаре есть только 77% из них), все известные ошибки типа неканонической формы исправлены, оставшееся (это улицы без статусных частей которые надо исправлять руками в базе, улицы без совпадений которые надо проверять и добавлять в словарь а также предположительно-опечатки, которые по большей части состоят из ложных срабатываний и также должны быть проверены и добавлены в словарь, либо действительных ошибок которые можно исправить) будет постепенно разбираться.
В общем, посыл такой: осторожнее с регулярками. Забытая ^, лишняя .* захватят гораздо больше чем надо, и поддерживать это крайне сложно. Что не умеет моя реализация — так это сравнить «улица Ленина» и «улица В.И. Ленина». Но решается это по моему опыту только расширением возможностей словаря, а при попытке сделать что-то похожее на /улица.*Ленина/ надо быть готовым к тому что сматчатся «улица Путь Ленина» и «улица Сергея Тюленина».
[(^(#1:6),8)~N,(?[(?-),й]),верхн*]|$N_Верхнийсделало бы «Верхним» «1-й Верхне-Профинтерновский переулок»Принцип сопоставления во всех случаях конечный автомат, нет? Но понятно что синтаксический сахар типа (= ) и замены внутри регулярки делает всё намного проще.
Это действительно неплохо. Забыл спросить, а какой объём (уникальных и всего названий)?
В данном случае синтаксис не принципиален.
Насколько умнее? Вот только из того что у меня есть в словаре с левенштейновским расстоянием 1 в нём же находятся совпадения для 5.5% названий. Для чего-то больше десятка, выглядит это примерно так: pastebin.com/Y8PX8f6p. Вы же пишете что у вас сравнение с пороговым значением в 75%, предполагаю что это левенштейновское расстояние в 1/4 длины строки, значит для средней улицы — 3. Для 3 уже 22% совпадений с несколькими улицами. В таких условиях неправильные совпадения весьма вероятны и в любом случае их надо сначала оценить количественно, иначе когда-нибудь обнаружится что хотя задача сопоставления/распознавания решена, сопоставилось/распозналось совсем не то что хотелось. Для вашей задачи, кстати, такие оценки есть?
С учётом комментария ниже, более-менее так оно и есть. Из OSM можно выгрузить все названия по любому региону, если хочется дополнительных гарантий по отсутствию ошибок, можно взять только те из них что есть у меня в словаре, например. Альтернативно можно сделать то же самое, например, с КЛАДР.
Я решал похожую задачу для 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/)