Regexp помогите написать на перле

Elina74

Чтобы заменял в строке, к примеру [Q] на <Q> за исключением тех случаев, когда [Q] находится внутри тегов [pre]...[/pre]
Между тегами кроме всего прочего могут быть произвольные символы...

artimon

Сделать это одним regexp'ом если и можно, то только в качестве примера того, как делать не надо.
Я бы сначала сохранил все [pre]...[/pre] отдельно, потом сделал всё что надо со строкой, а затем вернул [pre]...[/pre] на место.

Elina74

Понятно. Я так и делал, начал путаться и потому возник вопрос, нет ли способа покороче...
Спасибо.

Barbie29

#!/usr/bin/perl
$_=qq~
asd fdfg[Q] [pre]ee ffd x[Q]x
ee[Q][/pre][Q] [Q] asd fdfg[Q] [pre]
ee ffd x[Q]x ee[Q][/pre]
[Q] [Q]
~;
print "$_\n";
<a href="mailto:(\[pre\].*?\[q\].*?\[/pre\])|\[Q\]@$1?">(\[pre\].*?\[q\].*?\[/pre\])|\[Q\]@$1?</a>"$1":"\<Q\>"@igse;
print "$_\n";
вывод:
[mobile100 vilfred]$ perl aaa.pl
asd fdfg[Q] [pre]ee ffd x[Q]x
ee[Q][/pre][Q] [Q] asd fdfg[Q] [pre]
ee ffd x[Q]x ee[Q][/pre]
[Q] [Q]
asd fdfg<Q> [pre]ee ffd x[Q]x
ee[Q][/pre]<Q> <Q> asd fdfg<Q> [pre]
ee ffd x[Q]x ee[Q][/pre]
<Q> <Q>
[mobile100 vilfred]$
лоигика такая: если существует переменная $1, то её печатать, иначе заменять \[Q\], которое по условию или "|"...

Barbie29

ой...
I A aaa.pl (perl) Row 6 Col 19 0:10 Ctrl-K H for help
#!/usr/bin/perl
$_=qq~
asd fdfg[Q] [pre]ee ffd x[Q]x
ee[Q][/pre][Q] [Q] asd fdfg[Q] [pre]
ee ffd x[Q]x ee[Q][/pre]
[Q] [Q]
~;
print "$_\n";
(\[pre\].*?\[q\].*?\[/pre\])|\[Q\]@$1?"$1":"\<Q\>"@igse;
print "$_\n";

Barbie29

почемуж не надо то? если для s! по документации предусмотрен ключ e, помимо ключей igsmox, почему бы им не воспользоваться?

Elina74

Че-то я не очень въехал. Что значат значки @ и ?
Можно переписать в виде типа


$str = "всякая белиберда";

if($str =~ /всякие шаблоны/gise){

   $str =~ s/всякие шаблоны2/всякие шаблоны3/gise;

}

Barbie29

короче, если указывается тип шаблона, например буква m или s, то вместо m// или s/// можно писать любые символы(хоть русские) m! или s! или @ или @@ (для s/// можно писать и s{}{} вобщем, там много заморочек...

Elina74

А "?:" это условный оператор?

Barbie29

