相同前缀共用路径

在普通字典树中,一层处理键的下一个字符或选定单位。具有相同开头的键沿同一段路径前进,直到不同的位置才分支。节点上的结束标记或关联值,区分“某个键恰好到这里结束”与“这里只是其他长键的前缀”。

这一区分很重要:若已经存放某个长词,不能因为走到其中一半,就把尚未单独加入的短词也当成已存在的键。查找需要同时核对路径是否存在,以及对应结束位置是否承载有效条目。

参考:[1] [2]

精确命中与前缀查询分开

前缀枚举先走到给定前缀的位置,再收集它下面的有效键;最长前缀查询则沿输入继续前进,保留最近一次遇到的有效结束位置。二者回答的问题不同,也都不同于“输入是否就是一个完整已存键”。

例如路由前缀或自动补全可以利用这些关系,但最终含义仍由应用规定。字典树按输入单位匹配,不会自动判断两个名字是否指同一对象,也不会凭相似开头为不同词语补出语义关系。

参考:[1] [2]

字符范围与分支存储影响成本

用每个字符一个分支的直接表示,查找工作通常与键长有关;Princeton的256路示例便为核心操作给出与键长度成比例的界。若要枚举大量结果,还必须计算输出本身的数量与长度,不能只看走到前缀位置花了多少步。

每个节点分配整个字符表的子链接数组,可能给稀疏分支带来空间开销。三向搜索字典树等表示选择不同的分支结构。实现还须先明确键按字节、字符或其他单位处理,以及大小写、规范化与字符范围的接口规则。

参考:[1] [2]