介绍一个regular expression engine: RE2

RE2(http://code.google.com/p/re2/)是一个高速、安全、线程友好的正则表达式引擎。和常用的 PCRE, Perl, Python 中的正则表达式引擎类似。RE2 是一个 C++ 库。

我在2011年年初把RE2引入工作中,现在已经在很多项目中使用了。这一年的时间里,常有同事问为什么我们用 RE2,而不是其他正则表达式引擎?

我们是可以用其他引擎。用 RE2 的原因是各种主流正则表达式引擎(包扩Perl、Python 和 PCRE)一度都没有用真的自动机(real automata)。更详细的情况请参照http://swtch.com/~rsc/regexp/regexp1.html。

这个调查结果是 Russ Cox 做出的,也是他动手写 RE2 的原因。Russ Cox 是 Google Go 语言的设计者之一,也是 Go 语言的官方编译器的作者。(Go语言目前有两个编译器,官方编译器 http://golang.org 是基于 Plan9 操作系统上的代码写的;另一个是 GCC Go,随GCC 4.6以及更高版本发布,作者是 Ian Lance Taylor。)

Russ Cox 2006年在 Google 实习的时候,在他的实习生导师 Jeff Dean(美国科学院院士,MapReduce 和 Bigtable 的发明者)的鼓励下,开发了 Google Code Search。这是 Google 的各种垂直搜索引擎中唯一一个容许 query 为正则表达式的引擎。Code Search 的前身是 Google 里一个叫 gsearch 的工具。这个工具包括一个命令行工具和一组服务。这些服务把 Google 所有的代码分块后装入内存。查询的时候,它们并行的执行 query(用类似 grep 的方式),然后返回结果。

Google Code 的基本架构和 gsearch 一样;不同的是,代码不是以文本形式存储的,而是有索引结构的(trigram index)。这个结构巧妙的复用了 Google Web Search Engine 里的索引系统,但是支持正则表达式匹配。具体的介绍可以参见 Russ Cox 的这篇文章:http://swtch.com/~rsc/regexp/regexp4.html。

在这篇文章里, Russ Cox 介绍了他为了做 Google Code Search 专门调研了一下各种正则表达式的实现。结果发现大部分都不是用 real automata 实现的。换句话说,时间复杂度没有保证。他为此请教了 Rob Pike。Rob Pike 是 Ken Thompson 的同事,也是C语言的发明者之一。Ken Thompson 最早在ed中实现了正则表达式,并且导致了grep的诞生。Rob Pike 在2006年已经加入 Google了。他当时很惊讶,也因此鼓励 Russ Cox 用几十年前已经证明高效的算法,开发了 RE2。

我之前大概知道 RE2 的来历,但是没有上述文章里说的细致。这篇文章是 Russ Cox 最近发表的。恰好从一个方面解释了 RE2 的来历。不确定从 2006 年之后,其他各种正则表达式的引擎有没有什么变化。有兴趣的同学可以琢磨一下。

About these ads

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 28 other followers

%d bloggers like this: