《基于三叉搜索树的网页》由会员分享，可在线阅读，更多相关《基于三叉搜索树的网页（13页珍藏版）》请在金锄头文库上搜索。
1、 基于三叉搜索树的网页AUTOCOMPLETE 的实现 无线通信原理项目报告 2016-5-15 目录 1.1. 简述简述 . 1 2.2. 各种实现方法复杂度的比较各种实现方法复杂度的比较 . 1 3.3. TrieTrie 树树 . 2 3.13.1 TrieTrie 树的定义树的定义 . 2 3.23.2 TrieTrie 树的实现树的实现 . 3 4.4. 三叉搜索树三叉搜索树 . 4 5.5. 具体解决的问题具体解决的问题 . 8 5.15.1 减少内存占用减少内存占用 . 错误错误! ! 未定义书签。未定义书签。7 5.25.2 重名问题重名问题 . 8 5.35.3 用户输入可能
2、存在各种错误。用户输入可能存在各种错误。 . 10 5.4 对于对于 middlemiddle namename 的处理的处理。 . 11 6.6. 性能评估比较性能评估比较 . 11 1.1. 简述简述 我们实现了搜索框自动匹配功能， 当用户开始输入想要搜索的关键词时， 我们会根据当前输入的字符，我们会预测用户想要搜索的完整的关键字，并显示在下拉框中。为了减小时间复杂度和空间复杂度，我们采用了三叉搜索树(TST)来实现此功能。相比于其他方式(如redis，Trie 等)，TST 占用内存明显更小，搜索速度上也有一定优势。在具体实现方法上，我们采用 Java 编写 TST 主程序，并使用 To
3、mcat 实现前端与后端交互。 2.2. 各种实现方法复杂度的比较各种实现方法复杂度的比较 我们在选择几种不同的数据方法在缓存中存储数据的时候， 考虑了他们的时间复杂度。 具体见下表。 通过对比可以发现，TST 在时间复杂度上的优势。但是单词字母的插入顺序会很大程度上影响树的高度，而树的高度又与它的性能息息相关。 时间复杂度：时间复杂度： 设树的高度为 h，查找字符串的时间复杂度：o(logh)；插入字符串的时间复杂度：o(logh) 缺点缺点 匹配效率依赖于树的高度，可以在建 TST 之前，可采取相应措施，使得 tst 为平衡树，提高匹配的时间效率。具体方法后文会介绍。 3.3. TrieT
4、rie 树树 Trie 树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构，如英文字母的字典树是一个 26 叉树，数字的字典树是一个 10 叉树。 3.13.1 TrieTrie 树的定义树的定义 Trie 树与二叉搜索树不同， 键不是直接保存在节点中， 而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀（prefix） ，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。 Trie 树可以利用字符串的公共前缀来节约存储空间，如下图所示，该 Trie 树用 11 个节点保存了
5、8 个字符串 tea，ted，ten，to，A，i，in，inn。 图图 1Trie1Trie 树树 我们注意到 Trie 树中，字符串 tea，ted 和 ten 的相同的前缀（prefix）为“te”，如果我们要存储的字符串大部分都具有相同的前缀 （prefix） ， 那么该 Trie 树结构可以节省大量内存空间，因为 Trie 树中每个单词都是通过 character by character 方法进行存储，所以具有相同前缀单词是共享前缀节点的。 当然，如果 Trie 树中存在大量字符串，并且这些字符串基本上没有公共前缀，那么相应的 Trie 树将非常消耗内存空间，Trie 的缺点是空指
6、针耗费内存空间。 Trie 树的基本性质可以归纳为： （1）根节点不包含字符，除根节点外的每个节点只包含一个字符。 （2）从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。 （3）每个节点的所有子节点包含的字符串不相同。 3.23.2 TrieTrie 树的实现树的实现 Trie树是一种形似树的数据结构，它的每个节点都包含一个指针数组，假设，我们要构建一个26个字母的Trie树，那么每一个指针对应着字母表里的一个字母。从根节点开始，我们只要依次找到目标单词里下一个字母对应的指针，就可以一步步查找目标了。假设，我们要把字符串AB，ABBA，ABCD和BCD插入到Trie树中，
7、由于Trie树的根节点不保存任何字母，我们从根节点的直接后继开始保存字母。 如下图所示， 我们在Trie树的第二层中保存了字母A和B，第三层中保存了B和C，其中B被标记为深蓝色表示单词AB已经插入完成。 图图2 Trie2 Trie树的实现树的实现 我们发现由于Trie的每个节点都有一个长度为26指针数组， 但我们知道并不是每个指针数组都保存记录，空的指针数组导致内存空间的浪费。 假设，我们要设计一个翻译软件，翻译软件少不了查词功能，而且当用户输入要查询的词汇时，软件会提示相似单词，让用户选择要查询的词汇，这样用户就无需输入完整词汇就能进行查询，而且用户体验更好。 我们将使用 Trie 树结构
8、存储和检索单词，从而实现词汇的智能提示功能，这里我们只考虑 26 英文字母匹配的实现，所以我们将构建一棵 26 叉树。 由于我们最终采用的是三叉搜索树，关于由于我们最终采用的是三叉搜索树，关于 TrieTrie 树的具体实现这里不再赘述。树的具体实现这里不再赘述。 4.4. 三叉搜索树三叉搜索树 三叉搜索树是一种特殊的 Trie 树的数据结构， 它是数字搜索树和二叉搜索树的混合体。它既有数字搜索树效率优点， 又有二叉搜索树空间优点。 三叉搜索树使用了一种聪明的手段去解决 Trie 的内存问题（空的指针数组） 。为了避免多余的指针占用内存，每个 Trie 节点不再用数组来表示，而是表示成“树中有
9、树”。Trie 节点里每个非空指针都会在三叉搜索树里得到属于它自己的节点。 接下来，我们将实现三叉搜索树的节点类，具体实现如下： 图三图三 三叉搜索书的结点类三叉搜索书的结点类 由于三叉搜索树包含三种类型的箭头。第一种箭头和 Trie 里的箭头是一样的，也就是图 2 里画成虚线的向下的箭头。 沿着向下箭头行进， 就意味着“匹配上”了箭头起始端的字符。如果当前字符少于节点中的字符，会沿着节点向左查找，反之向右查找 接下来，我们将定义 Ternary Tree 类型，并且添加 Insert()和 Find()函数 图四图四 三叉搜索树的三叉搜索树的 insertinsert 函数函数 图五图五 三
10、叉搜索树的三叉搜索树的 findfind 函数函数 由于三叉搜索树每个节点只有三个叉， 所以我们在进行节点插入操作时， 只需判断插入的字符与当前节点的关系（少于，等于或大于）插入到相应的节点就 OK 了。 我们使用之前的例子，把字符串AB，ABBA，ABCD和BCD插入到三叉搜索树中，首先往树中插入了字符串AB，接着我们插入字符串ABCD，由于ABCD与AB有相同的前缀AB，所以C节点都是存储到B的CenterChild中，D存储到C的CenterChild中；当插入ABBA时，由于ABBA与AB有相同的前缀AB，而B字符少于字符C，所以B存储到C的LeftChild中；当插入BCD时，由于字
11、符B大于字符A，所以B存储到C的RightChild中。 图图六六 三叉搜索树三叉搜索树 我们注意到插入字符串的顺序会影响三叉搜索树的结构， 为了取得最佳性能， 字符串应该以随机的顺序插入到三叉树搜索树中， 尤其不应该按字母顺序插入， 否则对应于单个Trie节点的子树会退化成链表， 极大地增加查找成本。 当然我们还可以采用一些方法来实现自平衡的三叉树。 由于树是否平衡取决于单词的读入顺序， 如果按排序后的顺序插入， 则该方式生成的树是最不平衡的。 单词的读入顺序对于创建平衡的三叉搜索树很重要， 所以我们通过选择一个排序后数据集合的中间值，并把它作为开始节点，通过不断折半插入中间值，我们就可以创
12、建一棵平衡的三叉树。 5.5. 具体具体解决解决的的问题问题 5.15.1 不同不同类型类型数据的处理数据的处理 导入的数据库包括有 affiliations、authors、conference、field、journal 共 5 类数据，因此我们建立了 5 个的 TST，分别插入这 5 类数据。在搜索时，分别在 5 个 TST 内搜索。其中 authors 库比较大，大约有 73 万个作者，其他库共计约 3 万条数据，整体上数据量在 75 万左右。 5.25.2 重名重名问题问题 数据库中作者存在很多同名。为了解决重名问题，在建树时，我们在作者姓名后面加上作者 ID，使用 ID 区分同名作者。比如，数据库中存在多个作者姓名为“tao wang” ，在插入建树时，我们插入“tao wang: 80F5E6B7” 、 “tao wang：7DAE408A” 、“tao wang：7F9D979B”。当用户输入“tao wa”时，将查找出所有姓名为“tao wang”的作者，并以 ID 加以区分，查找结果如下: “authors“authors“: “AuthorID“AuthorID“:“80F5E6B7“80F5E6B7“, “AuthorName“AuthorName“:“tao wang
