RE2
. Библиотека написана на C++. Существует два подхода к реализации регулярных выражений: недетерминированные
конечные автоматы
(NFS) и детерминированные конечные автоматы (DFA). Первый механизм регулярных выражений используется, например, в Perl, Tcl и .NET. К сожалению, в этом случае время работы программы может расти
экспоненциально
, а также может неограниченно расти использование стека. Такое поведение оказалось неприемлемым для таких проектов Google, как Code Search, Sawzall и Bigtable, поэтому программисты компании написали библиотеку на основе детерминированных конечных автоматов. RE2 гарантирует линейную скорость выполнения поиска и ограниченное использование стека. DFA также используется, например, в lex и egrep. В отличие от большинства подобных реализаций RE2 поддерживает почти все основные возможности PCRE. Библиотека распространяется под BSD лицензией.
Источник:Все о Google на Хабрахабре
Источник: smartZone
Другие материалы на сайте b.Z - Записки о гаджетах, людях и музыке