有路径与存储单词是两回事
定义 7.1.1
(Trie、终止标记与标准形式)
Trie 在大小为 的有序有限字母表上存储有限字符串集合。根代表空前缀;每条边标记一个字符,从根到节点的路径拼出其前缀。节点可以标记为终止,表示对应字符串本身在集合中。没有终止标记的非根路径表示某个已存储字符串的前缀,而非已存储单词。根是例外:即使集合为空,它仍存在。
当 trie 的非根节点恰好是集合 中字符串的非空前缀(因此每个非根节点都是至少一个已存储字符串的前缀),并且节点为终止当且仅当其字符串属于 时,称这个 trie 对 是标准的。
下述插入及剪枝维持标准形式。本课讨论集合而非多重集合:重复插入不增加次数。若允许空字符串,它以根的终止标记表示。
概念视角组合
按共用前缀计算节点数
把已存储的字符串按字典序排成 ,并令 。 中长度大于 的每个前缀,都不是任何较前字符串的前缀,所以
其中 lcp 是最长公共前缀的长度。对 in、inn、tea、ten、to,各项为 ,共 个非根节点。共用前缀恰好省去了公共前缀的长度。
插入、查找与列举
插入时从根依次沿字符前进,缺少子节点便建立,最后把终点标为终止。精确成员查询沿路径前进,只有终点存在且标为终止才回答是。缺边证明不存在;到达非终止节点表示精确单词不在集合中。非根节点仍是某个已存储单词的前缀;即使集合为空,根也可以存在。插入空字符串只标记根。
前缀查询先沿前缀前进;若路径不存在,便没有已存储单词带此开头。否则遍历其子树,在每个终止节点输出字符串;若前缀节点本身终止,也要输出该前缀。先输出节点,再按字母次序访问子节点,便得到字典序。这是列举:找到前缀节点本身不是输出全部答案的成本。
跟踪与共用前缀
例题 7.1.2
(建立含共用前缀的 trie)
向空 trie 插入 to、tea、ten、in、inn。表示出的前缀包括空前缀和
包括根共有九个节点。终止节点恰是插入的五个单词;te 非终止,而 in 是终止节点,同时有通往 inn 的子节点。列举前缀 te 时先输出 tea,再输出 ten。
反例模式
前缀节点也可以是单词
若删除 in 时移除其整个节点和子树,也会破坏 inn。只清除 in 的终止标记便移除该精确单词,同时保留较长单词。因此删除后能到达节点,仍不足以判定精确成员关系。
常见错误
(把到达的节点当作已存储单词)
在跟踪用的 trie 中,路径 te 存在,所以路径一走完就回答“是”的查询会出错。但 te 并非终止,集合并不包含它。成员判定既需要完整的路径,也需要终止标记。
不损害其他单词的删除
对存在的字符串,沿路径找到终点并清除终止标记。然后向根回走:只在当前非根节点没有子节点且非终止时移除它;任一条件不成立便停止。若字符串不存在,保持 trie 不变。即使根变成未标记叶节点,也绝不移除根。
定理 7.1.3
(插入、查询与删除保持标准形式)
设某个 trie 对有限字符串集合 是标准的, 为一个字符串。插入 得到对 标准的 trie。成员测试回答“是”,当且仅当 。按上述方式删除 :若 ,trie 不变;否则得到对 标准的 trie。
证明
(删除之后哪些节点仍然需要)
插入只为 缺少的前缀加入节点,而 的每个前缀都是 中某个成员的前缀。它把终点标为终止,其余不变。由标准形式, 的路径存在且终点为终止,当且仅当 ,这就给出成员测试。
对于删除,设 ,并设 是 的路径上的节点, 为根, 是 的节点。清除 的标记后,终止节点恰是 的成员。若非根节点的前缀是 中某个成员的前缀,就称它为需要的。不在 的路径上的节点,是 中某个异于 的成员的前缀,所以是需要的;只有 可能不需要。
循环从 向上走。它只在节点当下非终止且没有子节点时才移除它。这种节点是不需要的:若 的某个成员延伸其前缀,就会迫使更长前缀的节点存在,也就是有子节点,而曾被移除的子节点本身都是不需要的。循环在第一个终止或有子节点的节点停止。终止节点是 的成员,所以是需要的。仍然存在的子节点是需要的:不在 的路径上的子节点,是异于 的成员的前缀; 的子节点真延伸 ,所以是异于 的成员的前缀;若循环停在 (),它在路径上的子节点 已被移除,所以剩下的子节点都不在路径上。每种情况中,停止处的节点都是需要的。需要的节点的每个祖先,都是同一成员的前缀,所以全都是需要的,不会被移除。
因此剪枝后的 trie 恰好含有 中成员的各个前缀所对应的节点,终止标记也恰好位于这些成员。若 ,则路径不存在,或其节点不是终止,因此不作任何改动。
证明透视
为何循环需要两个停止条件
两个停止条件各自保护不同的东西。终止标记保护在此节点结束的单词;子节点保护经过此节点的更长单词。单靠任何一个都不够。取 并删除 tom:节点 m 被移除,而 to 随即成为没有子节点的叶节点。若循环只检查“没有子节点”,就会删去 to,丢失一个已存储单词。若循环只检查“非终止”,则会删去更长单词的前缀节点,这正是上面反例所示的失败。
论证在第一个需要的节点完成。它上面的所有节点都是该节点字符串的前缀,所以祖先不需要另外检查。因此循环可以在第一次失败时停止,无需查看路径其余部分。
例题 7.1.4
(从跟踪用的 trie 删除)
在例子中,删除 tea 会清除其标记,只剪去最后的 a 节点:te 仍通往 ten,所以保留。若改删 in,只清除其标记而不剪去任何节点,因为 inn 仍存在。删除空字符串时,如根已标记则清除它,但绝不删除根或其他单词。
例题 7.1.5
(边界情形:不存在的单词、最后一个单词与空字符串)
从跟踪用的 trie 删除 tex,找不到边 x,所以字符串不存在,没有任何改动。删除 te 同样不改动:其节点存在,但并非终止,所以 te 不是成员。
现在设 。删除 a 会清除标记。节点 a 非终止且没有子节点,所以被剪去。循环到达根就停止,根保持不动:这就是空集合的 trie。
最后设 ,所以根为终止,并有子节点 a。删除 只清除根的标记,其他不变,而 a 仍是成员。
成本取决于表示法
命题 7.1.6
(使用子槽位数组时的代价)
设每个节点有 个子槽位的数组,可按字符常数时间索引。精确查询长度为 的字符串需 时间。插入及删除需 时间;若把 视为固定常数,就成为 。若子树遍历访问 个节点并输出共 个字符,找到长度 的前缀并按字母次序列举需 。对所有 个节点,此表示使用 个子槽位。
证明
(计算访问的节点数与扫描的槽位数)
查询至多沿 条边前进,访问至多 个节点,每个花费常数时间。插入至多建立 个节点,初始化每个节点的 个子槽位花费 。删除先向下走至多 个节点,再向上走;每次“没有子节点”的检验扫描 个槽位,每次移除花费 ,合计 。列举时,找到前缀节点花费 ,每个被访问的节点扫描子槽位花费 ,合计 ,写出输出花费 。存储空间是每个节点 个槽位。
稀疏映射可节省槽位,但查找及有序遍历成本取决于具体映射。
常见错误
(只按前缀计算列举代价)
找到前缀节点需 ,但答案可能是其下的整棵子树。代价 包括被访问的节点数 与输出 。前缀虽短而子树很大时,即使前缀路径便宜,列举仍然昂贵。
习题与解答
快速检查
(前缀与单词。例子中的 te 是精确成员吗?)
检查终止标记,而不只是路径。
解答 · 答案
不是。其节点存在,但未标为终止。
快速检查
(删除。删除 tea 后,ten 和 to 哪些仍存在?)
各条路径经过哪些节点?
解答 · 答案
两者都在;其路径都不经过被移除的最后 a 节点。
快速检查
(根。空字符串如何存储?)
只有根代表空前缀。
解答 · 答案
把根标为终止;不论空字符串是否成员,根都存在。
快速检查
(输出成本。为何只找到前缀节点不足以界定列举成本?)
想一想找到前缀节点之后还要做什么。
解答 · 答案
算法仍可能访问许多后代,而且必须输出匹配单词的字符。