Java教程

算法初识A

本文主要是介绍算法初识A，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

最优编码树

哈夫曼编码，Huffman Code

  • 编码，字符映射到二进制序列

  • 解码，二进制序列还原成对应的字符

  • 压缩（有损/无损），用较少的01序列描述原始信息

  • ASCLL编码，将字母、数字和一些常用的符号用一个字节编码
      eg:ASCII编码：“A”-01000001，十六进制：0x41

  • GBK/GB2，针对简体字的编码，每个汉字用两个字节编码
       GBK，”算“——CBE3， ”法“——B7A8

  • Unicode

  • UTF-8

  • 定长编码A、B、C、D

  • 不定长编码（频率高字符用较短的编码）

  • 前缀码问题

  • 编码效率：编码总长度÷字符数

  • 问题：给定符号计和S={S1，S2，…，Sn}，每个符号频次f={f1，f2，…，fn}，设及一套符号编码（变长），sigma fi×Li极小化
    在这里插入图片描述
    在这里插入图片描述
    以上哪个编码方式效率最高？答案是显而易见的[/滑稽]
    哈夫曼编码树（Huffman）
    东山放

  • 设A，B，C三个字符出现的频次分别为3，2，1
    Huffman算法：自下而上构建最优二叉编码树
    在这里插入图片描述
    Haffman编码算法描述：
    重复以下过程：

  • 1、创建Huffman树节点：
      选频数最小的两个节点i，j，创建其父节点k，fk=fi+fj

  • 2、调整频率集合：
      添加新建父节点的频率fk，删除两个子节点频率fi，fj
    在这里插入图片描述
    在这里插入图片描述
    哈夫曼编码是最优编码，但不唯一
    在这里插入图片描述

  • 贪心策略
      每一步都采取当前最好的选择从而希望达到全局的最优解，贪心策略并不每次都得到最优解

这篇关于算法初识A的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航