Краткое содержание: о библиотеке написанной мною для сопоставления с заданным словарём выражений на естественном языке — в частности, городских адресов.
Сколько существует способов написать адрес — в смысле, географический?
Даже если упростить задачу и отбросить всякие мелочи вроде номера дома, строения, участка, квартиры и т.п. — и работать в пределах одного города — сколько вариантов можно придумать для написания названий улиц, площадей, проездов, проулков и т.п.?
Возьмём простой пример:
улица Цветочная — может быть обозначена с сокращением, как «ул. Цветочная» и «Цветочная ул.» — кроме того «ул.» можно пропустить (если Цветочной площади в городе нет), а «Цветочная» можно написать с ошибками «Цвяточная» или «Цвиточная», равно как и «Цветошная» — всё это будет выглядеть недурно!
Пример посложнее:
2-я Конно-армейская улица — здесь душе поэта есть где разгуляться. Номер можно выразить как «2-ая» или просто «2», а можно даже прописью «Вторая» или с сокращением «Втор.» — дефис же между «конной» и «армейской» будет встречаться примерно у 50% опрошенных. До кучи выяснится что «конно-армейская» кому-то показалась длинной и сократилась до «2 Конноарм. ул.»
Другие интересные примеры связаны с именами «ул. Матроса Железняка» (или просто «Железняка»?), «пр. Мориса Тореза» (или «Мариса Тереза»?) а также совсем эпические случаи «ул. 3-я линия второй половины», «дорога на деревню Рыбацкое», «ул. Левый берег реки Ижоры» — прошу простить если и сам я их не осилил написать правильно по памяти.
Теперь представьте. что вы разрабатываете приложение, которое в том числе должно «причёсывать» (т.е. приводить к унифицированному виду) всю эту географию. Я столкнулся с этим в 2011 году — программа должна была обрабатывать объявления содержащие адреса перед их выходом в печать.
С точки зрения бизнеса необходимость «причёсывания» была актуальна по ряду соображений — чтобы не выпускать несколько объявлений с одинаковыми (но по-разному написанными) адресами — или чтобы не выпускать объявления с адресами из чёрного списка, за которые можно получить штраф (например, объекты недвижимости в отношении которых идёт судебное расследование и т.п.)
Кроме того, Цветочных улиц, например, я насчитал в Санкт-Петербурге штук шесть, в разных районах. А потому приведение улиц в порядок требовалось для того, чтобы проверить есть ли она в указанном районе, и если нет, поискать по близлежащим — не промахнулись ли.
До попадания этой задачи в мои руки старое приложение пользовалось для той же цели услугами специального человека — оператора — который за несколько часов пропускал через себя около 30000 строк и поправлял их по своему усмотрению. Это было не очень удобно по ряду причин. В том числе потому, что оператор имел забавную привычку — отправлять 90% незнакомых ему улиц в Колпино. В результате чего, проверяя сохранённые файлы словарей, в Колпинском районе я обнаружил больше улиц, чем во всех остальных районах вместе взятых.
Почему предыдущая версия приложения пользовалась услугами оператора?
Нетрудно догадаться, что программная обработка адресов требует каких-то неочевидных ухищрений. Среди занятных предложений которые я услышал от начальников и коллег были:
Отчаявшись найти подходящий совет, я стал экспериментировать. Прочёл в википедии об алгоритмах нечёткого сравнения строк. Попробовал. Действительно, для сравнения слова со словом это вполне недурно.
Но как быть с «ул. Дворцовая» и «пл. Дворцовая» — здесь замена «у» на «п» это не опечатка, хотя с точки зрения алгоритма вес её такой же как если «Дворцовую» на «Дверцовую» заменить.
Что ж, разобъём строку на слова (по пробелам например) и посчитаем для них опечатки отдельно, а после определим нечто вроде среднего значения, либо будем брать в качестве оценки ошибки максимальное из ошибок в каждом слове.
Эта идея работала уже интереснее. Однако проблему сокращений, перестановки слов, пропуска опциональных слов (как в «улице Александра Матросова» — вполне могут «Александра»-то пропустить) — она всё ещё не решала.
Недолго думая я взялся творить «мета-язык» для описания этих правил. То что получилось я назвал «Библиотекой разбора нечётких регулярных выражений для 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 у неё нет да и возможности замен которая мне была нужна; ошибки сравнения в ней тоже оцениваются иначе, тем не менее может быть полезной в других задачах.
Дамеро-Левенштейн — популярный несложный алгоритм нечёткого сравнения который я применил внутри, для сравнения единичных слов входящих в выражения.
Пример выражения, «причёсывающего» страны — он использовался для объявлений о недвижимости за пределами России. Я выбрал его поскольку он несколько проще чем выражения для топонимов города и в то же время может быть использован «как есть» для аналогичных целей. (он сокращён чтоб не выглядеть слишком отвратительно, но полная версия доступна здесь).
На деревню дедушке
Сколько существует способов написать адрес — в смысле, географический?
Даже если упростить задачу и отбросить всякие мелочи вроде номера дома, строения, участка, квартиры и т.п. — и работать в пределах одного города — сколько вариантов можно придумать для написания названий улиц, площадей, проездов, проулков и т.п.?
Возьмём простой пример:
улица Цветочная — может быть обозначена с сокращением, как «ул. Цветочная» и «Цветочная ул.» — кроме того «ул.» можно пропустить (если Цветочной площади в городе нет), а «Цветочная» можно написать с ошибками «Цвяточная» или «Цвиточная», равно как и «Цветошная» — всё это будет выглядеть недурно!
Пример посложнее:
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 (^р,респ,респуб*)