算法合集之《Trie图的构建、活用与改进》

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,Trie图的构建、活用与改进,山东省龙口一中,王赟,Trie树与Trie图,Trie树左是字典的一种存储方式。红色表示单词终止的位置。,Trie图右是由Trie树改造成的图。为方便起见，仅画出了平安图。,Trie图在多模式匹配中能发挥奇效。,五个模式串：,a,abc,bac,bbc,ca,主串：c b c b b c a c,匹配成功！,Trie图的构建例1,【例1】不良单词探测器,【题目描述】给出一个词典，其中的单词为不良单词。单词均为小写字母。再给出一段文本，文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如，假设rob是不良单词，那么文本problem含有不良单词。,【输入】第一行为一个整数n，表示不良单词的个数。接下来n行是词典。下面一行为一个整数m，表示文本的行数。接下来m行是文本。,【输出】如果文本包含不良单词，输出一行“Yes，否那么输出一行“No。,Trie图的构建例1,【样例输入】,1,rob,1,internetproblemsolvingcontest,【样例输出】,Yes,【备注】因此题只是用来讨论trie图的构建方法，故未给出数据范围。,Trie图的构建例1分析,判断文本是否包含不良单词可以一行一行地判断。而判断长为L的一行文本s是否含有不良单词可以这样进行：让i从1变化到L，依次判断s的前i个字符构成的字符串是否以不良单词结尾。,然而，我们希望在判断s的前k个字符时，能够利用前k-1个字符的结果，即这两个状态间可以方便地进行转移。注意到trie树中的边正如一个个“方向标，因此我们有了一个美好的设想：从根结点出发，沿着标有s1的边走一步，再沿标有s2的边走一步，一直这样走下去！,Trie图的构建例1分析,问题1：如果从当前走到的结点出发，没有需要走的边，该怎么办？,“创造一条这样的边！但我们不能同时创造一个结点，因此我们需要在已有的结点中找一个与我们想要走到的结点“等价的结点。什么叫“等价？先看这样一个问题：,定义trie树中从根结点到某个结点的路径上的边上的字符连起来形成的字符串为这个结点的路径字符串。如果一个结点的路径字符串以不良单词结尾，那么称这个结点为危险结点，否那么称之为平安结点。,问题2：如何判断某个结点是否危险？,Trie图的构建计算结点的危险性,再给出几个定义：,一个字符串去掉第一个字符后剩下的局部叫做它的后缀。,一个字符串对应的结点是指在trie图中从根出发，依次沿该字符串的每个字符走一步所到达的结点。,一个结点的路径字符串的后缀对应的结点称为它的后缀结点。,显然根结点是平安结点。,一个非根结点是危险结点的充要条件是：,它的路径字符串本身就是一个不良单词，或,它的路径字符串的后缀对应的结点是危险结点。,于是问题2转化为：如何求一个结点的后缀结点？,Trie图的构建计算后缀结点,根结点的后缀结点是它本身。,处于trie树第二层的结点的后缀结点也是根结点。,对于再往下的某个结点，设它的路径字符串的最后一个字符为c，那么这个结点的后缀为从它在trie树中父结点的后缀结点出发，沿标有c的边走一步后到达的结点。下文中称从x结点出发，沿标有字符c的边走一步到达的结点为x的c孩子,现在，问题2进一步转化为：如果它的父结点的后缀结点w没有c孩子怎么办呢？我们看到，两个问题已经合而为一了！,Trie图的构建两个问题的解决,我们假设w有这样一个c孩子记作x，并且从x出发又繁衍出无数的子子孙孙。我们来判断x的危险性。显然x本身的路径字符串不是不良单词，且它的子孙的路径字符串也不是不良单词。因此以x为根的子树中任一结点y的危险性与y的后缀结点的危险性相同回忆一下一个非根结点是危险结点的充要条件。这也就是说，以x为根的子树与以x的后缀结点为根的子树是一模一样的。因此，我们把需要新建的从w指向x的边直接指向x的后缀结点,即w的后缀结点的c孩子即可。,简言之，由于w本身的路径字符串既不是不良单词，又不是某个不良单词开头的一局部，所以它的首字母便没有用了！在这种情况下，w结点就等价于它的后缀结点。,Trie图的构建构建流程,按层次遍历trie树，同时：,求出每个结点的危险性,求出每个结点的后缀结点,补齐由它出发的边,补边的方法为：,从根结点出发的补边指向根本身；,对非根结点x，假设它没有c孩子，那么新建一条边，从x指向x的后缀结点的c孩子。,处理某个结点的过程中需要用到深度比它小的结点的后缀结点及各个孩子。由于我们按层次遍历trie树，这些信息都已求得。,Trie图的构建构建流程演示,5,0,1,9,4,2,10,7,8,6,3,a,b,c,b,c,a,c,c,b,a,图例：,安全结点,危险结点,c,b,c,a,b,a,b,a,b,a,c,a,b,c,Trie图的构建例1的解决,这样由trie树改造成的有向图就叫做trie图。图2就是由图1的trie树改造成的trie图。我们美好的设想终于变成了现实。由根结点出发，按照文本中的字符一步步走下去。假设走到一个危险结点，那么发现了一个不良单词；假设一直没走到危险结点，那么文本不含不良单词。,Trie图的构建例1的一点优化,此题的算法还可稍加优化。把平安结点分为两类：如果在trie树中由根结点到某个平安结点的路径上没有危险结点，那么称这个平安结点为真平安结点，否那么称之为假平安结点。由于新建的边的终点的深度不会大于起点的深度，因此要到达一个假平安结点，必须经过一个危险结点。而在此题中，一旦到达一个危险结点，程序就会停止，因此假平安结点是没有用的，也就是说，在此题trie图的构建过程中，假设发现一个危险结点，那么它及它的子孙的属性都不必计算了。,Trie图的构建复杂度分析,如果用L1、L2分别表示不良单词和文本的总长度，用a表示字符集中字符的个数，那么trie图的时间复杂度为O(L1a+L2)，空间复杂度为O(L1a)。,Trie图的活用,在上面的例题中，我们在trie图中记录了每个结点的危险性、后缀结点，并通过按层次遍历得到了图中结点的一个BFS序。其实，trie图中可以记录的信息不止这些；得到的BFS序也并不是毫无用处。,Trie图的活用例2,【例2】字谜题目来源：SPOJ WPUZZLES,【题目描述】给定一个L行C列的、由大写字母构成的矩阵，以及W个单词。每个单词可在矩阵中的任何位置朝着任何方向出现，且仅出现一次。编程找出每个单词的首字母在矩阵中的位置，以及单词的朝向。,【输入标准输入】第一行为一个整数T，表示数据的组数。下面有T组数据。每组数据中：,第1行为三个不超过1000的整数L、C、W。,下面L行，每行C个大写字母，表示矩阵。,下面W行，每行一个单词。,Trie图的活用例2,【输出标准输出】对每组数据，输出W行，每行为两个整数和一个字母，之间用一个空格隔开。第i行的两个整数表示第i个单词首字母的行号和列号从上至下依次为第0至L-1行，从左往右依次为第0至C-1列；字母表示单词的朝向，对应关系如下：,相邻两组数据的输出之间用一个空行隔开。,Trie图的活用例2,【样例输入】,1,4 5 4,MAIGO,QKRPT,AREMO,WERTY,AKI,MAIGO,ARM,ARMY,【样例输出】,2 0 B,0 0 C,0 1 D,0 1 D,Trie图的活用例2分析,此题中多模式匹配的模型是显而易见的。由于要求的是每个单词首字母的位置，我们在建trie图时，把每个单词都反过来，如单词MAIGO变成OGIAM。对每个方向的每一串字母进行一次多模式匹配，就可以找到所有的单词了。,在此题的trie图中，仅仅记录每个结点的危险性是不够的，还要记下每个结点的危险性是由哪个单词引起的。我们定义危险结点x的危险源：,假设x的路径字符串本身就是不良单词，那么它的危险源就是该单词；,否那么x的危险源就是它后缀结点的危险源。,每个结点的危险源可以在后缀结点的过程中求出。,Trie图的活用例2分析,MAIGO,QKRPT,AREMO,WERTY,那么，是不是每走到一个危险结点，便记下危险源的位置及朝向就可以了呢？不是的。比方在样例中，当我们沿着左上方向扫描(3,4)-(0,1)这个字符串YMRA，到达字母A时，由于该结点的危险源是YMRA，我们便记下了ARMY的位置和朝向。但同时我们就把单词ARM漏掉了。正确的做法是，当遇到一个危险结点时，记下它的危险源的位置和朝向，同时继续检查危险源对应结点的后缀结点，直到到达一个平安结点为止。,Trie图的活用例2的遗留问题,例2的字符集虽然只有26个字母，但trie图中结点的数目可能到达1,000,000，内存复杂度太高。这个问题留待第三局部trie图的改进解决。,Trie图的活用BFS序的应用,通过?字谜?一题我们学会了如何在trie图中记下更多的信息。下面简述一下对BFS序的应用。,在做多模式匹配时，有时仅仅找到不良单词是不够的，还要统计出每个单词出现的次数。进行这项工作时，我们并不需要判断每个结点的危险性，而只需累加经过每个结点的次数。但这时有单词对应的结点的访问次数并不就是这个单词出现的次数，比方在图2中，单词a出现时光标完全可能在结点ba上。因此我们自底向上地把每个结点的访问次数加到它的后缀结点上。这样处理之后，有单词对应的结点的访问次数就代表这个单词出现的次数了。,Trie图的活用,上面介绍了trie图的一些初步活用。但如果仅仅用trie图来做多模式匹配，那就太大材小用了。下面再通过几个例题来说明trie图的更灵活的应用。,从例1可以看到，危险结点在图中往往是一些障碍，在许多用到trie图的问题中，有用的结点只有真平安结点。我们把trie图中的真平安结点以及它们之间的边构成的子图叫做平安图。,Trie图的活用例3,【例3】病毒题目来源：POI#7,【题目描述】某些特定的01串是病毒的特征代码。如果一个01串不含有任何病毒特征代码，那么称它为一段平安代码。给定病毒特征库，判断是否存在无限长的平安代码。,【输入文件wir.in】第一行为一个整数n，表示病毒特征代码的条数。下面n行，每行一段病毒特征代码。所有代码长度之和不超过30000。,【输出文件wir.out】假设存在无限长的平安代码，输出一行“TAK，否那么输出一行“NIE。,Trie图的活用例3分析,【样例输入】,3,01,11,00000,【样例输出】,NIE,【分析】“无限长的平安代码是什么意思呢？就是说从根结点出发，在平安图中可以走无限步。“无限步又是什么意思呢？就是说平安图中有环。因此我们建立一个trie图并对其平安图进行拓扑排序，假设成功，那么平安图无环，输出“NIE，否那么输出“TAK。,Trie图的活用例4,【例4】Censored!题目来源：Ural 1158,【题目描述】一个由n(1=n=50)个字符组成的字符集及p(0=p=10)个不良单词长度均不超过10，求长度为m(1=m=50)且不含不良单词的字符串的数目。,【输入标准输入】第一行为三个整数n,m,p。第二行为n个字符，表示字符集。下面p行，每行一个不良单词。,【输出标准输出】一个整数，表示长度为m且不含不良单词的字符串的数目。,【样例输入】,3 3 3,QWE,QQ,WEE,Q,【样例输出】,7,Trie图的活用例4分析,求长度为m且不含不良单词的字符串的数目，就是求在平安图中从根结点出发走m步有多少种走法。用countstep,x表示从根结点出发走step步到结点x的走法数，那么容易写出右面的伪代码：,显然，此题还需要用高精度。,fillchar(count,sizeof(count),0);,count0,根:=1;,for step:=1 to m do,for 平安图中每条边(i,j)do,inc(countstep,j,countstep-1,i);,ans:=0;,for 平安图中每个结点x do,inc(ans,countm,x);,Trie图的活用小结,我们看到，tri