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

哈夫曼编码定义

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

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


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

1. 获取待解压文件对象,调用哈夫曼解压算法
        // 获取文件输入流对象
        var saveInputStream = File(zipPath).inputStream()
        var saveObjectInputStream = ObjectInputStream(saveInputStream)

        // 读取哈夫曼码数组
        var imageBytes:ByteArray = saveObjectInputStream.readObject() as ByteArray
        // 读取哈夫曼编码变
        var huffCodeTable:HashMap<Byte,String> = saveObjectInputStream.readObject() as HashMap<Byte,String>

        // 开始解压压缩包
        var huffZipUtil = HuffmanZipUtils()
        var objectBytes = huffZipUtil.huffmanDecode(huffCodeTable, imageBytes)
2. 将解压后的对象保存至本地
        // 保存解压后的文件
        var saveOutputStream = File(savePath).outputStream()
        saveOutputStream.write(objectBytes)

运行结果


国际惯例

贴上完整源码

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

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

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

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

    // 解压文件路径
    var saveFilePath = "$myFolder/deCompress.txt"

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

        // 解压文件
        fileUnZip(zipFilePath,saveFilePath)
    }

    /**
     * 解压文件
     *
     * @param zipPath : 压缩包路径
     * @param savePath : 解压后文件存储路径
     * */
    fun fileUnZip(zipPath:String,savePath:String){

        // 获取文件输入流对象
        var saveInputStream = File(zipPath).inputStream()
        var saveObjectInputStream = ObjectInputStream(saveInputStream)

        // 读取哈夫曼码数组
        var imageBytes:ByteArray = saveObjectInputStream.readObject() as ByteArray
        // 读取哈夫曼编码变
        var huffCodeTable:HashMap<Byte,String> = saveObjectInputStream.readObject() as HashMap<Byte,String>

        // 开始解压压缩包
        var huffZipUtil = HuffmanZipUtils()
        var objectBytes = huffZipUtil.huffmanDecode(huffCodeTable, imageBytes)

        // 保存解压后的文件
        var saveOutputStream = File(savePath).outputStream()
        saveOutputStream.write(objectBytes)

        // 关闭输入、输出流
        saveOutputStream.close()
        saveObjectInputStream.close()
        saveInputStream.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
    /**
     * 哈夫曼编码解码
     * @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){

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

            while (flag){

                // 循环截取二进制字符串
                if(end > decodeResult.length-1){
                    key = decodeResult.substring(start)
                    flag = false
                }else{
                    key = decodeResult.substring(start,end)
                }

                value = codeMap.get(key)

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

            }

            if(null == value){
                break
            }else{
                // 存储取到的 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的延迟初始化: lateinit var和by lazy

可是有的时候,我并不想声明一个类型可空的对象,而且我也没办法在对象一声明的时候就为它初始化,那么这时就需要用到Kotlin提供的延迟初始化。Kotlin中有两种...

19310
来自专栏Android技术分享

Android 必须知道2019年流行的框架库及开发语言,看这一篇就够了!

Universal-Image-Loader,早期广泛被用的一个可重复使用的仪器为异步图像加载、缓存、显示。作者已经停止维护。

1.1K70
来自专栏大前端

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

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

10710
来自专栏Android 技术栈

Kotlin | 2.Kotlin基础

在定义了val变量的代码块执行期间,val变量只能进行唯一一次初始化。但是,如果编译器能确保只有唯一一条初始化语句被执行,可以根据条件使用不同的值来初始化它:

9020
来自专栏大前端

当Kotlin遇见数据结构丨实现链式存储的二叉树并遍历

简单二叉树的创建分为三部分: 新建节点、新建树、给节点和树赋值并关联,下面进入编码阶段:

10620
来自专栏Android技术分享

熬过了互联网“寒冬”,接下来的金三银四你该怎么面试进BAT?

又要交房租了,工资怎么还不发?每个月总觉得钱不够花,工资总是跟不上消费,什么时候能涨个工资呢?

8920
来自专栏Android相关

Kotlin---泛型

Kotlin的不变型泛型和Java一样,通过声明泛型类型来使用泛型类。而该种泛型声明后,则无法使用父类方法与属性。在编译时候,会将泛型擦除。

17030
来自专栏Android技术分享

Android之调节屏幕亮度(文末附源码)

在使用微信或者支付宝的付款码支付时,如果你点击放大付款码,就会跳转到一个新的页面去显示大尺寸的付款码,而且你会发现屏幕变亮了,这样会便于扫码机识别你的付款码。当...

23920
来自专栏Android 技术栈

Kotlin | 1.定义和目的

11520

扫码关注云+社区

领取腾讯云代金券

年度创作总结 领取年终奖励