19软件工程《数据结构与算法》 第六周安排

理论课

讲解第4章的内容 99-113页

1、字符串的定义、存储结构

2、模式匹配BF、KMP （重点、难点）

3、矩阵的压缩存储

实验课

完成实验栈和队列

提示:第7周将会进行小测，大家可以根据自己的情况进行相应的复习

师说

本章中有部分同学会好奇为什么要引入以列序为主序和以行序为主序的存储方式?答案是因为一般情况下存储单元是单一的存储结构，而数组可能是多维的结构，则用一维数组存储数组的数据元素就存在着次序约定的问题，所以就有了以列序为主序和以行序为主序的存储方式。另外，目前大数据存储有两种方案可供选择:行存储（Row-Based）和列存储（Column-Based）。业界对两种存储方案仍存在很多争议，集中焦点是:哪个能够更有效地处理海量数据，且兼顾安全、可靠、完整性。从目前发展情况看，关系数据库已经不适应这种巨大的存储量和计算要求，基本是淘汰出局。

适逢深圳特区建立40周年，在最近举行的2020第三届深圳分布式存储行业大会上，在深入探讨IPFS/Filecoin技术潜力的同时，一同探索应用落地场景，助力区块链行业在2020年实现飞跃式发展。随着百万亿级别的数据经济时代的到来，新基建的建设速度正在加快步伐，数据也将呈现爆发式增长，对可靠、安全的分布式存储需求量大增，IPFS/Filecoin生逢其时，应该承担起这一历史使命。

模式匹配在传统的应用中是一项重要的操作，如信息集成、数据仓库、分布式查询处理等。现在大数据时代，模式匹配更显重要，模式匹配已几乎成为每个数据密集型分布式应用的一项基本任务。作为数据结构中字符串的一种基本运算场景，给定一个子串，要求在某个字符串中找出与该子串相同的所有子串。尽管早已可以在python下使用正则表达式或者使用其他语言的开发包可以高效而简洁地实现模式匹配，但了解相关算法背后机理亦不失其学习的意义。

扩展阅读

1. Brute-Force算法

核心思想在于从 T 的第一个字符开始遍历每一个字符，依次匹配 P。是最简单，也最低效的匹配方法

2. Boyer-Moore算法

通过跳跃启发式算法避免大量无用的比较。每次逐字符匹配从 P 最后一个字符开始。

3. Knuth-Morris-Pratt算法

穷举算法和 Boyer-Moore 算法在完全匹配中必然进行 len(P) 次匹配，KMP 算法充分利用 P 内部的字符串重叠，做进一步优化。

模式匹配算法总结

https://blog.csdn.net/weixin_43269174/article/details/90485767

关于KMP算法（105-107页），如果看不明白，可以通过下面的链接从另外一种维度进行理解

ttp://www.tuicool.com/articles/e2Qbyyf