Взвешенная дизъюнкция в Perl Regular Выражения?

Question

Я довольно опытен с регулярными выражениями, но у меня есть некоторые трудности с текущим приложением, связанным с дизъюнкцией.

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

United States COUNTRY California STATE San Francisco CITY Mission STREET 345 NUMBER

(где слова в крышках, что я назвал «идентификаторами «).

Мы хотим, чтобы разобрать его в:
United States COUNTRY
California STATE
San Francisco CITY
Mission STREET
245 NUMBER


ОК, это, конечно, надуманный для английского языка, но вот загвоздка: я работаю с китайскими данными, где на самом деле этот стиль спецификации идентификатора происходит все время. Пример ниже:

云南-省 ; 丽江-市 ; 古城-区 ; 西安-街 ; 杨春-巷 ; Yunnan-Province ; LiJiang-City ; GuCheng-District ; Xi'An-Street ; Yangchun-Alley

Это достаточно просто - ленивый матч на потенциальных идентификаторы кандидатов, разделенный в дизъюнктивной список.

Для Китая, являются следующие "область на уровне" субъекты:

省 (Province) , 自治区 (Autonomous Region) , 市 (Municipality)

Так что мой регулярное выражение до сих пор выглядит следующим образом:

(.+?(?:(?:省)|(?:自治区)|(?:市)))

У меня есть ряд они, чтобы учитывать разные части адреса. Следующий уровень, соответствующий городов, например, является:

(.+?(?:(?:地区)|(?:自治州)|(?:市)|(?:盟)))

Так, чтобы соответствовать провинции объект, за которым следует номер объекта:

(.+?(?:(?:省)|(?:自治区)|(?:市)))(.+?(?:(?:地区)|(?:自治州)|(?:市)|(?:盟)))

названными группами захвата:
(?<Province>.+?(?:(?:省)|(?:自治区)|(?:市)))(?<City>.+?(?:(?:地区)|(?:自治州)|(?:市)|(?:盟)))

Для вышесказанного это дает:
$+{Province} = 云南省
$+{City} = 丽江市

Это все хорошо и хорошо, и я добираюсь довольно далеко. Проблема, однако, заключается в том, что я пытаюсь учитывать идентификаторы, которые могут быть подстрокой других идентификаторов. Например, единая организация уличного уровня - «村委会», что означает деревенский оргкомитет. В наборе адресов, которые я хочу разделить, не каждый адрес имеет полное описание. Фактически, я нахожу «村委» и просто «村».

Проблема?Если у меня есть чистая дизъюнкция этих элементов, мы имеем следующее:

(?<Street>.+?(?:(?:村委会)|(?:村委)|(?:村)))

Что происходит, хотя, является то, что если у вас есть объект 保定 - 村委会 (Баодин Village оргкомитет), эта ленивое regex останавливается на 村 и называет его днем, осиротевший наш бедный 委会, потому что 村 является одним из потенциальных дизъюнктивных элементов.

Представьте английский эквивалент вроде следующего:
(?<Animal>.+?(?:(?:Cat)|(?:Elephant)|(?:CatElephant)|(?:City)))

У нас есть два входных строк:
1. «дерьмо catelephant дерьма города», где мы хотели «Дерьмо catelephant» и «дерьмо» город 2 «crap catelephant city», где мы хотели «дерьмовый кот» «город-слон»

Ах, решение, вы говорите, должно сделать жатву pre-identifier. Но! Сущности имеют одинаковый идентификатор, который не находится на одном уровне.

Возьмите 市, например. Это означает просто «город». Но в Китае есть города уездного, провинциального и муниципального уровней. Если этот символ произошел дважды в строке, особенно в двух смежных сущностях, жадный поиск неправильно маркировал бы жадное соответствие в качестве первого объекта. Как и в следующем:

广东-省 ; 江门-市 ; 开平-市 ; 三埠-区 石海管-区
Guangdong-province ; Jiangmen-City ; Kaiping-City ; Sanbu-District ; Shihaiguan-District

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

матч за жадного поиска будет be
江门市开平市

Это неверно, так как два смежных объекта должны быть разделены на составляющие их части. Однажды на уровне провинциального города, один является городом уездного уровня.

Вернитесь к исходной точке, и я благодарю вас за то, что вы читаете это далеко, есть ли способ поставить взвешивание на дизъюнктивные сущности? Я бы хотел, чтобы регулярное выражение находило самый высокий «взвешенный» идентификатор.村委会 вместо простого 村, например, «catelephant» вместо «cat». В предварительных экспериментах анализатор регулярных выражений, по-видимому, продолжается слева направо в поиске дизъюнктивных матчей. Является ли это правильным предположением? Должен ли я помещать наиболее часто встречающиеся идентификаторы сначала в дизъюнктивный список?

Если я потерял кого-либо с китайскими деталями, я извиняюсь и могу уточнить, если необходимо. Пример действительно не должен быть китайским - я думаю, что в более общем плане речь идет о механизме дизъюнктивного соответствия регулярных выражений - в каком порядке он предпочитает дизъюнктивные сущности и как он решает, когда «называть это» день "в контексте ленивого поиска?

В каком-то смысле есть ли какая-то промежуточная точка между ленивыми и жадными поисками? Найдите самый маленький бит, который вы можете найти до самого длинного/наивысшего взвешенного дизъюнктивного объекта? Будьте ленивы, но приложите немного усилий, если сможете, ради тщательности? (Кстати, моя философия работы в колледже?)

Answer 1

Как обрабатываются alternations зависит от конкретного регулярного выражения engine. Для почти всех движков (в том числе движка регулярных выражений Perl) чередование соответствует с нетерпением - то есть оно сначала совпадает с самым левым выбором и только пробует другую альтернативу, если это не удается.Например, если у вас есть /(cat|catelephant)/, он никогда не будет соответствовать catelephant. Решение состоит в том, чтобы переупорядочить выбор так, чтобы в первую очередь приходилось наиболее конкретное.