专栏首页大前端当Kotlin遇见数据结构丨哈夫曼编码

当Kotlin遇见数据结构丨哈夫曼编码

哈夫曼编码定义

哈夫曼编码是一种编码格式,属于可变字长编码的一种,该方法依照字符出现的概率来构建异字头的平均长度最短的码字,最终实现根据使用频率来最大化节省码字(字符)的存储空间和提高传输效率的目的,在数据压缩和通讯领域应用的非常广泛。

哈夫曼编码的码字是异前置码字,任一码字不会是另一码字的前面部分,这样各种码字可以连在一起传输,中间无需空格分离但又不会混淆。


Kotlin 中对字符串进行哈夫曼转码

对一串字符进行哈夫曼编码可分为五个流程:

1. 统计字符出现的次数,使用 HashMap 集合存储统计结果
        // HashMap 的 key 就是字符本身,value 为出现次数
        var arrMap:HashMap<Byte,Int> = HashMap()

        for(value in arr){

            var count = arrMap.get(value)

            // 次数不为空则继续叠加计数
            if(null != count){
                arrMap.put(value,count + 1)
            }else{
                arrMap.put(value, 1)
            }

        }
2. 遍历 HashMap 内容转化为二叉树的节点 Node ,使用 ArrayList 集合存储所有 Node
        var nodes:ArrayList<Node> = ArrayList()

        for((key,value) in arrMap){
            // Node 的 data 存储的就是字符本身,value 存储的是字符出现的次数,也是节点的权值
            nodes.add(Node(data = key, value = value))
        }
3. 以存储所有 Node 的 ArrayList 为源数据,构建哈夫曼树
    /**
     * 生成哈夫曼树
     * @param nodes: 待处理的节点集合
     *
     * @return 已构建完成的哈夫曼树
     * */
    fun createNodeTree(nodes: ArrayList<Node>): Node {

        while (nodes.size > 1){

            // 排序
            Collections.sort(nodes)

            // 整合
            var leftNode = nodes.get(nodes.size - 1)
            var rightNode = nodes.get(nodes.size - 2)
            var data = null
            var value = (nodes.get(nodes.size - 1).value!! + nodes.get(nodes.size - 2).value!!)
            var newNode = Node(leftNode = leftNode , data = data , value = value , rightNode = rightNode)

            // 删除
            nodes.remove(leftNode)
            nodes.remove(rightNode)

            // 添加
            nodes.add(newNode)
        }

        return nodes.get(0)
    }
4. 生成哈夫曼编码表,也就是生成由根节点到达不同叶子结点所需路径的集合
    // 哈夫曼临时编码(路径)
    var huffLine:StringBuffer = StringBuffer()

    // 哈夫曼编码表
    var huffCodes:HashMap<Byte, String> = HashMap<Byte, String>()

    /**
     * 生成哈夫曼编码对照表
     * @param nodeTree: 哈夫曼树
     *
     * @return 已构建完成的哈夫曼编码对照表
     * */
    fun createHuffCode(nodeTree: Node): HashMap<Byte, String> {

        getLine(nodeTree.leftNode,"0",huffLine)

        getLine(nodeTree.rightNode,"1",huffLine)

        return huffCodes
    }

    /**
     * 递归拼接所有叶子节点路径(编码)
     * @param node:准备拼接路径的节点
     * @param code:路径值
     * @param huffLine:前一路径值
     * */
    fun getLine(node: Node?, code: String, huffLine: StringBuffer) {

        var huffLine = StringBuffer(huffLine)

        huffLine.append(code)

        if(null == node?.data){
            getLine(node?.leftNode,"0",huffLine)
            getLine(node?.rightNode,"1",huffLine)
        }else{
            huffCodes.put(node.data!!,huffLine.toString())
        }
    }
5. 根据生成的编码表对字符串进行哈夫曼编码
    /**
     * 对字符串进行哈夫曼编码
     * @param arr: 目标字符串
     * @param huffCodeTable: 编码对照表
     *
     * @return 已完成哈夫曼编码的字符串的byte数组
     * */
    fun createHuffByte(someStr:String , huffCodeTable: HashMap<Byte, String>): ByteArray {

        var strArr: ByteArray = someStr.toByteArray()

        var resultStr = StringBuffer()

        // 拼接编码结果
        for(b in strArr){
            resultStr.append(huffCodeTable.get(b))
        }

        // 以8位为一组对编码结果进行分组
        var arrCount = 0
        if (resultStr.length % 8 == 0) {
            ByteArray(resultStr.length / 8)
            arrCount = (resultStr.length / 8)
        } else {
            ByteArray(resultStr.length / 8 + 1)
            arrCount = (resultStr.length / 8 + 1)
        }

        var resultByte = ByteArray(arrCount)
        for (b in 0..arrCount-1){
            var sbArr:String
            if((b*8+8) > resultStr.length){
                sbArr = resultStr.substring((b*8))
            }else{
                sbArr = resultStr.substring((b*8),(b*8+8))
            }
            resultByte[b] = sbArr.toInt(2).toByte()
        }

        return resultByte
    }
