Huffman code是由David Albert Huffman在MIT与其同学发明的一种用语数据压缩的编码方式。

除了最短路径[shortest path]问题，图的另一个经典问题是最小生成树。给定一个图[一般是无向图]，有n个点及一些连接的边每个边上都有对应的权重[权重可以用来描述任何可以量化的因素]，现在我们想要寻找一个子图能够将所有的点都链接起来[也就是说在这个子图内，任何两个节点可以直接或者间接连通]，并且要求子图的权重最小。这个子图就是所谓的最小生成树，或者更准确的说最小权重生成数[最小生成树不是惟一的，一个图可能有多个不同的最小生成树，比如两条边的权重一样，选择任何一条都可以形成最小生成树]。

Terms [专有名词]

前文介绍的Floyd-Warshell算法是解决多源最短路径问题[mutiple-source shortest-paths problem]，即多个起始点的最短路径，而Dijkstra最短路径算法则是解决单源最短路径问题[single-source shortest-paths problem]，也即是给定一个点，只需计算出该点到达另一点的最短路径即可。Dijkstra算法是贪心算法思想的成功应用，其核心思想是每次找到离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其余所有点的最短路径。

最短路径问题是图论，乃至整个计算机算法领域的一个重要问题，寻找最短路径的方法根据情况不同也会有不同的变化，Floyd算法算是其中比较简单易用的一个。

发表在著名hack杂志Phrack上的文章 Smashing The Stack For Fun And Profit 第一次具体详细描述了如何实施buffer overflow[缓存溢出]攻击[其作者就是著名的Elias Levy]。

LFS[Log-structured File System]也是由Berkeley的研究人员最先提出并实现的，他们当时认为随机I/O和顺序I/O之间存在着巨大性能差异，其实就是顺序I/O快，随机I/O慢[因为要磁盘需要seek和rorate的时间]。所以说随机I/O成了bottleneck拖了后腿。但是记得在介绍FFS的blog中说过，即便在FFS中，一个write操作其实是至少5次write操作，因为写入一个data block还要更新对应的metadata信息，这里面就比不可少的需要随机I/O。要是能够只用顺序读写就好了，可以大幅度提高I/O效率了。同时Berkeley的研究人员还认为write操作占据了全部操作的很大一部分，因为Memory在快速增长，能够Cache的数据也越来越多那么就要涉及更多的write操作。所以基于这样两个考虑：(1)write占所有disk操作大部分；(2)随机IO性能比连续IO差很多，要是能只用连续I/O就会大幅度提高性能，LFS不更新任何数据只提供append[追加]操作，同时会建立buffer将多次操作放进一个segment里一次性写入来有效利用顺序IO。

Fast File System，快速文件系统，是由Berkeley大学研究人员设计并实现的建立在UNIX操作系统的一套文件系统。这个系统主要目标已经体现在它的名字上，就是建立一个快速的文件系统。因为他们发现之前的UNIX的文件系统（参考之前的Blog文章“Concepts of Unix File System”）在性能方面存在问题，主要问题是在磁头定位，位置转化过程中浪费了大量的时间，导致效率不高。所以FFS的一大设计思路就是降低磁头的seek时间，而解决方案也很简单，keep related stuff together，这样seek的时候就可以节省时间。整个FFS涉及几个关键概念