sed: отрицание backreference в regex

[SLEDopit]

цель: удалить из текста строки без повторяющихся элементов перед и после указанного словом. слово может повторяться в одной строке несколько раз.

в интернетах написано, что это делается так:
/(.*)word(?!\1)/

но sed ругается или ничего не удаляет:

Код: Выделить всё

 $ echo {a,b,c}{word,d,e}{a:,b:,c:}|tr ':' '\n'|sed '/\(.\)word(?!\1)/d'
печать всех вариантов

 $ echo {a,b,c}{word,d,e}{a:,b:,c:}|tr ':' '\n'|sed -r '/(.)word(?!\1)/d'
sed: -e expression #1, char 15: Invalid preceding regular expression

 $ echo {a,b,c}{word,d,e}{a:,b:,c:}|tr ':' '\n'|sed -r '/(.)word(!\1)/d'
печать все вариантов

/(.)word\1/!d не подходит, т.к. в строке "word" может встречаться несколько раз.

[t.t]

Конкретный пример строк можно?

[watashiwa_daredeska]

в интернетах написано, что это делается так:
/(.*)word(?!\1)/

Это точно для sed написано? Больше похоже на perl.
Для sed придумалось:

Код: Выделить всё

sed -rn 'h;s/(.)word\1//g;ta;:a;s/word//;t;g;p'

Shell

$ cat | sed -rn 'h;s/(.)word\1//g;ta;:a;s/word//;t;g;p' <<EOF > xaworday > xaworday xawordcy > xawordcy > EOF xaworday

[watashiwa_daredeska]

P.S. Бага. В первой замене надо не удалять, а заменять на символ, которого нет в word, например, \n:

Shell

$ word=xxxx; cat | sed -rn 'h;s/(.)'"$word"'\1/\n/g;ta;:a;s/'"$word"'//;t;g;p' <<EOF xa${word}ay xa${word}ay xa${word}cy xa${word}cy xxx${word}xxx EOF xaxxxxay

[watashiwa_daredeska]

Хотя, тоже не идеал, есть случаи, когда это работает не так, как изначальный перловый regexp.

[SLEDopit]

Конкретный пример строк можно?

Код: Выделить всё

12_file_12_file_12
 12_file_12_file_23
 12_file_12_file_34
 12_file_23_file_12
 12_file_23_file_23
 12_file_23_file_34
 12_file_34_file_12
 12_file_34_file_23
 12_file_34_file_34
 23_file_12_file_12
 23_file_12_file_23
 23_file_12_file_34
 23_file_23_file_12
 23_file_23_file_23
 23_file_23_file_34
 23_file_34_file_12
 23_file_34_file_23
 23_file_34_file_34
 34_file_12_file_12
 34_file_12_file_23
 34_file_12_file_34
 34_file_23_file_12
 34_file_23_file_23
 34_file_23_file_34
 34_file_34_file_12
 34_file_34_file_23
 34_file_34_file_34

необходимо выделить строки, где до и после _file_ стоят одинаковые числа, т.е. из данных строк будет выделена только одна: 12_file_23_file_34

Хотя, тоже не идеал, есть случаи, когда это работает не так, как изначальный перловый regexp.

хм, но все равно спасибо. пока вроде на исключения не наткнулся.

[watashiwa_daredeska]

где до и после _file_ стоят одинаковые числа

цифры?

ока вроде на исключения не наткнулся.

