【转】PAT Tree 子串匹配结构

http://hxraid.iteye.com/blog/615295

 

Patricia Tree  简称PAT tree。 它是 trie 结构的一种特殊形式。是目前信息检索领域应用十分成功的索引方
法，它是1992年由Connel根据《PATRICIA——Patrical Algorithm to Retrieve Information Coded in Alphanumeric》算法发展起来的。

 

PAT tree 在字符串子串匹配 上有这非常优异的表现，这使得它经常成为一种高效的全文检索算法，在自然语言处理领域也有广泛的应用。其算法中最突出的特点就是采用半无限长字串(semi-infinite string 简称 sistring) 作为字符串的查找结构。

 

采用半无限长字串(sistring): 一种特殊的子串信息存储方式。

比如一个字符串CUHK。它的子串有C、CU、CUH、CUHK、U、UH、UHK、H、HK、K十种。如果有n个字符的串，就会有n(n+1)/2种子串，其中最长的子串长度为n。因此我们不得不开辟 n(n+1)/2个长度为n的数组来存储它们，那么存储的空间复杂度将达到惊人的O(n^3)级别。

 

但是我们发现这样一个特点：

            CUHK ——  完全可以表示 C、CU、CUH、CUHK

            UHK   ——  完全可以表示 U、UH、UHK

            HK     ——  完全可以表示 H、HK、

            K       ——  完全可以表示 K

这样我们就得到了4个sistring: CUHK、UHK、HK和K。

 

PAT tree的存储结构

如果直接用单个字符作为存储结点，势必构造出一棵多叉树(如果是中文字符的话，那就完蛋了)。检索起来将会相当不便。事实上，PAT tree是一棵压缩存储的二叉树结构。现在我们用“CUHK”来构造出这样一棵PAT tree 。

 

开始先介绍一下PAT tree的结点结构(看了后面的过程就再来理解这些概念)

* 内部结点：用椭圆形表示，用来存储不同的bit位在整个完整bit sequence中的位置。

* 外部节点(叶子结点)： 用方形表示，用来记录sistring的首字符在完整sistring中的开始位置(字符索引)和sistring出现的频次。

* 左指针：如果 待存储的sistring在 内部结点所存储的bit位置上的数据 是0，则将这个sistring存储在该结点的左子树中。

* 右指针：若数据是1，则存储在右子树中。

 

(1) 将所有sistring的字符转化成1 bytes的ASCII码值，用二进制位来表示。形成一个bit sequence pattern(没有的空字符我们用0来填充)。

                         sistring                           bit sequence

 完整sistring  ->   CUHK        010 00011   01010101   01001000   01001011   <- 完整bit sequence

                          UHK0        010 10101   01001000   01001011   00000000                          

                          HK00         01001000   01001011   00000000   00000000

                          K000         01001011   00000000   00000000   00000000

 

(2) 从第一个bit开始我们发现所有sistring的前3个bit位都相同010，那么相同的这些0/1串对于匹配来说就毫无意义了，因此我们接下来发现第4个bit开始有所不同了。UHK 的第4个bit是1，而CUHK、HK、K的第4个bit是0。则先构造一个内部结点iNode.bitSize=4（第4个bit），然后将UHK的字符索引 cIndex=2(UHK的开始字符U在完整的CUHK的第2位置上)构造成叶子结点插入到iNode的左孩子上，而CUHK、HK、K放在iNode右子树中。(如下图2)

 

(3) 递归执行第2步，将CUHK、HK、K进一步插入到PAT tree中。流程如下图所示。所有sistring都插入以后结束。

注意：既然PAT tree 是二叉查找树，那么一定要满足二叉查找树的特点。所以，内部结点中的bit 位就需要满足，左孩子的bit 位< 结点bit 位< 右孩子的bit 位。

 

PAT tree的检索过程

 

利用PAT tree可以实现对语料的快速检索，检索过程就是根据查询字串在PAT tree中从根结点寻找路径的过程。当比较完查询字串所有位置后，搜索路径达到PAT tree的某一结点。

 

      若该结点为叶子结点，则判断查询字串是否为叶子结点所指的半无限长字串的前缀，如果判断为真，则查询字串在语料中出现的频次即为叶子结点中记录的频次；否则，该查询字串在语料中不存在。

 

      若该结点为内部结点，则判断查询字串是否为该结点所辖子树中任一叶子结点所指的半无限长字串的前缀。如果判断为真，该子树中所有叶子结点记录的频次之和即为查询字串的出现频次。否则，查询字串在语料中不存在。

 

      这样，通过PAT tree可以检索原文中任意长度的字串及其出现频次，所以，PAT tree也是可变长统计语言模型优良的检索结构。

 

 

例如：要查找string= “CU ”(bit sequence=010 00 0 1 1 01010101) 是不是在CUHK 中。

(1)   根据“CUHK ”的PAT tree 结构( 如上图) ，根结点r 的bit position=4 ，那么查找bit sequence 的第4 个bit=0 。然后查找R 的左孩子rc 。

(2)    rc 的bit position=5 ，在bit sequence 的第5 个bit=0 。则查找rc 的左孩子rcc 。

(3)   rcc= ” CUHK ” 已经是叶子结点了，则确定一下CU 是不是CUHK 的前缀即可。

 

 

PAT tree 的效率

 

      特点：PAT tree查找的时间复杂度和树的深度有关，由于树的构造取决于不同bit位上0,1的分布。因此PAT tree有点像二叉查找树 ，最坏情况下是单支树(如上图例子)，此时的时间复杂度是O(n-1)，n为字符串的长度。最好情况下是平衡二叉树 结构，时间复杂度是O(log2(N))。另外，作为压缩的二叉查找树，其存储的空间代价大大减少了。

 

 

 

PAT tree的实际应用

 

       PAT tree在子串匹配上有很好的效率，这一点和Suffix Tree(后缀树)，KMP算法的优点相同。因此PAT tree在信息检索和自然语言处理领域是非常常用的工具。比如：关键字提取，新词发现等NLP领域经常使用这种结构。