字典树中每条边都对应一个字，从根节点往下的路径构成一个个字符串。字典树并不直接在节点上存储字符串，而是将词语视作根节点到某节点之间的一条路径，并在终点节点上做个标记。要查询一个单词，指需要顺着这条路径从根节点往下走。具体可以映射为下标所示：。至于字典树的实现，相信只要认真学过数据结构的读者，都能手到擒来，这里不在赘述。因为HanLP库已经提供了多种字典树。双数组字典树是一种状态转移复杂度为常数的数据结构。所以，我们就需要使用ACDAT进行遍历。读者只需要知道其原理，什么时候用双数组遍历，什么时候用ACDAT遍历就行。
暂无评论