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