一些关于矩阵的基础知识

一、特殊矩阵

正方矩阵/方阵( Square matrix )     大小为n×n 的矩阵

单位矩阵( Identity matrix )             对角线上元素为1,其余元素为0 的方阵,常用I 表示

置换矩阵( Exchange matrix )        反对角线上元素为1,其余元素为0 的方阵,常用J 表示

对角矩阵( Diagonal matrix )          非对角线上元素全为零的方阵

对称矩阵( Symmetric matrix )       满足矩阵中元素eij = eji   的方阵

三角矩阵(Triangle matrix)             分为上三角矩阵(元素eii 以上元素为零)和下三角矩阵

正交矩阵(Orthgonal matrix)          满足MTM = I 的方阵,矩阵和矩阵转置的乘积为单位矩阵

继续阅读

信息论基础

信息论是应用数学,电子信息工程和计算机科学相关信息量的一个分支。信息论最早是由香农同学发展起来的,他提出了信号处理操作如数据压缩和可靠地存储、传输数据的基本限制。现已推广并发展到多个领域:自然语言处理(NLP)、加密、包含通信网络更大范围的网络,如神经网,还有量子计算、其他形式的数据分析等等。

衡量信息的一个重要工具是熵(或者称为信息量,为统一起见,下文将全部用熵代替),它用来表示在信息中存储或通信一个符号需要的平均比特长度。熵量化了预测一个随机变量的值的不确定性。比如,说出一次投币过程的结果(两个等概率可能出现的结果)比说出一次掷骰子的结果(六个等概率可能出现的结果)的信息量要少。

应用到信息论基础涉及但不局限于以下方面:无损压缩、有损压缩和信号编码等。

继续阅读

HTTP 协议

一、HTTP 协议特点

  1. 支持客户端/服务器模式
  2. 客户端请求时,只需发送请求方式和路径,请求的方法有GET/HEAD/POST 等方式
  3. HTTP 允许传输任何类型数据对象。正在传输的数据类型为Content-type 定义
  4. 无连接,每次连接仅处理一个请求,Server 处理完Client 的请求,收到Client 的回复后断开连接
  5. 无状态,对于事务处理没有记忆能力

继续阅读

B- 树和B+-树

B- 树和B+-树是重要的两个用于数据检索的数据结构,广泛用在文件系统、数据库和数据检索中。

【重申】没有“B’减’树”这样的树,在之前的’-‘ 是个横杠杠

B- 树

类似于二分查找树。但不同于二分查找树,B 树可以有多个孩子节点,这样树的深度就不会太深,其次B 树是平衡树,即所有叶子节点到根节点路径长度一样,所有非叶子节点的孩子节点都满足一定条件(不少于$\lceil m/2 \rceil$、不多于m,m 为阶数),这样查找一个节点就不会便利太深。对B 树有这样的限制:

  1. 非叶子节点有至少$\lceil m/2 \rceil$ 个、至多m 个子节点
  2. 根节点可以至少有两个节点
  3. 所有叶子节点在同一层
  4. 有k 个子节点的非根节点恰好包含k-1 个关键码(key)

满足上面四个要求的树就是B 树。下图是一个m=5阶B 树例子,每个节点最少$\lceil 4/2 \rceil=3$个、最多5 个节点(指针)。关键码是用于区分左右子树(左边子树关键码都比该节点小,右边子树关键码都比该节点大),且非叶子节点和叶子节点关键码内都包含了关键码对应的数据信息(这点和B+ 树不同)。当插入和删除时会发生树的合并和拆分,具体参考【B树 和B+ 树】【性能分析】【动态动画演示】。

400px-B-tree.svg

B 树内没有重复的关键码,且把关键码相近的放在一起,利用了访问的局部性原理。根据第一点B 树有一定比率的非叶子节点是满的(>50%,B* 树可保证>75%),这样就能够提高空间利用率,减少检索和更新磁盘读取次数。但B- 树也有自己的问题:

  1. 因为非叶子节点上的关键码也包含了对应的信息,所以非叶子节点也会变得比较大,影响了阶数m 的扩展
  2. 当需要获取全部或者某个区段的关键码对应的信息,需要遍历B 树

 

B+-树

B+ 树针对B 树一些性能上的缺陷进行了改进,所以B+ 树在使用上更加广泛,通过性能分析和实际应用发现B+ 树比B 树更优。B+ 结构是这样定义的:

  1. 每个节点(除了根节点)至少有$\lceil m/2 \rceil$ 个、至多m 个子节点(同B 树)
  2. 根节点至少有两个子节点
  3. 有k 个子节点的节点必有k 个关键码
  4. 每个叶子节点都有指向下一个叶子节点的指针

从结构上看B+ 树减少了一个指向叶子节点的指针,B 树中关键码是左右子树的划分,不与子节点的某个关键码相同,而在B+ 树中关键码可以与右子树最小的关键码相同,这是因为B+ 树中只有非叶子节点才真正保存关键码对应的信息,而非叶子节点只是用来划分叶子节点和保存叶子节点关键码索引而已。这样非叶子节点就变得非常简单阶数m 也可以取得比较大(类似于文件系统中的inode,如果inode 中也保存了一些数据块的话就会变得很大,每次访问inode 就变得慢了)。

第二个变化就是如下图在每个叶子节点上都有连接下一个叶子节点的指针,这样就将所有的叶子节点以线性检索链表的方式连接了起来。在范围查询和做检查点或者备份时会更快。

800px-Bplustree

 

如果你觉得讲的太简单了,可以参考这里,没见过比那讲的更详细的了!但我个人感觉自己理解了就OK 了,总不至于要自己去写一个B 树的算法~