Блог им. 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 на Хабрахабре
Похожие новости
- Распознаем STL-код легко: std::vector
- Есть ли жизнь после Cisco ISE? Распаковка и тест-драйв российского NAC от Eltex в сетевой лаборатории
- ИИ взломали. Кто бы мог подумать?
- DPI, ТСПУ и операторы: архитектура блокировки трафика в России
- Максим Котенков: Мы сделали своё API для семантического анализа — и это убрало 70% рутины при подготовке SEO-ТЗ
- Почему автотесты пропускают изменения в API и как это исправить с Pydantic
- Что сегодня действительно важно в AI: 10 направлений по версии MIT Technology Review
- АЙNET: АЙNET: 30% крупных брендов отказываются от лендингов в пользу чековых ботов, а интерес к промо в Max вырос на 40%
- Как мы написали свой forward-proxy на Go и отказались от VPN для доступа к админкам
- i-Media: 43% потребителей идут на маркетплейсы за эмоциональной подзарядкой, а нейросети вытесняют поисковики: i-Media выпускает обзор digital-рынка за Q1 2026