6. 封装好上述流程
    /**
     * 哈夫曼压缩字符
     * @param someStr:需要被压缩的字符串
     *
     * @return 字符串被压缩过后的数组(比原字符串转化的数组长度短很多)
     * */
    fun huffmanZip(someStr: String):ByteArray{

        var dataByte:ByteArray = someStr.toByteArray()

        // 统计字符出现的次数以map形式保存结果,遍历map并生成节点放入list保存
        var nodes:ArrayList<Node> = createNodeList(dataByte)

        // 生成哈夫曼树
        var huffTree:Node = createNodeTree(nodes)

        // 生成哈夫曼编码对照表
        var huffCodeTable:HashMap<Byte,String> = createHuffCode(huffTree)

        // 对字符串进行编码
        var huffByte:ByteArray = createHuffByte(someStr, huffCodeTable)

        return huffByte
    }

运行结果


国际惯例

贴上完整源码

/**
 * 对字符串进行哈夫曼编码
 * @author liyongli 20190226
 * */
class HuffmanZipActivity : AppCompatActivity() {

    override fun onCreate(savedInstanceState: Bundle?) {
        super.onCreate(savedInstanceState)
        setContentView(R.layout.activity_huffman_zip)

        // 定义准备进行编码的字符串
        var someStr = " to be or not to be , thia's a question.  to be or not to be , thia's a question. "

        // 进行赫夫曼转码
        var huffCodeArr = huffmanZip(someStr)

        showNewTv.text = "哈夫曼编码后长度:" + huffCodeArr.size + "\n" + huffCodeArr.toList().toString()

        showOldTv.text = "哈夫曼编码前长度:" + someStr.toByteArray().size + "\n" + someStr.toByteArray().toList().toString()

    }

    /**
     * 哈夫曼压缩字符
     * @param someStr:需要被压缩的字符串
     *
     * @return 字符串被压缩过后的数组(比原字符串转化的数组长度短很多)
     * */
    fun huffmanZip(someStr: String):ByteArray{

        var dataByte:ByteArray = someStr.toByteArray()

        // 统计字符出现的次数以map形式保存结果,遍历map并生成节点放入list保存
        var nodes:ArrayList<Node> = createNodeList(dataByte)

        // 生成哈夫曼树
        var huffTree:Node = createNodeTree(nodes)

        // 生成哈夫曼编码对照表
        var huffCodeTable:HashMap<Byte,String> = createHuffCode(huffTree)

        // 对字符串进行编码
        var huffByte:ByteArray = createHuffByte(someStr, huffCodeTable)

        return huffByte
    }

    /**
     * 给数组中字符计数,并转为node集合
     * @param arr:由目标字符串转化的byte数组
     *
     * @return 由转换后的byte数组生成的节点集合
     * */
    fun createNodeList(arr:ByteArray):ArrayList<Node>{

        // HashMap 的 key 就是字符本身,value 为出现次数
        var arrMap:HashMap<Byte,Int> = HashMap()

        for(value in arr){

            var count = arrMap.get(value)
            
            // 次数不为空则继续叠加计数
            if(null != count){
                arrMap.put(value,count + 1)
            }else{
                arrMap.put(value, 1)
            }

        }

        var nodes:ArrayList<Node> = ArrayList()

        for((key,value) in arrMap){
            // Node 的 data 存储的就是字符本身,value 存储的是字符出现的次数,也是节点的权值
            nodes.add(Node(data = key, value = value))
        }

        return nodes
    }

    /**
     * 生成哈夫曼树
     * @param nodes: 待处理的节点集合
     *
     * @return 已构建完成的哈夫曼树
     * */
    fun createNodeTree(nodes: ArrayList<Node>): Node {

        while (nodes.size > 1){

            // 排序
            Collections.sort(nodes)

            // 整合
            var leftNode = nodes.get(nodes.size - 1)
            var rightNode = nodes.get(nodes.size - 2)
            var data = null
            var value = (nodes.get(nodes.size - 1).value!! + nodes.get(nodes.size - 2).value!!)
            var newNode = Node(leftNode = leftNode , data = data , value = value , rightNode = rightNode)

            // 删除
            nodes.remove(leftNode)
            nodes.remove(rightNode)

            // 添加
            nodes.add(newNode)
        }

        return nodes.get(0)
    }

    // 哈夫曼临时编码(路径)
    var huffLine:StringBuffer = StringBuffer()

