trie - zhouyichi

复习感想——数据结构篇其四_trie及其变形//从一次失败的尝试谈起

Trie树是用来处理多个字符串的数据结构。

Trie树的初始动机很简单，利用字符串间的公共前缀来节约字符串存储的空间及加快检索的速度。

    例如：单词 computer和command在trie树中只需要存储  com  和  puter及mand三个部分

Trie树中从根节点出发到树上任意节点的路径都可以代表一个单词。

Trie树很直观，其插入删除查找操作也很简单，这里不再赘述。

下面着重看一个问题，我曾经对这个问题做过一个很失败的尝试，但是通过对trie的改进版能得到这个问题的很漂亮的解。

例一：病毒

二进制病毒审查委员会最近发现了如下规律：某些确定的二进制串是病毒的代码。如果某段代码中不存在任何一段病毒代码，那么我们就称这段代码是安全的。现在委员会已经找出了所有的病毒代码段，试问，是否存在一个无限长的安全的二进制代码。

例如：如果{011，11，000000}是病毒代码集，那么0101010101。。。就是一个无限长安全代码。如果{01，11，000000}是病毒代码集，则不存在无限长安全代码。

分析：对于这个问题，我最开始的想法很简单（事实证明也很天真）

1．  设L是病毒集中最长的代码的长度。那么，容易证明，如果存在2L-1的长度的安全代码，那么，一定存在无限长安全代码。

2．  对2L-1的长度的所有代码都进行一次kmp。。。

我相信，这是一个很正常的“最初想法”，不难发现这个方法很慢，指数级的复杂度。。。

用类似于trie树的递归实现可以稍微快一点，但是依旧是指数级的复杂度。ToT

分析一下这个方法为什么这么慢。

1．  对于任意的病毒字符串来说（设其长度为l），那么对于这个字符串来说，要找出它的匹配，我们所关心的字符长度其实是  l  而不是2L-1。

2．  做了大量的无用功，以病毒字符集{011，01，000000}为例。

在程序过程中，如果发现011代码串是不安全的，那么，以这个为依据，我们可以直接论断0011，1011，00011。。。。。等等代码串都是不安全的，但是在那个失败的尝试中，对于这些代码串都进行了匹配。

这两个问题有种似曾相识的感觉。。。。。。确实曾经见过类似的动机（特别是第二个），同为字符串匹配算法的KMP算法的初始动机就很类似。KMP在解决一维字符串匹配问题的时候利用了自动机的思想，在这里也能用到！（而且这里用到的自动机我觉得在直观上更像自动机，毕竟我第一次接触自动机是在”数字逻辑电路”这门课上，当时的名字貌似叫状态机什么的。。。。）

接下来以病毒代码集为{011，11，000000}的情况为例说一下用trie的变形的具体作法，以及分析一下其中每一步的动机：

1．  把病毒代码集建成一颗trie树。动机：每一个具体的病毒所关心的代码长度为它本身的长度，如图：

其中黑色节点所代表的是病毒代码。

2．  在此图中添加一些边：完整地作出添加边后的图很麻烦，下图中仅仅是考虑了01字符串后添加的边。

什么叫考虑  01字符串后添加的边呢？？

任何一个   以01开头的字符串a，在判定a中是否存在病毒代码的目的下，等价于判断把a中的第一个字符：0去掉以后得到的字符串b 中是否有病毒代码。

同样的道理，以001开头的字符串等价于该字符串去掉前缀  00后的字符串

以101开头的字符串等价于以该字符串去掉前缀  1后得到的字符串。

3．  如果理解了这个建图的道理，那么，很容易发现，如果存在一个无限长字符串  a，它能一直在图中的白颜色节点中“走”，那么，对于该病毒集存在一个无限长完全代码，从而可以把这个问题转换为判断是否在白色节点中存在回路的问题（因为白色节点个数是有限的），那么仅需要对白色的节点进行一次dfs即可，成功地把复杂度降到了线性

4．  至此，此问题已经圆满解决。

总结：trie还有一些其他的变形。。以后再复习