У меня достаточно опыта работы с регулярными выражениями, но у меня возникли некоторые трудности с текущим приложением, связанным с дизъюнкцией.
Моя ситуация такова: мне нужно разделить адрес на его составные части на основе совпадения регулярного выражения с «элементами идентификатора» адреса. Сравнимым английским примером могут быть такие слова, как «штат», «дорога» или « бульвар" -- ЕСЛИ, например, мы написали это в наших адресах. Представьте, что у нас есть адрес, подобный следующему, где (и такого бы никогда не произошло в английском языке) мы указали тип идентификатора после каждого имени.
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>.+?(?:(?:村委会)|(?:村委)|(?:村)))
Однако происходит следующее: если у вас есть сущность 保定-村委会 (организационный комитет деревни Баодин), это ленивое регулярное выражение останавливается на 村 и прекращает работу, лишая нашего бедного 委会 осиротевшего, потому что 村 является одним из потенциальных дизъюнктивных элементов. .
Представьте себе английский эквивалент, подобный следующему:
(?<Animal>.+?(?:(?:Cat)|(?:Elephant)|(?:CatElephant)|(?:City)))
У нас есть две входные строки:
1. "crap catelephant crap city", где мы хотели "crap catelephant" и "crap city" 2. "crap catelephant city", где мы хотели "crap cat" "elephant city"
Ах, решение, как вы говорите, состоит в том, чтобы сделать захват предварительного идентификатора жадным. Но! Существуют сущности с одинаковым идентификатором, которые находятся на разных уровнях.
Возьмем, к примеру, 市. Это означает просто «город». Но в Китае есть города уездного, провинциального и муниципального уровня. Если этот символ встречается в строке дважды, особенно в двух соседних объектах, жадный поиск неправильно помечает жадное совпадение как первый объект. Как в следующем:
广东-省 ; 江门-市 ; 开平-市 ; 三埠-区 石海管-区
Guangdong-province ; Jiangmen-City ; Kaiping-City ; Sanbu-District ; Shihaiguan-District
(Обратите внимание, как указано выше, это было сегментировано вручную. Необработанные данные будут просто состоять из строк связанных символов)
Соответствие для жадного поиска:
江门市开平市
Это неправильно, так как два смежных объекта должны быть разделены на составные части. Один раз находится на уровне провинциального города, другой - уездного города.
Вернемся к исходной точке, и я благодарю вас за то, что вы дочитали до этого места, есть ли способ придать вес дизъюнктивным сущностям? Я бы хотел, чтобы регулярное выражение сначала нашло самый высокий «взвешенный» идентификатор. 村委会 вместо простого 村, например, «катслон» вместо просто «кошка». В предварительных экспериментах синтаксический анализатор регулярных выражений, по-видимому, движется слева направо при поиске дизъюнктивных совпадений. Является ли это обоснованным предположением? Должен ли я ставить наиболее часто встречающиеся идентификаторы первыми в дизъюнктивном списке?
Если я потерял кого-то с деталями, связанными с китайским языком, я приношу свои извинения и могу уточнить, если это необходимо. Пример на самом деле не обязательно должен быть китайским - я думаю, что в более общем плане это вопрос о механике дизъюнктивного сопоставления регулярных выражений - в каком порядке он отдает предпочтение дизъюнктивным объектам и как он решает, когда "называть это". в день» в контексте ленивого поиска?
В некотором смысле, есть ли какая-то золотая середина между ленивым и жадным поиском? Найдите наименьший бит, который вы можете найти перед самой длинной/самой взвешенной дизъюнктивной сущностью? Поленитесь, но приложите немного дополнительных усилий, если сможете, ради основательности? (Кстати, моя рабочая философия в колледже?)