建设网站必须要配置apache吗,贵阳的网站建设公司,温州捷创网站建设,网站设计定制开门见山#xff0c;文本压缩可以归纳为两大类, 符号方法和字典方法#xff0c; 下面分别介绍下#xff1a; 1#xff09;符号方法#xff0c;symbolwise method普通编码方式是每个字符都采用相同位数编码#xff0c; 比如asc码#xff0c; 每个字符都是8位编码。那么现… 开门见山文本压缩可以归纳为两大类, 符号方法和字典方法 下面分别介绍下 1符号方法symbolwise method普通编码方式是每个字符都采用相同位数编码 比如asc码 每个字符都是8位编码。那么现在要压缩就是要用更少的位数来表示字符。显而易见 我们只须用较小的位数来表示高概率字符 用较长的位数来表示低概率字符这样平均下来就可以实现压缩。那么这里面就有两个点a怎么来确定每个待编码字符的概率这就是概率模型问题。所谓概率模型就是为编码器提供的概率分布函数我们必须保证编码器和解码器使用相同的模型 不然解出来的就不对了。那么对于一个符号的编码位数是有个下限的 和这个符合的信息量I(s)相关。I(s) -logPr[s] (Pr[s]就是s符合出现的概率)所以对于”掷硬币面向上“这个事实至少要用-log(1/2)1位来编码。那么对于字母表中每个符合的平均信息量称为”概率分布的熵entropy“ H sum(Pr[s]*I[s])假定符合以假设的概率值独立出现H为压缩下限。即这是个理论极值实际上不可能达到。这也就是Claude Shannon著名的编码原理。 回到模型可分为每个字符都当独立的符号来处理的0阶模型和仅考虑有限个前驱符号的m阶有限上下文模型。 也可分为静态模型 半静态模型 和自适应模型。静态模型就是不考虑正在编码的文本只使用固定的模型这个模型就适用于文本模式相对固定的任务。半静态模型就先为要压缩的文件生成模型 发送给解压方 这个方法需要遍历两遍被压缩的文档 所以这个solution明显不太好。所以比较流行的是自适应模型adaptive modeling即以平缓的概率模型开始 随着遇到的符号变多 不断的调整。自适应模型往往要解决零频问题这个问题解决方法很多 最简单的是默认每个字符在刚开始时已出现过一次。这种模型的缺点是不能对文本进行随机访问 必须从文本的开头开始解码因为我们必须保证编码和解码时的context是相同的。 对于怎么建立符号概率模型 也是有很多研究 比如部分匹配模型Prediction by Partial Matching, PPM依据以前的字符做出预测, 动态马尔可夫模型基于有限状态机。这些模型就不详细描述了 有兴趣可以参看相关文献。 b知道待编码字符的概率怎么给它分配合适的编码 这就是编码算法的问题。 哈夫曼编码介绍编码算法当然先来看看哈夫曼编码 这个号称是作者在研究生时为了避免参加科目考试而想出的算法很简单也很高效。再一次对美国的教育环境表示深深的敬意和向往。这类算法基本想法就是给高概率字符分配较少位数的编码。这就有个问题 如果每个字符的编码位数不一样 那么我们怎么知道后一个字符的编码位数肯定不能用个len去指定。哈夫曼的方法是解决编码前缀的歧义性ambiguity 即前缀编码就是说每个编码的前缀都是不同的那么怎么去产生编码和怎么去解码呢哈夫曼树通过哈夫曼树从下到上进行编码 从上到下进行解码。具体怎么构建哈夫曼树 就不具体说了 很简单。再一次感叹此算法构思的巧妙和简单。对于静态的概率分布 哈夫曼算法是很好的 但对于自适应模型哈夫曼算法会耗费较多的内存或时间。因为自适应模型在同一时间会使用许多不同的概率分布依赖于被编码文本的上下文的不同。那么这样就要同时建立多颗哈夫曼树。 算术编码 那么对于自适应模型而言算术编码更受欢迎。算术编码相对比较复杂不过显著的优势是算术编码可以用低于一位的编码来表示高概率字符 而哈夫曼编码对于每个字符至少要用一位来编码。由于算术编码包含了各种不同的概率分布 所以比较适合自适应模型。但对于静态模型还是哈夫曼编码要快许多。 算术编码的基本思想就是 在编码过程中 随着各个字符的出现不断缩小概率区间 高概率字符不会大幅地缩短区间而低概率字符会导致产生一个小的多的‘下一个’区间。算术编码只有当编码完成时才会一次性输出编码编码值就是在最终的概率区间内任意选取一个值区间越小表示这个值所用的位数越多。不好理解就举个例子对于只有3个字符的字符集a,b,c, 对bccb进行编码为解决零频问题 开始假设a,b,c个出现过一次编码前概率区间为[0,1]此时abc的概率都是1/3所以abc各占概率区间的1/3, 如b的概率区间为[0.33, 0,66]开始编码......第一个字符b所以概率区间缩短为[0.33, 0,66]此时a:b:c的比例为1:2:1所以各个字符的概率区间变为a [0.333,0.416], b [0.416, 0.583], c [0.583, 0.666]第二个字符c所以概率区间缩短为[0.583, 0.666]此时a:b:c的比例为1:2:2所以各个字符的概率区间变为a [0.583,0.600], b [0.600, 0.633], c [0.633, 0.666]第三个字符c所以概率区间缩短为[0.633, 0.666]此时a:b:c的比例为123。。。。。。最终概率区间缩小至[0.639, 0.650]所以0.64就可以作为bccb的编码。 而解码的过程就是照着编码的过程重做一遍即可解码前概率区间为[0,1]此时abc的概率都是1/3所以abc各占概率区间的1/3, 如b的概率区间为[0.33, 0,66]所以0.64落在了b的概率区间内, 第一个字符为b概率区间缩短为[0.33, 0,66] 此时a:b:c的比例为1:2:1所以各个字符的概率区间变为a [0.333,0.416], b [0.416, 0.583], c [0.583, 0.666]所以0.64落在了c的概率区间内, 第二个字符为c。。。。。。最终完成解码。 区间中的数需要的多少位来表示和区间长度的负对数成正比。而最终的区间长度是已编码符合概率值的乘积显而易见。而log(AB) log(A)log(B), 所以最终的区间长度的对数就等于所有已编码符号单独概率值的对数的和。所以具有概率Pr[s]的符号s对输出编码的贡献是-logPr[s] 与符号信息量相同。所以算术编码的输出位数接近最优。 2字典方法dictionary method字典模式很好理解 用字典里面的码字来替换原文如果这个码字比原文的位数少那么就实现了压缩 如果你的字典是独有的 不公开的 那么就实现了加密。那么为了实现压缩 就要基于词或短语进行编码 基于字符压缩效果肯定不好 那么如果这个字典是静态的因为各个领域的词和短语都不一样的 所以不可能适用于所有文本。也有半静态的就是每次对要压缩的文本生成一个字典这个方法肯定也不好。所以就有自适应的字典方案adaptive dictionary scheme 这个就有技术含量了怎么产生自适应的字典了。当然牛人是很多的Ziv和Lempel发明了LZ77和LZ88两种方法。牛人想出来的方法都是很简单很好用的 这个也不例外基本原理就是文本的子串被指向其以前出现之处的指针所替换。说白了就是字典码书就是文本本身 码字就是指针。个人感觉在发明这个方法时 作者可能并没有想到什么基于字典模式的方法应该是后面的学者把它归到这类了。我们就以LZ77来了解下这个方法LZ77的输出码是一系列三元组a,b,c, a表示往前回溯多远 b表示短语多长 c表示要输入的下一个字符。为什么要有c项是为没有出现过的字符准备的, 这个设计照顾了新字符引进的需要。以abaabab为例输出码为0,0,a (0,0,b) (2,1,a) (3,2,b)这个方法需要在之前的文本中找到最大匹配窗口 这个不能线性查找 一般采用散列表 或二分查找树来实现。 著名的Gzip就是这个算法的一个变体Gzip用hash table来定位之前出现的字符串 用3个连续的字符作为hash键值链表中记录了这三个字符在窗口中出现的位置信息。出于效率的考虑限制了链表的长度 其实也没有必要记录过远的位置 记较近的几个位置比较合理。Gzip比较有意思的是对指针的偏移值也做了哈夫曼编码较常用的值用较少的编码。同时对字符串匹配长度值 也采用哈夫曼编码。当之前没有发现匹配的时候 传递一个原始字符raw character有意思的是这个原始字符和字符串匹配长度值公用同一个编码。也就是说第二项有可能是个字符串匹配长度值 也有可能是个原始字符反正前缀编码 也不冲突 用心良苦都是为了压缩。 转载于:https://www.cnblogs.com/fxjwind/archive/2011/07/04/2097718.html
