哈夫曼编码定义
哈夫曼编码是一种编码格式，属于可变字长编码的一种，该方法依照字符出现的概率来构建异字头的平均长度最短的码字，最终实现根据使用频率来最大化节省码字（字符）的存储空间和提高传输效率的目的，在数据压缩和通讯领域应用的非常广泛。
哈夫曼编码的码字是异前置码字，任一码字不会是另一码字的前面部分，这样各种码字可以连在一起传输，中间无需空格分离但又不会混淆。
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与数据结构原创内容持续更新中~
期待您点击关注或点击头像浏览更多移动端开发技术干货！
网友评论