    // 哈夫曼编码表
    var huffCodes:HashMap<Byte, String> = HashMap<Byte, String>()

    /**
     * 生成哈夫曼编码对照表
     * @param nodeTree: 哈夫曼树
     *
     * @return 已构建完成的哈夫曼编码对照表
     * */
    fun createHuffCode(nodeTree: Node): HashMap<Byte, String> {

        getLine(nodeTree.leftNode,"0",huffLine)

        getLine(nodeTree.rightNode,"1",huffLine)

        return huffCodes
    }

    /**
     * 递归拼接所有叶子节点路径(编码)
     * @param node:准备拼接路径的节点
     * @param code:路径值
     * @param huffLine:前一路径值
     * */
    fun getLine(node: Node?, code: String, huffLine: StringBuffer) {

        var huffLine = StringBuffer(huffLine)

        huffLine.append(code)

        if(null == node?.data){
            getLine(node?.leftNode,"0",huffLine)
            getLine(node?.rightNode,"1",huffLine)
        }else{
            huffCodes.put(node.data!!,huffLine.toString())
        }
    }

    /**
     * 对字符串进行哈夫曼编码
     * @param arr: 目标字符串
     * @param huffCodeTable: 编码对照表
     *
     * @return 已完成哈夫曼编码的字符串的byte数组
     * */
    fun createHuffByte(someStr:String , huffCodeTable: HashMap<Byte, String>): ByteArray {

        var strArr: ByteArray = someStr.toByteArray()

        var resultStr = StringBuffer()

        // 拼接编码结果
        for(b in strArr){
            resultStr.append(huffCodeTable.get(b))
        }

        // 以8位为一组对编码结果进行分组
        var arrCount = 0
        if (resultStr.length % 8 == 0) {
            ByteArray(resultStr.length / 8)
            arrCount = (resultStr.length / 8)
        } else {
            ByteArray(resultStr.length / 8 + 1)
            arrCount = (resultStr.length / 8 + 1)
        }

        var resultByte = ByteArray(arrCount)
        for (b in 0..arrCount-1){
            var sbArr:String
            if((b*8+8) > resultStr.length){
                sbArr = resultStr.substring((b*8))
            }else{
                sbArr = resultStr.substring((b*8),(b*8+8))
            }
            resultByte[b] = sbArr.toInt(2).toByte()
        }

        return resultByte
    }
}

本篇到此完结,更多Kotlin与数据结构原创内容持续更新中~

期待您点击关注或点击头像浏览更多移动端开发技术干货

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 当Kotlin遇见数据结构丨哈夫曼解码

    哈夫曼编码是一种编码格式,属于可变字长编码的一种,该方法依照字符出现的概率来构建异字头的平均长度最短的码字,最终实现根据使用频率来最大化节省码字(字符)的存储空...

    码脑
  • 当Kotlin遇见数据结构丨使用哈夫曼编码压缩文件

    哈夫曼编码是一种编码格式,属于可变字长编码的一种,该方法依照字符出现的概率来构建异字头的平均长度最短的码字,最终实现根据使用频率来最大化节省码字(字符)的存储空...

    码脑
  • 当Kotlin遇见数据结构丨使用哈夫曼编码解压文件

    哈夫曼编码是一种编码格式,属于可变字长编码的一种,该方法依照字符出现的概率来构建异字头的平均长度最短的码字,最终实现根据使用频率来最大化节省码字(字符)的存储空...

    码脑
  • js 常用技巧

    用户5927264
  • python 装饰器使用总结

    def wrapper_method1(func):# func用于接收被装饰的函数地址

    授客
  • 内存管理篇 (一):Go语言之逃逸

    汇编结果分析:通过汇编可以看出来,在mem.go中的fun()中的变量i是通过newobject(XX)来生成的数据,这就说明,这个i是存储在对中。

    灰子学技术
  • [!]The 'pods-xxx' target has libraries with conflicting name: libcrypto.a and libssl.a

    VV木公子
  • 大数据技术之_16_Scala学习_02_变量

    第二章 变量2.1 变量是程序的基本组成单位2.2 Scala 变量的介绍2.2.1 概念2.2.2 Scala 变量使用的基本步骤2.3 Scala 变量的基...

    黑泽君
  • 职业积累,试着比别人多走一步

    在职场上,经验的多少是衡量一个人价值的重要指标之一。所谓经验,简单地说就是大量占有信息,并在遇到问题时,从自己所知道或者所经历的事情里寻找相似的片段,作出最有效...

    用户1756920
  • 三分钟学 Go 语言——声明【变量】的各种方式

    大多数类型都是接触过的,比如c++的结构体,比如python的切片,java的接口,别看类型那么多以后写多了自然就会用了。

    机智的程序员小熊

扫码关注云+社区

领取腾讯云代金券