5.2 单词查找树

Robert Sedgewick　Kevin Wayne

和排序一样，我们也可以利用字符串的性质开发比第 3 章中介绍的通用算法更有效的查找算法，以便用于以字符串作为被查找的键的一般应用程序。
具体来说，本节中所讨论的算法在一般应用场景中（甚至对于巨型的符号表）都能够取得以下性能：
查找命中所需的时间与被查找的键的长度成正比；
查找未命中只需检查若干个字符。
仔细思考过后你会发现，这样的性能是相当惊人的。它们是算法研究的最高成就之一，也是建成现今能够便捷、快速地访问海量信息所依赖的基础设施的重要因素。更重要的是，我们可以扩展符号表的 API，添加基于字符的用于处理字符串类型的键的操作（但不必为所有 Comparable 类型的键都添加类似操作）。它们在实际应用中非常强大并实用，如表 5.2.1 所示。
表 5.2.1　以字符串为键的符号表的 API
    public class <b>StringST<Value></b>
                 StringST()创建一个符号表
            void put(String key, Value val)向表中插入键值对（如果值为 null 则删除键 key）
           Value get(String key)键 key 所对应的值（如果键不存在则返回 null）
            void delete(String key)删除键 key（和它的值）
         boolean contains(String key)表中是否保存着 key 的值
         boolean isEmpty()符号表是否为空
          String longestPrefixOf(String s)s 的前缀中最长的键
Iterable<String> keysWithPrefix(String s)所有以 s 为前缀的键
Iterable<String> keysThatMatch(String s)所有和 s 匹配的键（其中“.”能够匹配任意字符）
             int size()键值对的数量
Iterable<String> keys()符号表中的所有键
这份 API 与第 3 章中所介绍的符号表 API 有以下不同：
将泛型的 Key 的类型换成了具体的类型 String；
添加了 3 个方法：longestPrefixOf()、keysWithPrefix() 和 keysThatMatch()。
本节仍然遵守第 3 章中实现符号表时的几个基本约定（不接受重复键或空键，值不能为空）。
从对字符串的排序算法中可以看到，指定字符串的字母表常常是十分重要的。对小型字母表的简单而高效的实现不适用于大型字母表，这是因为后者消耗的空间太多。在这种情况下，应该添加一个构造函数，允许用例指定所使用的字母表。我们会在本节稍后讨论这个构造函数的实现，但目前暂时没有在 API 中列出它，因为要将精力集中在字符串类型的键上。

公开

同步至部落

取消

完成

0/2000

荧光笔

直线

曲线

笔记

复制

AI

深入了解
翻译
英语
中文简体
中文繁体
法语
德语
日语
韩语
俄语
西班牙语
阿拉伯语
解释
总结

本文深入介绍了三向单词查找树的数据结构及其在字符串键查找中的应用。通过详细讨论单词查找树的基本性质、数据表示方法和Java实现，以及新增的几个方法的实用性，读者能全面了解该数据结构的原理、实现和应用。文章还讨论了三向单词查找树的性质，包括空间利用、查找成本和适应不规则键的优势。此外，对于前缀匹配、查找所有键和通配符匹配等操作的实现也进行了探讨。总的来说，本文通过深入的技术讨论和丰富的实例，使读者能够全面了解三向单词查找树的原理、实现和应用，为他们在实际项目中应用该数据结构提供了有力支持。文章还对比了不同字符串查找算法的性能特点，指出了三向单词查找树在特定场景下的优势，为读者提供了选择合适实现方式的参考。

仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《算法（第 4 版）》

立即购买

登录后留言

精选留言

由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。

收起评论

public class <b>StringST<Value></b>
StringST()	创建一个符号表
void put(String key, Value val)	向表中插入键值对（如果值为 null 则删除键 key）
Value get(String key)	键 key 所对应的值（如果键不存在则返回 null）
void delete(String key)	删除键 key（和它的值）
boolean contains(String key)	表中是否保存着 key 的值
boolean isEmpty()	符号表是否为空
String longestPrefixOf(String s)	s 的前缀中最长的键
Iterable<String> keysWithPrefix(String s)	所有以 s 为前缀的键
Iterable<String> keysThatMatch(String s)	所有和 s 匹配的键（其中“.”能够匹配任意字符）
int size()	键值对的数量
Iterable<String> keys()	符号表中的所有键