热门文章 | 热门软件| 热门源码 | 热门电影 | 知识库 | 联系我们
软件 源码 教程 影视 健康 招聘
  HTML | JavaScript | ASP | PHP | JSP | NET | VB | VC | VF | Windows | Linux | Mysql | Mssql | Oracle | Struts 
当前位置: 创世纪计算机资源网 -> 文章频道 ->vb 
站内搜索:
哈夫曼算法(附编码规则)
作者:佚名 来源:不详 整理日期:2007-4-13

算法原理:

    ht首先被提出来,是为了解决这样的问题:

    对于N种数据(比如5种数据:A、B、C、D、E),在出现的频率已知的情况下(比如分别出现了3、5、2、6、4次),如何用不等长的01串来分别表示它们,使01串的总长度最短。

    比如原始串:ABADBCBDABEDBDEDCEDE 

    对于这个问题,首先得到:任何一个01串都不能是其他01串的前缀。也就是说,如果用“10”来表示A,那么其他01串就不能以“10”开头。
    建立01串的步骤如下:

    首先找到出现最少的两个数据(A、C),分别以它们为左右子树,建立一个二叉树。并将它们出现次数之和作为根节点:

1)

    5   5B  6D  4E
   / \
  3A 2C

    然后从剩下的4个数举重找到两个最小的,做同上的操作,知道只剩一个数据为止:

2)

    5         9    6D
   / \        / \
  3A 2C 5B 4E
  
3)

      11       9
     /  \       / \
    5   6D  5B 4E
   / \
  3A 2C
  
4)
           20
          /    \
       11      9
      /  \       / \
     5   6D  5B 4E
    / \
   3A 2C

    最后从根节点开始,每个左子树填0,右子树填1:

             ROOT
            /      \
           0        1
          / \        / \
         0  1D  0B 1E
        / \
       0A 1C

    这样每个数据对应的01串就是从根节点到数据所在的叶子节点的路 径:

A: 000
B: 10
C: 001
D: 01
E: 11

    这样原始串ABADBCBDABEDBDEDCEDE就成了:

000100000110001100100010110110011101001110111


压缩:

    把256个Ascii码看作256种数据,分析它们出现的次数,建立ht,得到256个01串。用这256个01串去替换原来的字符并按照二进制处理,就可以得到压缩后的文件了。

相关文章