5.5 数据压缩
Robert Sedgewick Kevin Wayne
这个世界充满了数据,而能够有效表达数据的算法在现代计算机基础架构中有着重要的地位。压缩数据的原因主要有两点:节省保存信息所需的空间和节省传输信息所需的时间。尽管科技在发展,但是这两点的重要性并没有发生变化,如今任何需要更大存储空间或是长时间等待下载任务完成的人都会意识到数据压缩的重要性。
当你在处理数字图像、声音、电影和其他各种数据时,就已经在与数据压缩打交道了。我们将会学习的算法之所以能够节省空间,是因为大多数数据文件都有很大的冗余:例如,文本文件中有些字符序列的出现频率远高于其他字符串;用来将图片编码的位图文件中可能有大片的同质区域;保存数字图像、电影、声音等其他类似信号的文件都含有大量重复的模式。
我们将会讨论广泛应用的一种初级的算法和两种高级的算法。这些算法的压缩效果可能有所不同,取决于输入的特征。文本数据一般都能节省 20% ~ 50% 的空间,某些情况下能够达到 50% ~ 90%。你将会看到,任何数据压缩算法的效果都十分依赖于输入的特征。注意:本书中,我们在提到性能的时候一般指的都是时间;而对于数据压缩,性能指代的是算法的压缩率,当然也会考虑压缩的用时。
从另一方面来说,现在的数据压缩技术并没有以前那么重要了,因为计算机的存储设备的成本已经大幅度降低,普通用户拥有的存储空间比以前要多得多。但是,现在数据压缩技术也比任何时候都更重要,因为现在存储的数据更多了,因此数据压缩能够节省的空间也就更大了。事实上,随着互联网的出现,数据压缩得到了更加广泛的应用,因为它是减少传输大量数据所需时间的最经济的办法。
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
本文深入探讨了数据压缩技术的重要性和应用,介绍了无损压缩和有损压缩的概念,并指出了数据压缩算法的局限性。通过实用的示例和清晰的语言,读者可以快速了解数据压缩技术的基本概念和应用,特别强调了基因数据的压缩方法,展示了在现代基因组学中应用数据压缩技术的重要性。此外,还介绍了前缀码的概念和展开、压缩的过程,以及单词查找树的结点表示和使用前缀码进行数据压缩的步骤,为读者呈现了数据压缩技术的实际应用和操作方法。通过对霍夫曼编码的构造和最优性的讨论,读者可以深入了解数据压缩算法的原理和优势。文章还探讨了算法在商业应用、科学计算、工程学和运筹学等领域的重要性,强调了算法在现代社会中的广泛应用和影响。整体而言,本文为读者提供了对数据压缩技术的基本了解,以及相关技术的应用和重要性。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《算法(第 4 版)》
《算法(第 4 版)》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论