Исключения могут быть в том случае, если имеются перекрытия. Например, 1_file_2_file_3 — «2» здесь является разделителем и для первого, и для второго _file_, поэтому 1_file_1_file_1 не будет «выделено». Ещё хуже, когда word и разделители имеют пересекающийся алфавит и могут перекрываться ещё суровее: word="abcabc"; line="aabcabcabcc" — эта строка вполне удовлетворяет требованиям (т.е. не удовлетворяет исходному regexp'у для удаления), но распознана не будет.

[SLEDopit]

цифры?

да, опечатался (:

Исключения могут быть в том случае, если имеются перекрытия.

такие варианты исключены, поэтому спасибо большое. ваше решение полностью подходит.

[drBatty]

в интернетах написано, что это делается так:
/(.*)word(?!\1)/

а в мануале написано, что sed не поддерживает такие выражения. и это не баг, а фича.

[SLEDopit]

и это не баг, а фича.

уж больно неудобная фича (:

[sash-kan]

в интернетах написано, что это делается так:
/(.*)word(?!\1)/

это perlre. если не ошибаюсь, lookbehind-ом называется. или lookahead-ом.

конструкция

Код: Выделить всё

sed '/\(\(.\)_file_\2\)\{2\}/s/$/\*/'

удовлетворяет приведённому примеру и этому описанию:

необходимо выделить строки, где до и после _file_ стоят одинаковые числа, т.е. из данных строк будет выделена только одна: 12_file_23_file_34

(помечает искомую строку звёздочкой)

уж больно неудобная фича

это «фича» perlre. в sed её никто не будет «запихивать».

p.s. читайте Фридла, и будет вам счастье и мир во всём мире.

[drBatty]

уж больно неудобная фича

за то - быстрая.

это «фича» perlre. в sed её никто не будет «запихивать».

почему? вроде пытаются переделать sed... а если посмотреть исходник текущей версии, то видно, что можно включить perl-синтаксис... (у меня что-то не получилось)

[ZyX]

в интернетах написано, что это делается так:
/(.*)word(?!\1)/

это perlre. если не ошибаюсь, lookbehind-ом называется. или lookahead-ом.

Здесь он смотрит после (или впереди) текущей позиции — lookahead.

это «фича» perlre. в sed её никто не будет «запихивать».

А также огромного количества других perl’оподобных движков регулярных выражений. Присутствует ещё и в Vim’е.

Кстати, а зачем это было делать именно на sed? Если в том, что вы написали в первом сообщении заменить «sed -r '/.../d'» на «perl -p -i -e 'undef $_ unless /.../'», то всё работает. Ещё можно попробовать «grep -P '...'». Но для этого grep должен быть собран с поддержкой pcre.

[watashiwa_daredeska]

за то - быстрая.

С backreference всё равно не быстрая, а sed поддерживает backreference.

[drBatty]

С backreference всё равно не быстрая, а sed поддерживает backreference.

не всё равно. действительно, с br выражение невозможно скомпилировать перед поиском (потому-что оно меняется в процессе поиска), однако в любом случае поиск выполняется за один проход. А вот с пред(после)просмотром 1 проход часто невозможен, потому поиск выполняется в этом случае ещё медленнее (на практике часто намного медленнее).

Ещё можно попробовать «grep -P '...'». Но для этого grep должен быть собран с поддержкой pcre.

ещё можно попробовать sed, с поддержкой pcre

[watashiwa_daredeska]

однако в любом случае поиск выполняется за один проход.

Можно пруфлинк на алгоритм? Естественно, с сохранением исходного авторства — миллион баксов, всё-таки :) Однопроходный алгоритм Томпсона я знаю, но:

Backreferences. As mentioned earlier, no one knows how to implement regular expressions with backreferences efficiently, though no one can prove that it's impossible either. (Specifically, the problem is NP-complete, meaning that if someone did find an efficient implementation, that would be major news to computer scientists and would win a million dollar prize.)

[ZyX]

Ещё можно попробовать «grep -P '...'». Но для этого grep должен быть собран с поддержкой pcre.

ещё можно попробовать sed, с поддержкой pcre

Grep с поддержкой pcre получается при указании соответствующего USE флага устанавливается без дополнительных ухищрений и отлично работает. Sed’а с поддержкой pcre в репозитории нет, а, судя по сообщениям выше, я от того потерял совсем немного.

[SLEDopit]

sed '/\(\(.\)_file_\2\)\{2\}/s/$/\*/'

Спасибо, но все же это немного не то. Вариант watashiwa_daredeska больше подходит.
Просто если я напишу вот так:

Код: Выделить всё

sed -r "/((.)_file_\2){${#CONST}}/s/$/\*/"

то перестает работать при длине CONST > 2 (просто у меня не всегда только 2 _file_ в строке, заранее точно неизвестно их количество, а длина CONST соотвествует количеству _file_.

(Specifically, the problem is NP-complete, meaning that if someone did find an efficient implementation, that would be major news to computer scientists and would win a million dollar prize.)

Эх, не тем я занимаюсь (:

Ещё можно попробовать «grep -P '...'».

Попробовал. Только он, по ходу, с русскими символами особо работать не умеет. Цифры и латиница - нормально, русские - ничего не выдает.

[drBatty]

Можно пруфлинк на алгоритм? Естественно, с сохранением исходного авторства — миллион баксов, всё-таки :)

info sed
вы видимо не поняли... старые ссылки просто сохраняются в структуре наподобие стека. В sed допустимо всего 10 ссылок, потому есть жестокие ограничения... При таких условиях даже $1000 не получить...
алгоритм - в любом дистрибутиве.

Specifically, the problem is NP-complete, meaning that if someone did find an efficient implementation, that would be major news to computer scientists and would win a million dollar prize.

угу. если N*M будет большой новостью. а строчка*10 (максимум) - это как-то не интересно...

Sed’а с поддержкой pcre в репозитории нет, а, судя по сообщениям выше, я от того потерял совсем немного.

согласен. ИМХО sed с перловыми RE ещё и глючит... В любом случае - лучше использовать perl, если это действительно надо.

Попробовал. Только он, по ходу, с русскими символами особо работать не умеет. Цифры и латиница - нормально, русские - ничего не выдает.

попробуйте перевести в однобайтовую кодировку, а уж потом обработать. sed умеет и так... но лучше так не делать...

[ZyX]

Ещё можно попробовать «grep -P '...'».

Попробовал. Только он, по ходу, с русскими символами особо работать не умеет. Цифры и латиница - нормально, русские - ничего не выдает.

Тоже есть такая проблема, но только если со строками надо что-то делать (например, напечатать только часть строки из-за флага -o). Если надо просто решить, печатать ли строку или нет, то всё нормально. grep-2.5.4-r1 USE="nls pcre".

[watashiwa_daredeska]

угу. если N*M будет большой новостью. а строчка*10 (максимум) - это как-то не интересно...

О чём это Вы? Какие N*M?

Shell

$ for i in $(seq 20 2 ${#a}); do \ b=${a:0:$i}; \ echo $b; \ time (echo $b | sed -rn 's/^(.+)(.+)(\1\2|\2\1)+$/\1 \2/p'); \ done ababababbaabababbaba a b real 0m0.666s user 0m0.664s sys 0m0.000s ababababbaabababbabaab a b real 0m2.647s user 0m2.632s sys 0m0.000s ababababbaabababbabaabab a b real 0m16.262s user 0m16.261s sys 0m0.000s ababababbaabababbabaababba a b real 1m16.733s user 1m16.721s sys 0m0.012s ababababbaabababbabaababbaab a b real 7m25.733s user 7m25.612s sys 0m0.080s ababababbaabababbabaababbaabab <тут я уже не дождался>

Как видите, в регекспе всего 2 группы \1 и \2, строчка растет линейно на 2 символа, а время экспоненциально. Так что, никаких N*M.

[drBatty]

а время экспоненциально.

ИМХО должно расти квадратично, а вовсе не экспоненциально.
Хотя в вашем скрипте - да, экспоненциально.
Вот если-бы вы искали в строке длинной M последовательность из N символов, то время было-бы N*M, у вас-же N с каждым просмотренным символом увеличивается, и получается экспонента (точнее конечный ряд).

т.е. поиск в строке(точнее в не просмотренном хвосте) \1 производится довольно просто - sed знает где начинается \1, и хранит указатель на эту br. Ну и затем тупо проверяет символы в строке на совпадение с ссылками в \1. (могу и напутать, смотрел этот код с пол-года назад).

т.о. если мы ищем шаблон /ABCD/ в строке из N символов, то каждый символ(в строке) будет просмотрен 1 раз - шаблон скомпиллируется. А вот если искать шаблон /(.)\1/, то каждый символ будет просмотрен дважды (кроме первого) на совпадение с прошлым символом. Однако, вся строка будет просмотрена всего 1 раз.

В данном случае sed может запомнить 9 указателей на ссылки, но всё сильно усложнится, если сделать пред(после) просмотр как в перле.

[watashiwa_daredeska]

А вот если искать шаблон /(.)\1/

Это очень хороший шаблон — тут группа начинается и заканчивается в фиксированном месте. Если /.*(.*)\1/, то всё гораздо хуже — каждый символ может быть просмотрен N^2 раз (перепробовать разные начала и концы группы \1), пока не сматчится это самое \1. Ну, либо соответствующее увеличение кол-ва памяти. В общем, это уже далеко не тот простой DFA из алгоритма Томпсона.

[drBatty]

Это очень хороший шаблон — тут группа начинается и заканчивается в фиксированном месте. Если /.*(.*)\1/, то всё гораздо хуже — каждый символ может быть просмотрен N^2 раз (перепробовать разные начала и концы группы \1), пока не сматчится это самое \1. Ну, либо соответствующее увеличение кол-ва памяти.

полностью согласен. тут алгоритм надо менять.
вот ещё пример: отрезание ровно половины строки c одинаковыми символами.

Shell

$ echo 'ZZZZZZZZZZZZZZZZZZZ' | sed -r 's/(.*)\1/\1/' ZZZZZZZZZZ

тут находится N/2 совпадений, и берётся последнее, самое большое. Конечно поделить строку пополам можно намного быстрее. (за время пропорциональное O(1)). вот только sed этого не умеет :(

[watashiwa_daredeska]

полностью согласен. тут алгоритм надо менять.

Тут надо отказываться от backreferences :)
На самом деле, я ошибся — там N^3: N (исходные, по Томпсону) * N (перебор точек начала группы) * N (перебор точек конца). Очередная группа с backreference даёт ещё *N^2 в общем случае, но может и N, если начало совпадает с концом предыдущей, например. Да, существуют оптимизации для часто используемых случаев, но они не полны и всегда можно сочинить ситуацию, когда эти оптимизации просядут и получится полноценный перебор со всеми вытекающими.

[drBatty]

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

с другой стороны мне на практике обычно попадаются случаи, когда намного быстрее сделать без br. Как в делении пополам - ведь sed в любой момент знает длину строки, и может с лёгкостью отрезать половину (наверное за 5-10 тактов).