我爱正则表达式

关于 Trie 的介绍，请读上文Trie，此不赘述。本文主要分析 Trie 实现原理，并给出 Python 的实现。

构造检索树

先正更上文不精确之处。上文说，

具体说来，就是提取出备选项文本的公共部分，构造“检索树”…

其实 Trie 并不是提取所有的“公共部分”，而是只提取“前缀”而已。例如，对于正则式/abbcc|abcc/，它生成的结果是(?-xism:ab(?:bcc|cc))，而非abb?cc，可见它并没有智能到足够程度，可应用之而不可迷信之。具体原因，可以通过读源码以及本文分析而理解。

新建一个 Trie 对象之后，每向它添加一个字串，它都做如下操作：

• 整体的数据结构是 Hash 表，亦即Python中的Dictionary。
• Hash表的每一个元素指向它自身；以所输入的子串的每个字母为Key，如果它自身为空，则指向一个新建的匿名Hash；
• 最后一个元素的Key为空字串‘’，value为1。这也是判断每个分支是否结束的标志。

请看一下对于字串 foobar分析后所生成的数据结构：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

{ 'f' => {          'o' => {                   'o' => {                            'b' => {                                     'a' => {                                              'r' => {                                                       '' => 1                                                     }                                            }                                   }                          }                 }        } }

很美观，对不对。奇妙的是，对于第一条字串，它生成的结构是这样的；对于新插入的第二条，第三条……第N条字串，它不是另起炉炉灶，而是萧规曹随，见缝插针，充分利用前面已经成生的数据结构。这要归功于Hash/Dictionary这种数据结构的特点。看一下针对于foobar foobah fooxar foozap fooza 完全插入后的效果：

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

'f' => {            'o' => {                     'o' => {                              'b' => {                                       'a' => {                                                'h' => {                                                         '' => 1                                                       },                                                'r' => {                                                         '' => 1                                                       }                                              }                                     },                              'x' => {                                       'a' => {                                                'r' => {                                                         '' => 1                                                       }                                              }                                     },                              'z' => {                                       'a' => {                                                '' => 1,                                                'p' => {                                                         '' => 1                                                       }                                              }                                     }                            }                   }          } }

这个结构图很直观地解释了为什么是提取前缀而非后缀中缀什么的。

构造一个检索树，已经不是一个问题。现在来看看如何将它转换为正则表达式。

检索树的正则表现

原文源码比较精炼，用了许多Perl特有的语法且无注释。我简要解释一下作者思路。

• 如果当前节点的 key 为空，且当前只有一个键，则该分支结束，返回空值。这也是前文伏笔的照应：为什么要加上$ref->{''}=1;。
• 对于不为空的节点，一一分析之。

• 只要当前节点不为空，一直递归调用本函数，将当前key+下个节点的递归结果push到数组@alt中备用。
• 否则只将 key push到 @cc中。

• @cc是用来保存单个字母的，而@alt则是用来保存多个字母的备选项的。
• 将@cc中的元素格式化为[abc]的样子。当然，如果只有一个元素就不必了。
• 将@alt中的元素格式化为(?:abc|xyz)的样子，一个元素则免。
• 在适当的地方添加问号，表示备选。

读懂了源码，自己实现起来就不是问题了。我在读此代码时，使用了纸笔抄写、观测print、Data::Dumper输出等方式来辅助理解。事实证明卓有成效。

移植到Python

从Perl到Python，其实就像从英语到法语的转换一样，只是将拼写方式，细微语法修整一下即可，算不得伤筋动骨的大手术。我是用它来验证理解、熟悉语法细节的。代码如下。只要from trie import Trie就能使用了。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

#!/usr/bin/python # -*- coding: utf-8 -*- # #author:         rex #blog:           http://iregex.org #filename        tr.py #created:        2010-08-01 20:24 class Trie():     """Regexp::Trie in python"""     def __init__(self):         self.data={}     def add(self, word):         ref=self.data         for char in word:             ref[char]=ref.has_key(char) and ref[char] or {}             ref=ref[char]         ref['']=1     def dump(self):         return self.data     def _regexp(self, pData):         data=pData         if data.has_key("") and len(data.keys())==1:             return None         alt=[]         cc=[]         q=0         for char in sorted(data.keys()):             if isinstance(data[char],dict):                 try:                     recurse=self._regexp(data[char])                     alt.append(char+recurse)                 except:                     cc.append(char)             else:                 q=1         cconly=len(alt) and 0 or 1  #if len, 0; else:0         if len(cc)>0:             if len(cc)==1:                 alt.append(cc[0])             else:                 alt.append('['+''.join(cc)+']')         if len(alt)==1:             result=alt[0]         else:             result="(?:"+"|".join(alt)+")"         if q:             if cconly:                 result+="?"             else:                 result="(?:%s)?" % result         return result     def regexp(self):         return "(?-xism:%s)" % self._regexp(self.dump()) a=Trie() for w in ['foobar', 'foobah', 'fooxar', 'foozap', 'fooza']:     a.add(w) print a.regexp()

Ubuntu 10.04, Python 2.6.5 环境下测试通过。