【计算机程序设计艺术 TAOCP】卷3·6.3 数字查找：把键码拆成字符，怎样沿前缀找到记录-北京尧图网络

把 car、cart、cat 放进同一张表前三次查找可能反复比较开头的 c 和 a。既然这些前缀相同能不能把相同部分只组织一次让后续字符决定去哪里数字查找正是从键码的组成部分出发。这里的“数字”可以是一位二进制、一组比特也可以是一个字符它不要求键码本身是十进制整数。关键变化是用当前字符或数位直接选择下一条路径。阅读定位《计算机程序设计艺术》第 3 卷《排序与查找》第 2 版苏运霖译国防工业出版社2002 年原书 §6.3书内第 458—478 页扫描 PDF 页码为书页加 13。末页与 §6.4 相接。原书包含检索树、数字查找树和 Patricia 方法本文使用自拟的稀疏字符 Trie 代码解释前缀和终止标记。1. Trie 把共有前缀变成共有路径一个朴素的字符 Trie 可以这样组织根表示空前缀。从一个节点出发标记为字符ccc的边表示在当前前缀后追加ccc。沿完整键走到的节点用额外标志表示“这里确实存有一个键”。于是 car 和 cart 共享 c、a、r 三条边cart 只额外走一条 t 边cat 在 a 之后分向 t。这种结构同时支持两个问题精确查找是否存有完整键 car前缀查找有哪些键以 ca 开头精确查找走完输入后还要检查终止标志。前缀查找走到前缀节点后则要枚举下面所有已经终止的键。两种查询共享前半段路径终点条件不同。2. “走得到”不等于“这个键存在”假设只存 cart。查询 car 可以顺利走过三条边但 car 并没有被插入。因此节点是否存在与键是否存在必须分开记录。同样地删除 car 时如果 cart 还在就不能把 r 节点以下的整段路径删掉。正确做法是先清除 car 的终止标志再从下往上删除既不表示完整键、又没有孩子的空节点。空字符串也值得单独检查。它对应根本身所以根可以有终止标志。若程序默认“每个键至少有一条边”就会把这个边界漏掉。键值映射还要处理另一种歧义值本来就允许是 None 时不能用“值是否为 None”判断键是否存在。下面的实现使用独立的 terminal 标志查无此键时抛出 KeyError已存 None 则正常返回 None。原书还讨论在叶端保存完整键、减少展开节点的方法。这种表示并不要求把每个键的所有字符都各建一个节点但最终需要比较候选的完整键。不能把某一种叶端表示中的检查步骤直接从另一种实现里删掉。3. 时间为什么与键长有关设键长为LLL每个字符选取孩子的成本为常数。普通 Trie 的精确查找读取至多LLL个字符因此是O(L)O(L)O(L)键不在表中时遇到不存在的分支可以提前结束。这个上界不需要表中的键随机分布。它也不意味着查找完全“与数据规模无关”随着数据增加键长、前缀共享、内存占用和缓存行为都可能变化。与二叉查找树相比比较次数的单位发生了变化。平衡 BST 查找是O(log⁡n)O(\log n)O(logn)次完整键比较每次比较长字符串可能读多个字符Trie 的O(L)O(L)O(L)计数通常是数位访问或分支选择。不先统一成本单位这两个表达式就无法直接比较。对于前缀PPP假设返回kkk个结果光是输出它们的记录标识就需要Ω(k)\Omega(k)Ω(k)工作若输出完整字符串还至少与总输出长度成比例。不能把一次定位到前缀节点的O(∣P∣)O(|P|)O(∣P∣)当作返回全部结果的时间。下面的 Python 版本用字典保存孩子依赖字典操作的通常均摊或期望效率。为按字符顺序枚举结果还会对子节点排序并构造路径字符串这些成本也应算入实际枚举过程。4. 多大的分支数合适若每个节点用一个长度为MMM的数组保存孩子选第ddd个孩子十分直接但每个节点都要付出MMM个槽位。很多节点只有一两个孩子时空指针占用会很明显。分支表示好处要付出的成本固定MMM路数组分支定位直接稀疏节点浪费槽位稀疏映射只保存实际存在的分支映射结构和查找有额外成本一次读取更多比特同样位长可能需要更少层分支数随每层位数指数增加压缩单孩子路径减少节点和指针跳转需要检查被压缩的标签或完整候选若每层读取rrr位那么M2rM2^rM2r。把rrr增大并不保证总时间一直下降更大的节点可能抵消更浅的层数。在独立、均匀的MMM进制数位模型中要把约nnn个键分开所需区分长度通常与log⁡Mn\log_M nlogMn同阶。这是概率模型下的尺度判断。输入若共享很长的前缀仍然需要处理这些前缀不能用这个平均估计替代最坏分析。5. 数字查找树与 Trie 不要混在一起数字查找树也称 DST可以在节点中直接存放一个完整键。查找时先比较目标与当前完整键是否相同不同才根据目标的某一位选择左、右或更一般的下一分支。这与“内部节点表示前缀、沿字符逐层前进”的 Trie 表示有差别节点中的记录可能在较浅位置就被完整比较并命中。分支根据目标数位决定不必根据它与当前节点键的大小关系决定。不能照搬二叉查找树的规则认为一次中序遍历必然得到键的大小次序。读实现时应先确认节点装的是记录、前缀、位位置还是边标签每一步比较的是完整键还是一个数位。名字相近并不保证状态含义相同。6. Patricia只保留真正分叉的位置假设一批二进制键的前二十位完全相同只有第二十一位才出现差别。普通二进制 Trie 会经过一串只有一个孩子的节点。Patricia 的重要想法是记录实际发生分歧的位位置跳过没有分支作用的部分。压缩带来一个必须补回的条件走到候选记录不代表已经检查了所有位。一个不存在的查询键可能在所有已检查的分叉位上都选择了同样的方向却在被跳过的位置不同。因此对于完整键的精确查找最后仍要核对候选完整键。长度也属于键的一部分。一个键是另一个键的前缀时需要独立的结束标记或者在比较和分支规则中显式编码长度。若直接给短键无限补零它可能与后缀全零的长键混淆。原书 Patricia 的讨论还涉及文本后缀和前缀匹配。若任务是判断“文本某个后缀是否以查询串开头”最后应该验证查询长度对应的前缀若任务是字典中的精确键查找则必须验证完整键和长度。二者的接受条件不能混用。压缩路径同样可以采用保存字符串片段的形式。插入一个在片段中间分歧的新键时需要把片段拆成共有前缀与两个分支这使插入逻辑复杂一些但能减少节点数量。7. 可运行的字符 Trie精确查找、前缀枚举与删除下面按 Python 字符串迭代得到的 Unicode 码点处理键使用字符串本身的比较顺序枚举不处理拼音排序、大小写折叠或 Unicode 规范化。这些语义应在使用索引前统一。classNode:def__init__(self):self.children{}self.terminalFalseself.valueNoneclassTrie:def__init__(self):self.rootNode()def_walk(self,key):nodeself.rootforchinkey:nodenode.children.get(ch)ifnodeisNone:returnNonereturnnodedefput(self,key,value):nodeself.rootforchinkey:ifchnotinnode.children:node.children[ch]Node()nodenode.children[ch]node.terminalTruenode.valuevaluedef__contains__(self,key):nodeself._walk(key)returnnodeisnotNoneandnode.terminaldefget(self,key):nodeself._walk(key)ifnodeisNoneornotnode.terminal:raiseKeyError(key)returnnode.valuedefremove(self,key):node,pathself.root,[]forchinkey:childnode.children.get(ch)ifchildisNone:raiseKeyError(key)path.append((node,ch))nodechildifnotnode.terminal:raiseKeyError(key)node.terminalFalsenode.valueNoneforparent,chinreversed(path):childparent.children[ch]ifchild.terminalorchild.children:breakdelparent.children[ch]defwith_prefix(self,prefix):startself._walk(prefix)ifstartisNone:returnstack[(prefix,start)]whilestack:key,nodestack.pop()ifnode.terminal:yieldkey,node.valueforchinsorted(node.children,reverseTrue):stack.append((keych,node.children[ch]))trieTrie()forkey,valuein[(cart,4),(car,None),(cat,3),(dog,5),(,0)]:trie.put(key,value)print(list(trie.with_prefix(ca)))trie.remove(car)print(carintrie,cartintrie,trie.get())print(list(trie.with_prefix(car)))输出[(car, None), (cart, 4), (cat, 3)] False True 0 [(cart, 4)]删除 car 后cart 仍然存在说明删除的是键的终止状态而非粗暴删除整条前缀路径。空字符串存于根节点值为 None 的键也能与不存在区分。进一步验证时可以用普通字典做参照随机执行插入、覆盖和删除每次前缀查询都同“扫描字典并筛选 startswith 的键再排序”的结果比较。还应检查一条长链、所有键共享前缀、空前缀返回全表以及删除不存在键时结构不变。8. 选结构之前先确定键的表示数字查找利用了键的内部结构因而特别依赖编码规则。按字节还是按字符分支、怎样区分短键与长键、是否规范化大小写都会改变“同一个键”的定义。Trie 适合把精确查找和前缀枚举放在一起考虑压缩结构解决单分支路径带来的空间浪费DST 和 Patricia 又在节点内容、位选择和最后确认方式上作了不同取舍。下一篇 §6.4 将不再沿键码前缀逐层分支而是先算出一个表地址。地址计算很快接下来的问题是多个键算到同一个地方时怎么办以及删除后怎样保证后面的键仍然找得到。

【计算机程序设计艺术 TAOCP】卷3·6.3 数字查找：把键码拆成字符，怎样沿前缀找到记录

相关推荐

Agent 记忆系统设计：上下文窗口装不下的长期项目，什么该记住、什么该忘掉

AI生成PPT工具的几种使用路径与体验记录

别让错题本变成抄题本：我给孩子用的 AI 错题本开源了

更多资讯

Kubernetes Pod Not Found报错排查：命名空间、上下文与标签选择器实战

PostgreSQL主从流复制与pgpool-II高可用部署实战

Java数据结构与算法分析：递归、复杂度与链表指针精解

高效调试方法论：从基础工具到AI辅助的BUG终结术

Linux标准IO库：原理、优化与实战应用

跨平台扫码功能实现方案与技术解析

今日更新

Agent-Reach：打通大模型触达外部系统的最后一公里

深度学习图像隐写分析实战：从CNN原理到毕设源码全解析

AI赋能知识产权供需匹配：专利评估、需求挖掘与多路召回工程实践

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？