Trie树查询
基于三数组Trie索引树原理的汉语词典查询机制,并用递归算法实现构词状态表的自动构建.
Trie树是搜索树的一种，来自英文单词"Retrieval"的简写，可以建立有效的数据检索组织结构，是中文匹配分词算法中词典的一种常见实现。它本质上是一个确定的有限状态自动机(DFA)，每个节点代表自动机的一个状态。在词典中这此状态包括"词前缀"，"已成词"等。Trie树就是字典树，其核心思想就是空间换时间.字典树有如下简单的性质：
(1) 根节点不包含字符信息;
(2) 一棵m度的Trie或者为空，或者由m棵m度的Trie组成。
搜索字典项目的方法为：
(1) 从根结点开始一次搜索;
(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树，转到该子树继续进行检索;
(3) 在相应的子树上，取得要查找关键词的第二个字母，并进一步选择对应的子树进行检索。
(4) 迭代过程……
(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。
双数组Trie(Double-Array Trie)是trie树的一个简单而有效的实现，由两个整数数组构成，一个是base[]，另一个是check[]。设数组下标为i ,如果base,check均为0,表示该位置为空。如果base为负值，表示该状态为词语。Check表示该状态的前一状态，t=base+a, check[t]=i 。
感谢您访问：生涯设计公益网！本文永久链接：https://www.16175.com/111070.html。侵删或不良信息举报请联系邮箱：121488412@qq.com或微信：aban618。