当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与数据结构原创内容持续更新中~

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