The OpenNET Project / Index page

[ новости /+++ | форум | wiki | теги | ]

Компания Google открыла исходные тексты библиотеки регулярных выражений RE2

11.03.2010 23:56

Компания Google открыла под лицензией BSD исходные тексты RE2, написанной на языке C++ библиотеки для организации выполнения PCRE-совместимых регулярных выражений. Библиотека отличается высокой скоростью работы, хорошей безопасностью, поддержкой использования в многопоточных программах. RE2 позиционируется в качестве альтернативы реализаций регулярных выражений в PCRE, Perl и Python, особенно эффективной при обработке больших объемов данных.

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

  1. Главная ссылка к новости (http://google-opensource.blogs...)
Лицензия: CC-BY
Тип: К сведению
Ключевые слова: pcre, regex, re2, google
При перепечатке указание ссылки на opennet.ru обязательно
Обсуждение (43) Ajax | 1 уровень | Линейный | Раскрыть всё | RSS
  • 1.1, Аноним (-), 00:09, 12/03/2010 [ответить] [﹢﹢﹢] [ · · · ]  
  • +1 +/
    лучше чем буст?
     
     
  • 2.3, zhus (ok), 00:33, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +1 +/
    да :)
     
     
  • 3.11, pavlinux (ok), 01:53, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    >да :)

    sed !? Не?

     

  • 1.2, LolzN00b (?), 00:22, 12/03/2010 [ответить] [﹢﹢﹢] [ · · · ]  
  • –7 +/
    У Google пока ничего хорошего не было, кроме, быть может, поиска.
     
     
  • 2.4, ASM (??), 00:34, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    Поиск построенный на плохих регекспах... Вероятно всё скоро измениться...
     
     
  • 3.13, Онаним (?), 03:59, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    В поиске Google уже можно использовать regexp-ы?? Я опять проспал обед?
     
     
  • 4.23, ПринцЧорнойТьмы (ok), 08:53, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    http://www.google.com/codesearch -- тут можно.
     
  • 2.6, Ноним (?), 00:41, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    google search, google mail и самое главное google adwords и adsense (на них они сделали весь свой капитал) это о популярных продуктах.
    А так их продукты все хороши
     
     
  • 3.14, аноним (?), 04:41, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • –5 +/
    Поиск да codesearch очень да web-почта, да еще и прямо у большого брата, хорош... текст свёрнут, показать
     
     
  • 4.17, Ноним (?), 06:07, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +3 +/
    "ad* это поганая реклама, ее хорошей может разве что больной назвать."

    Если бы ты на ней деньги умел зарабатывать, ты бы так не говорил.

    "не-web проекты, как-то protocol buffers, google perftools."
    Кстати да, MapReduce etc

    "Почти все остальное откровенный мусор - браузер-троян"
    Ложь, вы слышали звон каких-то фанатиков и толком не стали разбираться в чем дело, советую вам еще раз пойти по интернетам и собрать информации о Chrome. Клон Iron был создан только ради PR.

     
  • 3.10, pavlinux (ok), 01:46, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    Некоторые люди, сталкиваясь с проблемой, думают,
    "- Я знаю, я буду использовать регулярные выражения",
    Теперь у них есть две проблемы. :)

                                   (c) Джэйм Завински

     

  • 1.9, pavlinux (ok), 01:32, 12/03/2010 [ответить] [﹢﹢﹢] [ · · · ]  
  • –1 +/
    > $ perl -e '("a" x 100000) =~ /^(ab?)*$/;'
    > Segmentation fault (core dumped)
    >$

    pavel@suse64:/tmp> perl -e '("a" x 100000) =~ /^(ab?)*$/;'
    pavel@suse64:/tmp> echo $?
    0

    Просто в гугле юзают х...вый Perl :)

     
  • 1.12, iZEN (ok), 02:45, 12/03/2010 [ответить] [﹢﹢﹢] [ · · · ]  
  • –2 +/
    Почему под BSDL? (Риторический вопрос)
     
     
  • 2.15, аноним (?), 04:42, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    >Почему под BSDL? (Риторический вопрос)

    А под чем еще?

     
     
  • 3.21, СуперАноним (?), 07:08, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • –2 +/
    Библиотеку логично под LGPL
     
     
  • 4.25, www2 (ok), 09:27, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +2 +/
    Логично для кого?
     
  • 2.22, Аноним (-), 07:25, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • –2 +/
    потому что своя свобода дороже свободы какого-то там кода
     
  • 2.24, Michael Shigorin (ok), 09:20, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    >Почему под BSDL? (Риторический вопрос)

    Видимо, потому что PD не по всем юрисдикциям признаётся, а смысл выпуска -- стандартизировать реализацию де-факто.  Гругря им сиренево в крапинку, потому как ни возврата кодом, ни тем более денег от этого напрямую не ожидают.

     

  • 1.16, ACCA (ok), 05:43, 12/03/2010 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    >Для обработки регулярных выражений в RE2 применен метод автомата (http://swtch.com/~rsc/regexp/regexp1.html), отличающийся линейной

    Походу беспонтовый гон, либо в 2007 году был баг в Perl 5.8.7.


    $ perl -e '$n = 100; $x="a?"x $n . "a" x $n; $t = "a" x 100000; if ($t =~ /$x/){ print "match\n"; }'

    match

    Perl 5.10.0 отработал мгновенно, а обещали 10**15 лет.

     
  • 1.26, Дмитрий Телегин (?), 09:36, 12/03/2010 [ответить] [﹢﹢﹢] [ · · · ]  
  • +/
    >С точки зрения потребления памяти, размер стека в RE2 имеет фиксированную величину

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

     
     
  • 2.27, Карбофос (ok), 10:14, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    поиск результатов скана снифера? если бы я часто такое использовал, то написал бы программку с доступом к файлу блоками. максимальный размер памяти - размер блока * 2, чтобы не было особых потерь в скорости скана и учитывать то, что строка может быть в двух блоках. для такой задачи не нужна вся оперативка :)
    чем искал-то?
     
     
  • 3.30, Unixoid_потому_что_кривые_руки_писали_этот_модуль (ok), 12:46, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    В boost кстати блочные регэкспы есть, я даже юзал когда-то вроде, уже не помню.
     
     
  • 4.32, Карбофос (ok), 13:39, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    спасибо за инфу, надо будет посмотреть...
     
  • 3.33, Дмитрий Телегин (?), 14:07, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +3 +/
    >чем искал-то?

    Написал свою маленькую шуструю программку, позволяющую искать в разных кодировках и использующую фиксированный буфер памяти, но без регулярных выражений :)
    http://sourceforge.net/projects/findstr/

     
     
  • 4.35, Карбофос (ok), 16:18, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    а вот за открытый проект - плюсик
     
     
  • 5.37, Аноним (-), 18:21, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    Ну разве что за это :)

    Потому что аффтар явно не осилил в дупель стандартную, требуемую POSIX'ом опцию -F (grep -F) ... Я так ищу в *.iso и *.gho и *.tib - пожирание быстро доходит до 500KiB и больше не растёт. Deban Lenny, размер имиджей - один DVD (4.3GB).

     
     
  • 6.39, Карбофос (ok), 20:14, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    ну может он делал мультиплатформенную прогу? в виндах с такими фишками, как grep, вообще полный абзац. кстати, я про опцию -F не знал (стыдно!). просто сканировать как-то большие файлы не приходилось...
     
     
  • 7.40, Xaionaro (ok), 14:21, 13/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    Под винду ж вроде существует пакет GNU утилит.
     
  • 7.42, Mna (??), 16:24, 13/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    >ну может он делал мультиплатформенную прогу? в виндах с такими фишками, как
    >grep, вообще полный абзац. кстати, я про опцию -F не знал
    >(стыдно!). просто сканировать как-то большие файлы не приходилось...

    Cygwin существует и давно стабильно работает (http://cygwin.com)

    Недавно доделали работу с UTF-8 в консоли (bash), что не может не радовать.

    Там так же хорошо работают man и info.

     
     
  • 8.43, Карбофос (ok), 17:12, 13/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    хех да знаю я про это, народ только далеко не все вантузятники это знают ... текст свёрнут, показать
     
  • 7.46, Дмитрий Телегин (?), 08:58, 15/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    > ну может он делал мультиплатформенную прогу? в виндах с такими фишками, как grep, вообще полный абзац. кстати, я про опцию -F не знал (стыдно!). просто сканировать как-то большие файлы не приходилось...

    Не кросплатформенную, я на Debian давно. Кстати если бы опция -F работала, то наверное не писал бы своего :)

     
  • 6.45, Дмитрий Телегин (?), 08:51, 15/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    > аффтар явно не осилил в дупель стандартную, требуемую POSIX'ом опцию -F

    Осилил и к сожалению проку от неё было немного. Если она сейчас работает как положено, то только рад :) да и моя программка актуальности не потеряла: и буфер можно задать и кодировки.

     
     
  • 7.49, Дмитрий Телегин (?), 09:52, 15/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    > Если она сейчас работает как положено, то только рад

    Только что потестил опцию F и ничего радостного...

    dd if=/dev/zero of=test bs=1M count=2000
    grep -F qwer test

    У меня на ноутбуке всего 1 Гб и через несколько секунд я получил:
    grep: test: Невозможно выделить память

    Для моей программки такие поиски для оперативки ничего не стоят, как собственно и поиски на /dev/sda :)

     

  • 1.28, svn (??), 10:26, 12/03/2010 [ответить] [﹢﹢﹢] [ · · · ]  
  • +1 +/
    Не пойму ажиотажа.

    backreference NOT SUPPORTED. Вот и весь секрет трудоёмкость линейной.

     
     
  • 2.31, DeadLoco (ok), 12:59, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +1 +/
    Да там не только бекреференсы пострадали, а вообще все тяжелые операции, включая lookahead/lookbehind. Фигня, короче.
     
     
  • 3.38, Аноним (-), 18:32, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    >Фигня, короче.

    Ну чего же сразу фигня то?
    А если не нужны баки, а скорость и небольшое предсказуемое потребление рамы - нужны?

    PS: man grep, "Known Bugs" section:

    Large repetition counts in the {n,m} construct may cause grep to use lots of  memory. In addition, certain other obscure regular expressions require exponential time and space, and may cause grep to run out of memory.

    Back-references are very slow, and may require exponential time.

     
     
  • 4.44, DeadLoco (ok), 19:05, 13/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    >>Фигня, короче.
    >
    >Ну чего же сразу фигня то?
    >А если не нужны баки, а скорость и небольшое предсказуемое потребление рамы - нужны?

    Тогда не нужно сравнивать с PCRE.

    "Наш велосипед значительно выигрывает по массо-габаритным характеристикам у Бугатти Вейрон..."

     

  • 1.29, Аноним (-), 11:48, 12/03/2010 [ответить] [﹢﹢﹢] [ · · · ]  
  • +1 +/
    "В RE2 полностью поддерживается синтаксис регулярных выражений Perl и PCRE."
    НАГЛАЯ ЛОЖЬ!
    http://code.google.com/p/re2/wiki/Syntax
    "Grayed out expressions are not supported by RE2."
    А таких там много.
     
     
  • 2.34, Дмитрий Телегин (?), 14:25, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    >"Grayed out expressions are not supported by RE2."
    >А таких там много.

    Согласен, что не мало, но там большая часть серого от VIM. Убрав его синтаксис картина становится лучше.

     
     
  • 3.36, DeadLoco (ok), 17:22, 12/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    >>"Grayed out expressions are not supported by RE2."
    >>А таких там много.
    >
    >Согласен, что не мало, но там большая часть серого от VIM. Убрав
    >его синтаксис картина становится лучше.

    Лучше чего?

    RE2 несравнима с PCRE по функционалу. Фактически, RE2 - куцое подмножество регулярных выражений вообще. Да, в этом подмножестве она может работать оптимальнее PCRE, что не удивительно. Но RE2 - это RE2, а PCRE - это PCRE.

    Лично я уважаю PCRE за богатство функционала при конечности FSA :) и за возможность хранить прекомпилированные FSA для массового повторного использования.

     
     
  • 4.48, Дмитрий Телегин (?), 09:09, 15/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    >>Согласен, что не мало, но там большая часть серого от VIM. Убрав
    >>его синтаксис картина становится лучше.
    >
    >Лучше чего?

    Лучше чем с особенностями VIM нереализованными в ни RE2 ни в PCRE :)

     
  • 3.41, ACCA (ok), 15:41, 13/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    >>"Grayed out expressions are not supported by RE2."
    >>А таких там много.
    >
    >Согласен, что не мало, но там большая часть серого от VIM. Убрав
    >его синтаксис картина становится лучше.

    Угу. Ещё убрав синтаксис Perl и половину PCRE.

     
     
  • 4.47, Дмитрий Телегин (?), 09:02, 15/03/2010 [^] [^^] [^^^] [ответить]  
  • +/
    >>Согласен, что не мало, но там большая часть серого от VIM. Убрав
    >>его синтаксис картина становится лучше.
    >Угу. Ещё убрав синтаксис Perl и половину PCRE.

    Какой смысл здесь утрировать? Посмотрите сколько в % останется серого если убрать особенности vim. Или список даже просмотреть внимательно не удосужились?

     

     Добавить комментарий
    Имя:
    E-Mail:
    Текст:



    Спонсоры:
    Слёрм
    Inferno Solutions
    Hosting by Ihor
    Хостинг:

    Закладки на сайте
    Проследить за страницей
    Created 1996-2019 by Maxim Chirkov
    Добавить, Поддержать, Вебмастеру