вопросительный знак - это минимализация действия квантификатора(ограничение жадности типа если a.*a - найдет все символы в строке(жадный находящиеся между самыми дальними adfggasdfa (подстроку dfggasdf то a.*?a найдет подстроку dfgg. Короче см. тут:
http://genphys.phys.msu.ru/~dmitriyk/perl/regex.shtml
вобщем без поллитры тут много не наваяешь...

Barbie29

ключ е делает левую часть регекспа компилируемой
s/regex/условие?да:иначе/e

Elina74

Клево. А ведь проверка наличия [Q] внутри [pre]...[/pre] не обязательно. Работает и так:


$str =~ (\[pre\].*?\[/pre\])|\[Q\]@$1?"$1":"\<Q\>"@igse;

bleyman

такие вещи не следует делать регкспами, наверное. По крайней мере, в один этап. Я тут как-то хотел выдрать из файла кусок одним регекспом - типа чтобы он засасывал весь файл.
Обнаружил, что
(.\n)*zzz
тормозит квадратично (есди в файле нет строки zzz). И даже понял почему.

Julie16

Хммм... А почему?

bleyman

Берёт первый символ, начинает искать подстроку в оставшемся (линейно).
Берёт второй символ, ...
...
= квадрат пополам.
Это лечится, если поставить вначале ^, но мне нужно было multiline.
Вообще глядя на этот пример легко понять, как вообще умеют тормозить НКА. Тормозить они умеют полиномиально (с любой наперёд заданной степенью соответствующей количеству значков * и + но не сильнее.
Например, (.|\n)*a(.|\n)*z на строке из aa...a будет тормозить кубически.

tokuchu

Берёт первый символ, начинает искать подстроку в оставшемся (линейно).
Берёт второй символ, ...
...
= квадрат пополам.
Есть более эффективные способы поиска подстроки.
ообще глядя на этот пример легко понять, как вообще умеют тормозить НКА. Тормозить они умеют полиномиально (с любой наперёд заданной степенью соответствующей количеству значков * и + но не сильнее.
Например, (.|\n)*a(.|\n)*z на строке из aa...a будет тормозить кубически.
IMHO, автомат работает за линейное время. Проблема скорее всего в скорости построения этого автомата, но оно ограничено полиномом конечной степени от длины регулярного выражения.

bleyman

>Есть более эффективные способы поиска подстроки.
Я бы хотел обратить ваше внимание на то, что автомат не ищет подстроку. Ищет подстроку вот такой регексп: "zzz"
А у нас тут "(.|\n)*zzz" - это разные регеспы, и они по разному работают.
>IMHO, автомат работает за линейное время.
>Проблема скорее всего в скорости построения этого автомата
Не уверен - не пизди. Я - уверен, я проверял.

tokuchu

Я бы хотел обратить ваше внимание на то, что автомат не ищет подстроку. Ищет подстроку вот такой регексп: "zzz"
А у нас тут "(.|\n)*zzz" - это разные регеспы, и они по разному работают.
Если это ищет автомат, то нам посрать что он ищет. Автоматы работают не более чем за линейное время от длины подаваемой строки.
Не уверен - не пизди.
Если ты уверен, то напиши где я напиздел. Иначе - не пизди сам.
Я - уверен, я проверял.
Что именно ты проверял? Есть теория - я тебе написал с какой скоростью и что должно работать. Если ты проверял что-то другое, то напиши что и как.

Dasar

> Автоматы работают не более чем за линейное время от длины подаваемой строки.
В общем случае, сложность автомата - это кол-во состояний на кол-во условий перехода.
В идеале за счет расхода памяти - можно сделать, чтобы переходы выполнялись за константное время.
Но если, например, строки уникодные - то на каждое состояние будет уходить 65к * 4 = 260к
В сложных случаях, например, когда есть параллельные ветки и т.д, - кол-во состояний тоже может расти экспонециально.
например, в запросе:
[Hh][Ee][Ll][Ll][Oo], [Ww][Oo][Rr][Ll][Dd]
кол-во состояний получается 1024
Соответственно, честные автоматы (с одним состоянием и константным временем перехода) делаются не всегда

rosali

честные автоматы
Если 1024 состояния закодированы 10 битами, что ж в этом нечестного? Просто формулу перехода сложнее вычислять, чем просто в таблицу слазить.
чтобы переходы выполнялись за константное время
Константные по сравнению с чем? Все переходы во всех автоматах за одно и то же время? Вряд ли. Таблица может в кеш не влезть и т.п.

tokuchu

В общем, конечно, это так, но:
Но если, например, строки уникодные - то на каждое состояние будет уходить 65к * 4 = 260к
Это без оптимизаций и с расчётом на максимум 256^4 состояний. Даже если хранить не плоскую таблицу, а как-нибудь изощряться, то всё равно автомат не начнёт работать за полиномиальное время, где степень полинома зависит от чиса звёздочек.
например, в запросе:
[Hh][Ee][Ll][Ll][Oo], [Ww][Oo][Rr][Ll][Dd]
кол-во состояний получается 1024
Почему-то я сильно сомневаюсь, что автомат, разбирающий этот регэксп, будет иметь 1024 состояния. Ну если не рассматривать тот вариант, что при желании такое можно придумать, а при ещё большем желании можно и ещё развернуться, но цель-то не в этом.

tokuchu

Но если, например, строки уникодные - то на каждое состояние будет уходить 65к * 4 = 260к
Ещё... Памяти нужно не больше чем
C * (<число_состояний_автомата> * <число_различных_символов_в_регэкспе> + <число_символов_в_алфавите>)
с сохранением линейности автомата.
Поэтому каждое состояние не должно занимать столько места. Только в случае если у нас в регэкспе стоят все или почти все возможные символы.
PS. Хотя ты, наверное, и сам уже догадался.

bleyman

Автомат-то работает за линейное время, да. Это я не прав конечно был.
Проверял я то, что автомат строится быстро, а ищет медленно.
Причина этого в том, как мне кажется, что они не напускают автомат на всю строку сразу, а осуществляют бэктрекинг ручками (мб чтобы размер автомата не рос слишком быстро, не знаю).
То, как это происходит, я описал выше.
Если у кого-нибудь есть под рукой что-нибудь кроме .NET Regex Engine, можно проверить, вдруг это чисто его особенность.
Типа, как долго работает .*zzz на длинной строке aaa...a
ЗЫ: К чему это вы всё про уникод и таблички говорите? Понятно, что там какое-то специальное представление, поиск по которому всё равно занимает O(1) или O(ln(n (что одно и то же как правило).

Dasar

> C * (<число_состояний_автомата> * <число_различных_символов_в_регэкспе> +
> <число_символов_в_алфавите>) с сохранением линейности автомата
Каким образом тогда будет осуществляться константность перехода?
т.е. каким образом будет осуществляться уход от множества if-ов:


case State5:

  if (ch == 'a')

     state = State6;

  if (ch == 'd')

     state = State4;

  if (IsDigit(ch

    state = State7;

//и т.д.

имхо, для константности перехода - памяти все-таки нужно пропорционально 'кол-во состояний * кол-во символов алфавита'

tokuchu

Если у кого-нибудь есть под рукой что-нибудь кроме .NET Regex Engine, можно проверить, вдруг это чисто его особенность.
Типа, как долго работает .*zzz на длинной строке aaa...a
В тестах ниже файлы содержат одну строку из букв "a" длиной соответсвующей названию:


$ time grep ".*zzz" file1M

real    0m0.024s

user    0m0.010s

sys     0m0.012s



$ time grep ".*zzz" file16M

real    0m0.298s

user    0m0.185s

sys     0m0.099s



$ time grep ".*zzz" file128M

real    0m2.608s

user    0m1.413s

sys     0m0.887s

Результаты выглядят достаточно линейно...

Julie16

Эээээ... Как бы сказать... У FJ в первом примере нужно еще было получать какой-то кусок из файла. А это не совсем регексп. У тебя же именно регексп - проверка соответствия на шаблон.
.*zzz и (.*)zzz - очень разные вещи. Второй - и не регексп вовсе.

tokuchu

В упрощённом виде:
Каждому встречающемуся символу в регулярном выражении присваивается номер, всем остальным символам тоже присваивается один и тот же номер. (1-я таблица символ_алфавита->номер)
Дальше строится автомат уже над этими номерами. (2-я таблица состояние*номер->состояние).

tokuchu

Ну тут есть конечно заморочки, но мне кажется, что здесь вопрос в количестве памяти, которую можно заюзать... хотя по идее и так надо будет хранить всю найденную строчку, поэтому в любом случае её надо юзать.
Потестил sed-ом - вот результаты:


$ time sed 's/\(.*\)zzz/\1eee/' file8k > /dev/null

real    0m0.609s

user    0m0.602s

sys     0m0.003s



$ time sed 's/\(.*\)zzz/\1eee/' file16k > /dev/null

real    0m2.432s

user    0m2.414s

sys     0m0.013s



$ time sed 's/\(.*\)zzz/\1eee/' file32k > /dev/null

real    0m9.787s

user    0m9.676s

sys     0m0.024s
Действительно видна зависимость n^2 от длины строки. Фигня какая-то . Не поверил. Сделал на perl:


$ cat 1.pl

#!/usr/bin/perl

$_ = <>;

s/(.*)zzz/$1eee/;

print $_;



$ time perl 1.pl < file1M > /dev/null

real    0m0.018s

user    0m0.011s

sys     0m0.006s



$ time perl 1.pl < file16M > /dev/null

real    0m0.279s

user    0m0.139s

sys     0m0.056s



$ time perl 1.pl < file128M > /dev/null

real    0m4.555s

user    0m1.073s

sys     0m0.555s
Результаты радикально отличаются. Осталось понять кто не прав...

Maurog

кстати про 1024 состояния....
идем сюда
http://gibbon.kinnet.ru/uzhas/index.php
и вводим ето
(HvhEveLvlLvlOvoWvwOvoRvrLvlDvd)
получаем 22 состояния
кто-нить может дать строку, чтобы вершин в источнике было больше, чем символов в строке?:)

Dasar

Без звездочек и отрицаний не интересно.

Maurog

звездочка-ето итерация
к тому же в примере [Hh][Ee][Ll][Ll][Oo], [Ww][Oo][Rr][Ll][Dd]
я не увидел звездочек=)

Dasar

звездочка имелось ввиду, как произвольный символ.
> к тому же в примере [Hh][Ee][Ll][Ll][Oo], [Ww][Oo][Rr][Ll][Dd]
значит, пример, неправильно - слишком простой.

tokuchu

Без звездочек и отрицаний не интересно.
Разве от "звёздочек" намного хуже будет?
Оставить комментарий
Имя или ник:
Комментарий: