专栏首页大前端当Kotlin遇见数据结构丨使用哈夫曼编码压缩文件

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

哈夫曼编码定义

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

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


Kotlin 中如何实现哈夫曼压缩文件

1. 获取待压缩文件对象,调用哈夫曼压缩算法
        // 获取文件输入流对象
        var fileInputStream = File(filePath).inputStream()
        var imageBytes = fileInputStream.readBytes()

        // 开始压缩文件
        var huffZipUtil = HuffmanZipUtils()
        var huffBytes = huffZipUtil.huffmanZip(imageBytes)
2. 将压缩后的对象以及编码对照表,以 .zip 形式保存至本地
        // 保存压缩包
        var saveOutputStream = File(savePath).outputStream()
        var saveObjectOutputStream = ObjectOutputStream(saveOutputStream)

        saveObjectOutputStream.writeObject(huffBytes)
        saveObjectOutputStream.writeObject(huffZipUtil.huffCodeTable)

运行结果


国际惯例

贴上完整源码

HuffmanZipFileActivity.kt
/**
 * 使用哈夫曼编码压缩文件
 * @author liyongli 20190305
 * */
class HuffmanZipFileActivity : AppCompatActivity() {

    // 获取根目录路径
    var sdPath = getSDPath()

    // 存储文件夹位置
    var myFolder = "$sdPath/KotlinAndDataStructure"

    // 原文件路径
    var testFilePath = "$myFolder/compress.txt"

    // 压缩包路径
    var zipFilePath = "$myFolder/compressPackage.zip"

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

        // 压缩文件
        fileZip(testFilePath, zipFilePath)
    }

    /**
     * 压缩文件
     *
     * @param filePath : 目标文件路径
     * @param savePath : 压缩包存储路径
     * */
    fun fileZip(filePath:String,savePath:String){

        // 获取文件输入流对象
        var fileInputStream = File(filePath).inputStream()
        var imageBytes = fileInputStream.readBytes()

        // 开始压缩文件
        var huffZipUtil = HuffmanZipUtils()
        var huffBytes = huffZipUtil.huffmanZip(imageBytes)

        // 保存压缩包
        var saveOutputStream = File(savePath).outputStream()
        var saveObjectOutputStream = ObjectOutputStream(saveOutputStream)

        saveObjectOutputStream.writeObject(huffBytes)
        saveObjectOutputStream.writeObject(huffZipUtil.huffCodeTable)

        // 关闭输入、输出流
        saveOutputStream.close()
        saveObjectOutputStream.close()
        fileInputStream.close()
    }


    /**
     * 获取手机根目录
     *
     * @return SD 卡根目录路径
     * */
    fun getSDPath():String?{

        // 判断 SDcard 是否可用
        if(!(Environment.MEDIA_MOUNTED.equals(Environment.getExternalStorageState()))){
            return null
        }

        // 使用 shall 命令获取(获取失败则在最后更换为普通方式再次获取)
        var cmd = "cat /proc/mounts"
        var run = Runtime.getRuntime()
        var br:BufferedReader? = null
        try {
            var process = run.exec(cmd)
            br = BufferedReader(InputStreamReader(BufferedInputStream(process.inputStream)))
            var line = ""
            var flag = true
            while (flag) {
                line = br.readLine()
                if(null != line){
                    if(line.contains("sdcard") && line.contains("android_secure")){
                        var strArr = line.split(" ")
                        if(strArr.size >= 5){
                            flag = false
                            return strArr[1].replace("/.android_secure", "") + File.separator;
                        }
                        if (process.waitFor() != 0 && process.exitValue() == 1) {
                            break
                        }
                    }
                }
            }
        }catch (e:Exception){
            e.printStackTrace()
        } finally {
            br?.close()
        }

        // 使用普通方法获取
        return Environment.getExternalStorageDirectory().path + File.separator
    }
}
HuffmanZipUtils.kt
    // 编码对照表
    var huffCodeTable:HashMap<Byte,String> = HashMap()

    /**
     * 哈夫曼压缩
     * @param someArr:目标数组
     *
     * @return 被压缩后的数组
     * */
    fun huffmanZip(someArr:ByteArray):ByteArray{

        var dataByte:ByteArray = someArr

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

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

        // 生成哈夫曼编码对照表
        huffCodeTable = createHuffCode(huffTree)

        // 对数组进行编码
        var huffByte:ByteArray = createHuffByte(someArr, 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 someArr: 目标数组
     * @param huffCodeTable: 编码对照表
     *
     * @return 已完成哈夫曼编码的byte数组
     * */
    fun createHuffByte(someArr:ByteArray , huffCodeTable: HashMap<Byte, String>): ByteArray {

        var strArr: ByteArray = someArr

        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遇见数据结构丨哈夫曼编码

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

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

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

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

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

    主机优惠教程
  • Java11震撼发布了,我们该怎么办?

    Java11已经发布了,我们今天聊聊大家还停留在哪个版本呢?大家对于新版本的迅速的发布有什么想说的呢?

    好好学java
  • Linux Shell 中的 ()、(())、[]、[[]]、{} 怎么用是不是还傻傻分不清?

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

    昱良
  • SEO的html劫持和html劫持代码

    这段时间有个人问我SEO的html劫持是怎么做的,代码又是什么样子的,然后就有了这篇文章。大家可以看看,学习一下。

    开心分享
  • 当Kotlin遇见数据结构丨哈夫曼解码

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

    码脑
  • Ramda 函数库参考教程

    学习函数式编程的过程中,我接触到了 Ramda.js。 我发现,这是一个很重要的库,提供了许多有用的方法,每个 JavaScript 程序员都应该掌握这个工具。...

    ruanyf

扫码关注云+社区

领取腾讯云代金券