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领域经常使用这种结构。
分享到:
相关推荐
直接删除s串中与t串相同的子串
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
用动态规划求最大匹配子串,算法思想以及算法实现。还有时间复杂度分析。
设s和t是给定的两个串,在主串s中找到等于子串t的过程称为模式匹配,如果在s中找到等于t的子串,则称匹配成功,函数返回t在s中的首次出现的存储位置(或序号),否则匹配失败,返回-1。t也称为模式。 简单的模式匹配...
输入两行字符串s和t(s和t可以含空格,length(t)≤length(s)≤50),将s串中首次与t匹配的子串逆置,并将处理后的s串输出。 【输入形式】 输入文件为当前目录下的invertsub.in。文件中有两行字符串s和t,...
用C 语言描述的数据结构的方法创建一个串,然后将其中某个子串T替换为另一个子串S
大整数计算器最长公共子串数据结构课设,沈阳工程学院
输入两行字符串s和t(s和t可以含空格,length(t)≤length(s)≤50),将s串中首次与t匹配的子串逆置,并将处理后的s串输出。 【输入形式】 输入文件为当前目录下的invertsub.in。 文件中有两行字符串s和t,分别以...
本文实例讲述了C语言求两个字符串的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * ...
本文探讨了Codeforces Round#452 (Div. 2) F题的两种做法。 关键词:解题报告; 数据结构; 字符串;
输入一个字符串,将输出该字符串最长对称子串及其长度,很精巧的算法
串的基本操作堆存储表示:初始化串、复制串、判断串是否为空、比较两个字符串、计算字符串长度、清空串、连接串、找子串、模式匹配、替换子串、插入和删除子串
VB 6.0 在字符串中用一子串替换另一子串,采用VB中内置的Replace函数来实现,类似这种的替换字符串方法,在平时使用十分广泛,在WEB编程的ASP/PHP/ASP.NET中,同样使用广泛。本示例中,主要是替换一个字符串中的指定...
求在由+1和-1组成的数据串中和最大的子串
用定长顺序存储结构表示串: (1) 建立两个文本文件,分别存储串str1“hellohisgoodl”和串str“hellogdygoodl” (2) 输出两个串的最长公共子串“hello”和“goodl”; (3) 分析算法时间复杂度。
2. 从侧边栏的类别目录找到「子串匹配」 3. 按照「推荐指数」从大到小进行刷题,「推荐指数」相同,则按照「难度」从易到 4. 拿到题号之后,回到本合集进行检索
删除S串中与T相同的子串~~~~~~~~
数据结构,串的操作 链式存储 逆置子串 ***题目3: 若S和T是用结点大小为1的单链表存储的两个串,设计算法将S中首次与T匹配的子串逆置。
此程序为VC6.0实现判断一个字符串是否为另一个字符串的子串