Question

算法可粗分为数值算法和非数值算法，本文主要研究非数值算法。

1.1 压缩算法

原理 ： 数据的冗余性，来自信息论中香农的 熵 。

概论 ： 可分为有损和无损压缩。 无损压缩的模型主要有： Huffman 编码，算术编码, 字节压缩和字典压缩等。

里程碑 ：

1948 , 香农在 Bell System Technical Journal 上发表了《A Mathematical Theory of Communication 》, 提出了 熵 的概念，为现代信息论的创始人。

1952 , D.A.Huffman 发表论文 A Method for the Construction of Minimum Redundancy Codes

1977 , 以色列人 Jacob Ziv 和 Abraham Lempel 发表了论文 顺序数据压缩的一个通用算法 (A Universal Alogrithem for Sequential Data Compression)。简称 LZ77。

1978 , 他们发表了该论文的续篇 通过可变比率编码的独立序列的压缩 (Compression of Individual Sequences via Variable-Rate Coding)。简称 LZ78。

1984 , Terry Welch 发表了名为 高性能数据压缩技术 (A Technique for High-Performance Data Compression) 的论文。 简称 LZW。

压缩技术的概况是：

                     压缩技术
                        |
                /------------------------------\
         通用无损数据压缩           多媒体数据压缩 (大多为有损压缩)
               |                                |
    /----------------\            /------------------------------------\
基于统计         基于字典    音频压缩        图像压缩                视频压缩
模型的压         模型的压        |              |
缩技术           缩技术         MP3 等在      /-------------------、      AVI
    |                 |                  二值   灰度   彩色   矢量     MPEG2 等
  /------\          /-------------\      图像   图像   图像   图像
Huffman  算术      LZ77   LZ78   LZW       |      |      |      |
编码     编码       \-------------/     传真机  FELICS  GIF    PostScript
 |         |               |            标准    JPEG 等  JPEG 等 Windows WMF 等
UNIX 下    接近无损    PKZIP、LHarc、ARJ、
的 COMPACT 压缩极限    UNIX 下的 COMPRESS
程序等    的高级应用  程序等

1.2 串的模式匹配算法

算法	预处理时间	匹配时间
朴素算法	0	O(n-m+1)
KMP	O(m)	O(n)
flashtxt		O(n)
DFA		O(n)

注：n 表示原串的长度，m 为匹配度的长度

1.3 图论算法

G ＝ (V，E) V 为顶点集合 ｛v1,v2...} ; E 为边集合， E1 = {vi, vj}

1）显示图

概念： 图的结构显式给出，包括图的顶点，边及权重。 如路径问题，着色问题。

常用术语：权，环，入度，出度，路径，连通图，网络

搜索策略： 穷举搜索包括深度优先和广度优先。

2）隐式图

概念：一些求解，最优化或证明题中，给出初始结点和目标，在解问题过程中使用的搜索空间如子集树或排列树。

常用术语：子集树（问题在 n 个元素的子集中进行｝，排列树（问题在 n 个元素的排列中进行）

搜索策略： 启发式搜索包括回溯和分支限界等。

本章参考

[1]. http://datacompression.info/

[2]. 笨笨数据压缩教程 http://wenku.baidu.com/view/c204071555270722192ef701.html