Блог им. kureimoru / RE2 — новая библиотека регулярных выражений
Вчера Google выпустил новую библиотеку регулярных выражений —
RE2
. Библиотека написана на C++. Существует два подхода к реализации регулярных выражений: недетерминированные
конечные автоматы
(NFS) и детерминированные конечные автоматы (DFA). Первый механизм регулярных выражений используется, например, в Perl, Tcl и .NET. К сожалению, в этом случае время работы программы может расти
экспоненциально
, а также может неограниченно расти использование стека. Такое поведение оказалось неприемлемым для таких проектов Google, как Code Search, Sawzall и Bigtable, поэтому программисты компании написали библиотеку на основе детерминированных конечных автоматов. RE2 гарантирует линейную скорость выполнения поиска и ограниченное использование стека. DFA также используется, например, в lex и egrep. В отличие от большинства подобных реализаций RE2 поддерживает почти все основные возможности PCRE. Библиотека распространяется под BSD лицензией.
Источник:Все о Google на Хабрахабре
RE2
. Библиотека написана на C++. Существует два подхода к реализации регулярных выражений: недетерминированные
конечные автоматы
(NFS) и детерминированные конечные автоматы (DFA). Первый механизм регулярных выражений используется, например, в Perl, Tcl и .NET. К сожалению, в этом случае время работы программы может расти
экспоненциально
, а также может неограниченно расти использование стека. Такое поведение оказалось неприемлемым для таких проектов Google, как Code Search, Sawzall и Bigtable, поэтому программисты компании написали библиотеку на основе детерминированных конечных автоматов. RE2 гарантирует линейную скорость выполнения поиска и ограниченное использование стека. DFA также используется, например, в lex и egrep. В отличие от большинства подобных реализаций RE2 поддерживает почти все основные возможности PCRE. Библиотека распространяется под BSD лицензией.
Источник:Все о Google на Хабрахабре
💬 Комментарии
В связи с новыми требованиями законодательства РФ (ФЗ-152, ФЗ «О рекламе») и ужесточением контроля со стороны РКН, мы отключили систему комментариев на сайте.
🔒 Важно Теперь мы не собираем и не храним ваши персональные данные — даже если очень захотим.
💡 Хотите обсудить материал?
Присоединяйтесь к нашему Telegram-каналу:
https://t.me/blogssmartzНажмите кнопку ниже — и вы сразу попадёте в чат с комментариями