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

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

哈夫曼编码定义

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

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


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

相对于 Kotlin 中实现哈夫曼编码,解码的流程则简单很多:

1. 将待解码的 byte 数组转回二进制字符串
        // 存储byte数组转化来的二进制字符串,用以比较和替换哈夫曼编码
        var decodeResult = StringBuffer()

        // 将byte数组转化为二进制字符串
        for(count in 0..byteCodes.size - 1){

            var code = byteCodes[count]
            var flag = (count == byteCodes.size - 1)

            decodeResult.append(byteToBit(code,!flag))
        }
2. 将二进制字符串按照编码表解码,得出 ASCll 码数组
       // 调换哈夫曼编码表键值对,用以与二进制字符串进行比较和替换
        var codeMap:HashMap<String,Byte> = HashMap()
        for((tableKey,tableValue) in huffamCodeTable){
            codeMap.put(""+tableValue,tableKey)
        }

        // 存储解码后的byte数组
        var codeList = ArrayList<Byte>()

        // 比较开始位置
        var start = 0

        // 上次比较停止位置
        var end = start + 1

        for(len in 0..decodeResult.length-1){

            // 当字符串全部截取完毕后,停止循环
            if(end >= decodeResult.length-1){
                break
            }

            // 截取出来的字符为编码表的 key
            var key = ""
            // 根据 key 取到的对应 ASCII 码
            var value:Byte? = null
            // 截取停止标记
            var flag = true

            while (flag){

                // 循环截取二进制字符串
                key = decodeResult.substring(start,end)
                value = codeMap.get(key)

                // 判断截取内容是否是正确的 key , 是的话结束本次循环,不是的话结束标记向后移动继续截取 key
                if(null == value){
                    end += 1
                }else{
                    flag = false
                    start = end
                    end += 1
                }

            }

            // 存储取到的 ASCII 码
            codeList.add(value!!)
        }

        // 将全部 ASCII 码转为 Byte 数组并返回
        var byteArray = ByteArray(codeList.size)
        for(item in 0..codeList.size-1){
            byteArray[item] = codeList.get(item)
        }

最后得出的 byteArray 就是解码后的数组,使用 String(byteArray) 即可得到原字符串内容

附加高铁票: Kotlin 中实现哈夫曼编码,点我发车


运行结果


国际惯例

贴上 转码解码 完整源码

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

    // 编码对照表
    var huffCodeTable:HashMap<Byte,String> = HashMap()

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

        // 定义准备进行编码的字符串
        var someStr = "to be or not to be to be or not to be to be or not to be"

        // 进行赫夫曼转码
        var huffZipArr = huffmanZip(someStr)
        showNewTv.text = "内容编码后:" + huffZipArr.toList().toString()

        // 进行哈夫曼解码
        var huffDecodeArr = huffmanDecode(huffCodeTable,huffZipArr)
        showOldTv.text = "内容解码后:" + String(huffDecodeArr)

    }

    /**
     * 哈夫曼压缩字符
     * @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)

        // 生成哈夫曼编码对照表
        huffCodeTable = 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
    }

    /**
     * 哈夫曼编码解码
     * @param huffamCodeTable:指定的编码表
     * @param code:待解码byte数组
     *
     * @return 解码后的byte数组
     * */
    fun huffmanDecode(huffamCodeTable: HashMap<Byte, String>, byteCodes: ByteArray):ByteArray {

        // ① 将 byte 数组转回二进制字符串

        // 存储byte数组转化来的二进制字符串,用以比较和替换哈夫曼编码
        var decodeResult = StringBuffer()

        // 将byte数组转化为二进制字符串
        for(count in 0..byteCodes.size - 1){

            var code = byteCodes[count]
            var flag = (count == byteCodes.size - 1)

            decodeResult.append(byteToBit(code,!flag))
        }

        // ② 将二进制字符串按照编码表解码

        // 调换哈夫曼编码表键值对,用以与二进制字符串进行比较和替换
        var codeMap:HashMap<String,Byte> = HashMap()
        for((tableKey,tableValue) in huffamCodeTable){
            codeMap.put(""+tableValue,tableKey)
        }

        // 存储解码后的byte数组
        var codeList = ArrayList<Byte>()

        // 比较开始位置
        var start = 0

        // 上次比较停止位置
        var end = start + 1

        for(len in 0..decodeResult.length-1){

            // 当字符串全部截取完毕后,停止循环
            if(end >= decodeResult.length-1){
                break
            }

            // 截取出来的字符为编码表的 key
            var key = ""
            // 根据 key 取到的对应 ASCII 码
            var value:Byte? = null
            // 截取停止标记
            var flag = true

            while (flag){

                // 循环截取二进制字符串
                key = decodeResult.substring(start,end)
                value = codeMap.get(key)

                // 判断截取内容是否是正确的 key , 是的话结束本次循环,不是的话结束标记向后移动继续截取 key
                if(null == value){
                    end += 1
                }else{
                    flag = false
                    start = end
                    end += 1
                }

            }

            // 存储取到的 ASCII 码
            codeList.add(value!!)
        }

        // 将全部 ASCII 码转为 Byte 数组并返回
        var byteArray = ByteArray(codeList.size)
        for(item in 0..codeList.size-1){
            byteArray[item] = codeList.get(item)
        }

        return byteArray
    }

    /**
     * 将byte转为8位长度的二进制字符
     * @param bt:需要转化的byte字符
     * @param flag:是否截取为8位字符
     * */
    fun byteToBit(bt:Byte, flag:Boolean):String{
        if(flag){
            var temp = bt.toInt() or 256
            var str = Integer.toBinaryString(temp)
            return str.substring(str.length - 8)
        }else{
            return Integer.toBinaryString(bt.toInt())
        }
    }

}

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

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

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

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

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

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

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

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

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

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

    码脑
  • 对象储存cos-腾讯云对象储存cos

    COS是腾讯云提供的对象存储服务,功能非常强大,可以作为文件服务器,CDN加速,静态网页服务,还提供了图片的常用操作。

    张天华
  • 腾讯云对象储存cos的配置方法简单说明

    COS是腾讯云提供的对象存储服务,功能非常强大,可以作为文件服务器,CDN加速,静态网页服务,还提供了图片的常用操作。相关API文档:https://cloud...

    主机优惠教程
  • Linux Shell 中的 ()、(())、[]、[[]]、{} 怎么用是不是还傻傻分不清?

    ①命令组。括号中的命令将会新开一个子shell顺序执行,所以括号中的变量不能够被脚本余下的部分使用。括号中多个命令之间用分号隔开,最后一个命令可以没有分号,各命...

    昱良
  • 发现一个很N且免费的html5拓扑图 关系图 生成组件

    旺财的城堡
  • 小程序快速封装函数以便公共调用

    最近的那个项目,因为多处记录功能需要写入存储时间,如果每个页面都写一次会使得代码太臃肿,所以我们使用封装函数调用。

    许坏
  • 基础知识 | 每日一练(101)

    士人有百折不回之真心,才有万变不穷之妙用。立业建功,事事要从实地着脚,若少慕声闻,便成伪果;讲道修德,念念要从虚处立基,若稍计功效,便落尘情。 ...

    闫小林

扫码关注云+社区

领取腾讯云代金券