3.5 应用
Robert Sedgewick Kevin Wayne
在计算机发展的早期，符号表帮助程序员从使用机器语言的数字地址进化到在汇编语言中使用符号名称；在现代应用程序中，符号名称的含义能够通行于跨越全球的计算机网络。快速查找算法曾经并继续在计算机领域中扮演着重要角色。符号表的现代应用包括科学数据的组织，例如在基因组数据中寻找分子标记或模式从而绘制全基因组图谱；网络信息的组织，从搜索在线贸易到数字图书馆；以及互联网基础构架的实现，例如包在网络结点中的路由、共享文件系统和流媒体等。高效的查找算法确保了这些以及无数其他重要的应用程序成为可能。在本节中我们会考察几个有代表性的例子。
能够快速并灵活地从文件中提取由逗号分隔的信息的一个字典程序和一个索引程序。逗号分隔的格式（及类似格式）常用于存储网络信息。
为一组文件构建逆向索引的一个程序。
一个表示稀疏矩阵的数据类型。它用符号表处理的问题规模能够远远大于这种数据类型的标准实现。
在第 6 章中，我们会学习一种适合于数据库或者文件系统的符号表，它能够保存的数据量超过你的想象。
符号表在本书其他章节的算法中也会起到关键的作用。例如，我们会使用符号表来表示图（第 4 章）以及处理字符串（第 5 章）。
在本章中我们已经看到，实现能够快速进行各种操作的符号表是一项很有挑战性的任务。另一方面，我们学习过的实现都经过了仔细研究，应用广泛并且在许多环境中都可用（包括 Java 的标准库）。从现在开始，符号表就将成为你的编程工具箱中的一件重要武器。
3.5.1 我应该使用符号表的哪种实现
表 3.5.1 总结了由本章中多个命题和性质得到的各种符号表算法的性能特点（散列表的最坏情况除外，它的结果来自于研究文献并且也不太可能在实际应用中遇到）。从表中显然可以知道，对于典型的应用程序，应该在散列表和二叉查找树之间进行选择。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入介绍了符号表在计算机科学中的重要性和实际应用。符号表在科学数据组织、网络信息组织和互联网基础构架实现中发挥着重要作用，同时在文件中提取信息、构建逆向索引、表示稀疏矩阵等方面也有具体应用。文章比较了散列表和二叉查找树在典型应用程序中的选择，以及在特定情况下的优劣势，并介绍了符号表实现中的一些改进和优化方法。此外，还详细介绍了符号表在电话黄页、字典、账户信息、基因组学、实验数据、编译器、文件系统、互联网 DNS 等领域的典型应用。文章还提供了从文件或网页中提取逗号分隔信息的程序示例，展示了符号表在实际应用中的灵活性和多样性。总的来说，本文通过对符号表的应用和实现进行详细介绍，为读者提供了深入了解符号表在计算机科学中的重要性和实际应用的全面视角。文章还强调了符号表在处理巨型稀疏矩阵等大规模数据时的重要性，以及在科学计算中的广泛应用和性能优化的潜力。
仅可试看部分内容，如需阅读全部内容，请付费购买文章所属专栏
《算法（第 4 版）》
《算法（第 4 版）》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示，欢迎踊跃留言。
收起评论