Одно расширенное POSIX регулярное выражение для соответствия всем кратчайшим подстрокам, которые начинаются с «a», заканчиваются на «b» и не содержат ни одного элемента набора строк
Учитывая строку, можно ли написать одно POSIX-расширенное регулярное выражение , чтобы оно соответствовало всем кратчайшим подстрокам, которые начинаются с a и заканчиваются b, но не содержат cb, cd или fg? Я хочу использовать такое регулярное выражение с функциями gensub, match или split (в gawk). Например,
- строка
"0a3cbsbtacc12bbb": соответствующая подстрока —"acc12b"; - строка
"a4cdddbbb5": нет соответствующей подстроки; - строка
"1taa/b///fafgfgcb2abb": совпадающими подстроками являются"a/b"и"ab".
Подход «отметить отрицательные совпадения» (с использованием символов, которые не встречаются во всем тексте) не подходит в моей ситуации: меня интересует только одно регулярное выражение. Итак, если я использую, например, split("1taa/b///fafgfgcb2abb", arr, regex, seps), я ожидаю seps[1] == "a/b" и seps[2] == "ab".
Если невозможно написать подходящее регулярное выражение (или если любое подходящее регулярное выражение слишком неэффективно с точки зрения производительности), мне было бы интересно узнать, почему.
пожалуйста, уточните, почему метод маркировки отрицательного соответствия не подходит в вашем случае. Эффективность? Обратите внимание, что всегда можно экранировать входные строки, чтобы неиспользуемые символы стали доступны для использования. Строки многострочные? Если нет, новая строка уже доступна
@jhnc: <пожалуйста, уточните, почему подход с маркировкой отрицательного соответствия не подходит в вашем случае> — потому что я не смог найти обобщенный способ решения проблемы, то есть какой-то фиксированный код, который работает с любым вводом. Если такой способ существует, можете ли вы в комментариях дать краткое описание подхода?
@EdMorton: Я бы определенно предпочел решение с использованием одного POSIX ERE. Почему? Потому что это позволяет использовать функции gensub, match и split с этим регулярным выражением. В противном случае один вопрос превращается в три вопроса (поскольку эти три функции решают три разные проблемы).
@EdMorton: <вы спрашиваете о том, как реализовать то, что, по вашему мнению, является решением проблемы, а не спрашиваете, как решить проблему> — есть три задачи: заменить, сопоставить и разделить. Для их выполнения существуют три соответствующие функции. Это можно сделать с помощью одного регулярного выражения, поэтому оно является решением (если оно существует). Так что мой вопрос определенно не вопрос XY...
Если вы на самом деле просто хотите найти все кратчайшие строки в каждой строке, которые начинаются и заканчиваются строками и не содержат других строк, тогда примите ответ на этот вопрос, который вы задали (или не делайте этого, если чувствуете, что не получили ответ) а затем опубликуйте новый вопрос об этом с минимальным воспроизводимым примером, включая образец ввода/вывода, демонстрирующий это.
@EdMorton: я уже принял ответ. На самом деле, сейчас меня интересует обобщенный алгоритм (в виде C-подобного псевдокода) для построения необходимого регулярного выражения (по трем входным данным: начальная подстрока, набор запрещенных подстрок, конечная подстрока), но это превращается Это довольно нетривиальная проблема, и я даже не знаю, где спросить...
Я в замешательстве. В вашем вопросе явно требуется одно регулярное выражение. Вы даже курсивом это выделили. Теперь я вижу, что вы принимаете ответ, который не дает вам ни одного регулярного выражения. Если бы я только знал, что вас устраивают другие решения, я бы не тратил на это столько времени :-(
@trincot: Я принял ответ, когда ваш ответ был удален. В любом случае, я объяснил проблему с текущей версией вашего ответа в своем комментарии к нему: поскольку построение регулярного выражения настолько нетривиально, мне нужен псевдокод для реализации решения, которое работает в других ситуациях.
Хорошо. У вас есть ответ? Просто чтобы знать, нужны ли еще усилия с моей стороны.
@lyricalwicked, похоже, вы застряли в очень распространенном мышлении, пытаясь использовать регулярное выражение для решения вашей проблемы, вместо того, чтобы просто пытаться найти лучшее решение вашей проблемы, поэтому об этом есть цитата/страница - ' Некоторые люди, столкнувшись с проблемой, думают: «Я знаю, я буду использовать регулярные выражения». Теперь у них две проблемы.'.
@trincot Я ценю объяснение подхода DFA и уверен, что оно будет полезно другим людям, которые его найдут 👍
@trincot: Я понятия не имею, потребуются ли дополнительные усилия с вашей стороны, потому что меня беспокоит сложность/производительность регулярного выражения (и его порождающей функции на языке gawk) для моих комбинаций трех параметров (начальная подстрока, набор запрещенных подстрок, конечная подстрока): Боюсь, подход, основанный на регулярных выражениях, не подходит для практического использования. Именно такую возможность и подразумевал последний абзац исходного вопроса. [1/4]
@trincot: я понятия не имею, как будет выглядеть (и работать) регулярное выражение в некоторых ситуациях (при условии, что начальная/конечная подстроки имеют максимальную длину 64 символа, максимальный размер набора запрещенных подстрок составляет 8, где каждая элемент имеет максимальную длину 4 символа). [2/4]
@trincot: Единственное, что я могу сказать, это то, что мне было бы интересно увидеть функцию gawk (или C-подобный псевдокод, который можно преобразовать в функцию на языке gawk), которая при наличии трех входных данных ( начальная подстрока, набор запрещенных подстрок, конечная подстрока), выводит расширенное POSIX регулярное выражение для сопоставления всех кратчайших подстрок, которые начинаются с начальной подстроки и заканчиваются конечной подстрокой, но не содержат ни одной запрещенной подстроки. [3/4]
@trincot: Если результирующие регулярные выражения (и соответствующие генерирующие алгоритмы на языке gawk) могут иметь неприемлемую сложность/производительность, такая функция будет представлять для меня только теоретический интерес, и она мне не нужна, потому что я не буду ее использовать. [4/4]
Ответы 3
Можно написать регулярное выражение, которое перечисляет все возможные способы избежать запрещенных подстрок:
([^cf]|c[^bd]|f[^g])*[cf]?$
Однако на практике это довольно неуклюже; в большинстве случаев, вероятно, лучше провести рефакторинг своего мышления.
Здесь показано только, как пропускать строки, которые не являются cb, cd или fg. [cf]?$ в конце должен быть просто [cf]?, если вы встраиваете его в контекст, где за ним должно следовать что-то, хотя, если это что-то b, вы тоже хотите исключить c (потому что в противном случае, упс, вы просто разрешили cb).
a([^cf]|c[^bd]|f[^g])*f?b
Если вы хотите избежать наличия a или b в пропущенной строке, вам также необходимо добавить их в запрещенный набор:
a([^abcf]|c[^bd]|f[^g])*f?b
Все станет несколько сложнее, если ваши реальные строки длиннее одного или двух символов; но это то, о чем вы на самом деле спросили.
Данное регулярное выражение не работает. Этот код: echo '1taa/b///fafgfgcb2abb' | LC_ALL=en_US.utf8 gawk -F '\\|' '{split($0, arr, /a([^cf]|c[^bd]|f[^g])*f?b/, seps); print(seps[1] ", " seps[2])}' — печатает aa/b, abb вместо a/b, ab. Этот код: echo 'affgbcd' | LC_ALL=en_US.utf8 gawk -F '\\|' '{split($0, arr, /a([^cf]|c[^bd]|f[^g])*f?b/, seps); print(seps[1])}' — печатает affgb вместо пустой строки.
* по определению соответствует самой длинной доступной подстроке. В PCRE вы можете сказать *?, чтобы переключиться на нежадное сопоставление, но в Awk вам нужно будет добавить ab к классу запрещенных символов [^cf], чтобы получить что-то подобное. Что касается вашего второго примера, я не думаю, что ваши ожидания верны; он разделяется на пустую строку и остаток cd после «разделителя».
В конечном счете, это именно те причины, по которым я бы старался избегать такого подхода.
<он разбивается на пустую строку и остаток cd после «разделителя»> — если $0 равен affgbcd, он вообще не должен разбиваться: нет подстрок, которые можно было бы использовать в качестве разделителей. Поэтому seps[1] должен быть напечатан как пустая строка (поскольку она не существует), а не affgb. Но ладно, похоже, что невозможно иметь подходящее регулярное выражение...
Регулярное выражение a([^abcf]|c[^bd]|f[^g])*f?b находит совпадение в affgbcd, чего не должно быть: echo 'affgbcd' | LC_ALL=en_US.utf8 gawk -F '\\|' '{print(match($0, /a([^abcf]|c[^bd]|f[^g])*f?b/))}' печатает 1 вместо 0.
предположительно ERE теперь позволяют +?, *?, ??, но может пройти некоторое время, прежде чем реализации догонят
более общее решение:
Вот функция awk, которая принимает строку и три регулярных выражения.
Выходные данные представляют собой список индексов, длин и непересекающихся строк, таких, что:
- rs — совпадения только в начале строки
- re — совпадения в конце строки (любые другие совпадения должны перекрываться с
rs) - rx — не соответствует строке
awk '
function findshort(s,rs,re,rx, nextstart,q,qpos,qtry,pos,spos,slen,elen) {
print s,"-->"
nextstart = 1
while (spos = match((q = substr(s, nextstart)), rs)) {
slen = RLENGTH
qtry = q = substr(q, spos)
qpos = elen = pos = 0
while ((pos = match((qtry = substr(qtry, pos+1)), re)) \
&& ((qpos += pos)+(elen = RLENGTH))<=slen) {
}
if ((qpos+elen)<=slen) break
q = substr(q, 1, qpos+elen-1)
nextstart += spos+length(q)-1
if (!match(q, rx)) {
pos = 1
while (length(q)>0 \
&& pos = match((qtry = substr(q, pos+1)), rs) \
&& length(qtry)>=elen \
&& !match(qtry, rx))
q = qtry
print nextstart-length(q), length(q), q
}
if (!length(q)) ++nextstart
if (nextstart>length(s)) break
}
}
BEGIN {
findshort("1taa/b///fafgfgcb2abb", "a","b","cb|cd|fg")
findshort("0a3cbsbtacc12bbb", "a","b","cb|cd|fg")
findshort("a4cdddbbb5", "a","b","cb|cd|fg")
findshort("aaabcbbaaaaaaefgbbbb", "aa","bb","bc")
findshort("abc", "abc","b","cb|cd|fg")
findshort("abcb", "abc","b","cb|cd|fg")
findshort("abcab", "abc","b","cb|cd|fg")
findshort("00ab2bc11", "ab","bc","$^")
findshort("abcdef", "x*","[bc]","z")
findshort("abcdef", "abcde","d*","z")
findshort("abc", ".?",".?",".")
findshort("abc", ".{0}",".{0}","z")
findshort("abc", ".*",".*","z")
findshort("abbbabaababab", "ab+","b+a","z")
}
'
давая:
1taa/b///fafgfgcb2abb -->
4 3 a/b
19 2 ab
0a3cbsbtacc12bbb -->
9 6 acc12b
a4cdddbbb5 -->
aaabcbbaaaaaaefgbbbb -->
12 7 aaefgbb
abc -->
abcb -->
abcab -->
1 5 abcab
00ab2bc11 -->
3 5 ab2bc
abcdef -->
2 1 b
3 1 c
abcdef -->
1 5 abcde
abc -->
abc -->
1 0
2 0
3 0
abc -->
1 3 abc
abbbabaababab -->
1 5 abbba
8 3 aba
По сути, функция проходит по входной строке и выполняет в цикле:
- извлеките крайний левый хвост, который начинается с
rs- если это невозможно, остановись
- обрезать правую часть до крайнего левого
re, который заканчивается на концеrsили за его пределами- если это невозможно, остановись
- если
rxне совпадает- обрезать LHS до тех пор, пока
rsне будет совпадать нигде, кроме начала (убедившись, чтоreпо-прежнему соответствует, аrxнет) - распечатать обрезанную строку
- обрезать LHS до тех пор, пока
- пропустить обрезанную строку
- если это невозможно, остановись
- иначе начни другой поиск
Результаты получаются путем обработки входных данных слева направо с использованием определенной последовательности операций. Обратите внимание, что при обработке каким-либо другим способом с использованием другого алгоритма возможны другие результаты. Например:
input = abbbabaababab
rs = ab+
re = b+a
rx = z
может быть законно разделено на любое из:
<abbba> ba <aba> bab
abbb <aba> <aba> ab
abbb <aba> ab <aba> b
оригинальный принятый ответ:
Демонстрация общего подхода, как и просили:
awk '
{
printf "original: %s\n", $0
# escape input to ensure availability of substrings for marking
gsub(/=/,"=e")
# now `/=[^e].*/` is guaranteed to not match
# mark negative matches
gsub(/cb|cd|fg/,"=x&")
printf "marked: %s\n", $0
# split
n = split($0, arr, /a([^ab=]|(=[^x]))*b/, seps)
# unmark/unescape results
gsub(/=x/,"", seps[0])
gsub(/=e/,"", seps[0])
for (i=1;i<=n;i++) {
gsub(/=x/,"", arr[i])
gsub(/=x/,"", seps[i])
gsub(/=e/," = ", arr[i])
gsub(/=e/," = ", seps[i])
}
printf "sep[0]: %s\n", seps[0]
for (i=1;i<=n;i++) {
printf "pat[%i]: %s\n", i,arr[i]
printf "sep[%i]: %s\n", i,seps[i]
}
}
' <<'EOD'
1taa/b///fafgfgcb2abb
EOD
давая:
original: 1taa/b///fafgfgcb2abb
marked: 1taa/b///fa=xfg=xfg=xcb2abb
sep[0]:
pat[1]: 1ta
sep[1]: a/b
pat[2]: ///fafgfgcb2
sep[2]: ab
pat[3]: b
sep[3]:
(Глючит - находит крайнюю левую, а не самую короткую)
Если a или b являются строками, а не отдельными символами (например, aaaa, bbbb),
их тоже нужно отметить. Тогда разделение будет выглядеть примерно так:
split($0, arr, /=xaaaa([^=]|(=[^x]))*=xbbbb/, seps)
sep[1] должно быть a/b, а не aa/b.
@lyricallywicked см. исправления
<Если a или b являются строками, а не отдельными символами> — да, a и b в моем вопросе определенно являются строками (технически подстроками, потому что они являются лишь частями входной строки), а не отдельными символами. Например, я мог бы захотеть сопоставить все кратчайшие подстроки, которые начинаются с ab и заканчиваются bc, но не содержат cb, cd или fg. Я не понимаю, как применить этот ответ. Например, я ввожу 00abc11, поэтому sep[1] должно быть abc. Кажется, ни /ab([^ab=]|(=[^x]))*bc/, ни /=xab([^=]|(=[^x]))*=xbc/ не работают?
@lyricallywicked в abc, ab и bc перекрываются, поэтому потребуется другой подход
@EdMorton: Я выбрал a и b так, чтобы весь заголовок вопроса не превышал максимальную длину (150 символов)... Но да, я согласен, мне следовало уточнить это в посте.
@jhnc: Пожалуйста, не удаляйте ответ. Я могу преобразовать весь ввод, чтобы гарантировать, что начальная и конечная подстроки не перекрываются. Если невозможно найти абсолютное кратчайшее, я могу принять самое левое кратчайшее. Но мне нужно еще несколько объяснений вашего /=xaaaa([^=]|(=[^x]))*=xbbbb/ примера. То есть мне нужно знать, как отмечать/сопоставлять начальные/конечные подстроки.
Новый подход @EdMorton - несколько менее эффективный, но более общий. не уверен, что уловил все ошибки обивана
Ну блин! Теперь я не так расстраиваюсь из-за того, что не могу придумать однострочник из головы. Я возился с этим около 10 минут и решил, что краткая однострочная фраза просто не в моих силах. (хотя до сих пор я мало что знал о дизайне DFA)
@DavidC.Rankin, и в моем коде все еще есть ошибки... :-/
@jhnc: findshort("abcb", "abc","b","cb|cd|fg") печатает abcb --> 0 2 ab (правильный вывод: abcb --> 0: нет совпадающих подстрок). findshort("abcab", "abc","b","cb|cd|fg") печатает abcab --> 0 2 ab (правильный вывод — abcab --> 1 5 abcab).
@lyricallywicked Я исправил несколько ошибок. еще тестовые примеры?
@jhnc: мне понадобится некоторое время (до одной недели), чтобы обдумать возможные случаи и проверить производительность. Интересное совпадение: ваше решение использует подход «циклы + условные выражения», но в настоящее время у меня возникают необъяснимые проблемы с производительностью моего собственного решения «циклы + условные выражения» для несвязанной проблемы...
@jhnc: ваше решение «отметить отрицательные совпадения» функционально приемлемо, если я уберу некоторые требования (хотя я еще не проверял его производительность), за исключением одной детали: я бы предпочел иметь одну функцию разделения, основанную на предположении, что a и b обозначают строки (подстроки), а не отдельные символы... Например, если на входе 00ab2bc11 (избегая перекрытия в совпадающей подстроке), начальной подстрокой является ab, конечной подстрокой является bc, то split($0, arr, /=xab([^=]|(=[^x]))*=xbc/, seps) не выводит правильную результат.
@lyricallywicked, ты добавил ab и bc в =x gsub? Я получаю ab2bc в sep[1]. Если у вас есть простые строки, такие как rs/re, я ожидаю, что findshort даст правильный ответ, и производительность должна быть хорошей, поскольку возврат не потребуется.
@jhnc: значит, единственное, что нужно добавить к текущему решению, это gsub(/ab|bc/,"=x&") (где ab и bc — произвольные начальные/конечные подстроки)? Тогда одиночный split($0, arr, /=xab([^=]|(=[^x]))*=xbc/, seps) будет работать во всех случаях (при условии, что перекрытия исключены и меня не волнует, жадно ли совпадает подстрока слева)?
@jhnc: ...поэтому я добавил gsub(/ab|bc/,"=x&") в код. Для 00ab2bc11 он печатает пустую строку для sep[0] и ничего для sep[1], что не является ожидаемым результатом.
@lyricallywicked Я все меньше уверен в том, что исходный код метки работает правильно даже для отдельных символов, а не для строк. Я думаю, будут проблемы, если какой-либо из вариантов в =x gsub перекроется (ab|bc|cb|cd|fg не сможет правильно отметить cbc или bcb - будет пропущен один из bc или cb)
@jhnc: <Я становлюсь менее уверенным в том, что исходный код маркировки работает правильно даже для отдельных символов, а не для строк> — это одна из причин, почему я думал, что подход «отметить отрицательные совпадения» не подойдет для решения проблемы. проблема поиска всех указанных подстрок.
@lyricalwicked да, люди пропустили, что ab и т. д. были заменой для более длинных последовательностей - для приведенных вами примеров маркировка работает (или даже есть регулярное выражение, как показал Тринкот), но в более сложных случаях оно не будет работать, если не будет изменено ( У меня есть идея хранить отметки отдельно, но производительность может быть низкой). В любом случае, поскольку ваши фактические подстроки/регулярные выражения могут перекрываться, я бы забыл о своем первоначальном подходе и попробовал новый код. Его логика верна, хотя ошибки вполне могут быть.
С помощью дизайна DFA и исключения состояний я добрался до этого регулярного выражения:
a([^abcf]|c+[^abcdf]|c*f+(c+f+)*([^abcfg]|c+[^abcdf]))*(c*f+(c+f+)*)?b
Дизайн DFA
Вот DFA, соответствующий описанным вами правилам:
Некоторые примечания:
Я не включил переходы, которые приводят к состоянию отклонения. В частности:
- из состояния 𝐶 переходы для символов
bиdотсутствуют - для состояния 𝐹 переход для символа
gотсутствует - для состояний 𝐴, 𝐵, 𝐶 и 𝐹 переходов для
aнет. - в начальном состоянии нет переходов для символов, кроме
a - состояние принятия 𝐵 вообще не имеет переходов.
Переходы используют синтаксис регулярных выражений. В частности [^ ]. Далее эти переходы будут расширены другим синтаксисом регулярных выражений, например * для нуля или более повторений, + для одного или нескольких повторений, ? для того, чтобы сделать шаблон необязательным и | для альтернатив (ИЛИ).
Переход и ликвидация государства
Цель состоит в том, чтобы постепенно удалять циклы и состояния из DFA, расширяя оставшиеся переходы шаблонами, которые (потенциально) соответствуют более чем одному символу, чтобы в конечном итоге мы получили диаграмму DFA только с состояниями начала и принятия и всего с одним оставшимся переходом. между этими двумя состояниями и которое имеет последнее регулярное выражение.
Во-первых, мы могли бы удалить циклы в состояниях 𝐶 и 𝐹. Затрагиваются все входящие переходы:
Тогда мы могли бы удалить состояние 𝐶. Это означает, что для каждой комбинации входящего/исходящего перехода нам нужно добавить эту последовательность к переходу, который заменяет эту пару (переход непосредственно от источника к цели, пропуская 𝐶). Имеется два входящих и два исходящих перехода, поэтому нам предстоит выполнить работу за 4 комбинации:
Давайте удалим тот цикл, который мы ввели в 𝐹:
Теперь мы можем удалить состояние 𝐹. У него один входящий и два исходящих перехода, поэтому есть две комбинации для замены:
Наконец, мы удаляем состояние 𝐴, что означает, что у нас остался один переход, который включает в себя ноль или более повторений цикла в 𝐴:
Итак, мы получаем регулярное выражение, о котором я упоминал вверху.
Можете ли вы опубликовать псевдокод всего алгоритма для генерации регулярного выражения? Входные данные: 1. Начальная подстрока; 2. Набор запрещенных подстрок; 3. Конечная подстрока. Результатом является регулярное выражение.
Это было бы слишком широко. Надеюсь, моих изменений в ответе будет достаточно, чтобы объяснить, как я действовал и получил результат. См. также Как преобразовать конечные автоматы в регулярные выражения?.
Само регулярное выражение, похоже, соответствует моим потребностям (я проверил его на нескольких входных данных). Но поскольку у меня нет алгоритма генерации (как псевдокода), я не смогу построить регулярные выражения для других ситуаций.
Весьма впечатляюще. Прекрасно объясняет, почему мои попытки придумать однострочник с головы до ног не закончились хорошо...
Решается с помощью отрицательного просмотра вперед
(?!cb|cd|fg), но awk и POSIX/ERE не поддерживают обходные пути.