哈夫曼编码定义
哈夫曼编码是一种编码格式，属于可变字长编码的一种，该方法依照字符出现的概率来构建异字头的平均长度最短的码字，最终实现根据使用频率来最大化节省码字（字符）的存储空间和提高传输效率的目的，在数据压缩和通讯领域应用的非常广泛。
哈夫曼编码的码字是异前置码字，任一码字不会是另一码字的前面部分，这样各种码字可以连在一起传输，中间无需空格分离但又不会混淆。
Kotlin 中对字符串进行哈夫曼转码
对一串字符进行哈夫曼编码可分为五个流程：
1. 统计字符出现的次数，使用 HashMap 集合存储统计结果
// 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)
}
}
2. 遍历 HashMap 内容转化为二叉树的节点 Node ，使用 ArrayList 集合存储所有 Node
var nodes:ArrayList<Node> = ArrayList()
for((key,value) in arrMap){
// Node 的 data 存储的就是字符本身，value 存储的是字符出现的次数，也是节点的权值
nodes.add(Node(data = key, value = value))
}
3. 以存储所有 Node 的 ArrayList 为源数据，构建哈夫曼树
/**
* 生成哈夫曼树
* @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)
}
4. 生成哈夫曼编码表，也就是生成由根节点到达不同叶子结点所需路径的集合
// 哈夫曼临时编码（路径）
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())
}
}
5. 根据生成的编码表对字符串进行哈夫曼编码
/**
* 对字符串进行哈夫曼编码
* @param arr: 目标字符串
* @param huffCodeTable: 编码对照表
*
* @return 已完成哈夫曼编码的字符串的byte数组
* */
fun createHuffByte(someStr:String , huffCodeTable: HashMap<Byte, String>): ByteArray {
var strArr: ByteArray = someStr.toByteArray()
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
}
6. 封装好上述流程
/**
* 哈夫曼压缩字符
* @param someStr:需要被压缩的字符串
*
* @return 字符串被压缩过后的数组（比原字符串转化的数组长度短很多）
* */
fun huffmanZip(someStr: String):ByteArray{
var dataByte:ByteArray = someStr.toByteArray()
// 统计字符出现的次数以map形式保存结果，遍历map并生成节点放入list保存
var nodes:ArrayList<Node> = createNodeList(dataByte)
// 生成哈夫曼树
var huffTree:Node = createNodeTree(nodes)
// 生成哈夫曼编码对照表
var huffCodeTable:HashMap<Byte,String> = createHuffCode(huffTree)
// 对字符串进行编码
var huffByte:ByteArray = createHuffByte(someStr, huffCodeTable)
return huffByte
}
运行结果
国际惯例
贴上完整源码
/**
* 对字符串进行哈夫曼编码
* @author liyongli 20190226
* */
class HuffmanZipActivity : AppCompatActivity() {
override fun onCreate(savedInstanceState: Bundle?) {
super.onCreate(savedInstanceState)
setContentView(R.layout.activity_huffman_zip)
// 定义准备进行编码的字符串
var someStr = " to be or not to be , thia's a question. to be or not to be , thia's a question. "
// 进行赫夫曼转码
var huffCodeArr = huffmanZip(someStr)
showNewTv.text = "哈夫曼编码后长度：" + huffCodeArr.size + "\n" + huffCodeArr.toList().toString()
showOldTv.text = "哈夫曼编码前长度：" + someStr.toByteArray().size + "\n" + someStr.toByteArray().toList().toString()
}
/**
* 哈夫曼压缩字符
* @param someStr:需要被压缩的字符串
*
* @return 字符串被压缩过后的数组（比原字符串转化的数组长度短很多）
* */
fun huffmanZip(someStr: String):ByteArray{
var dataByte:ByteArray = someStr.toByteArray()
// 统计字符出现的次数以map形式保存结果，遍历map并生成节点放入list保存
var nodes:ArrayList<Node> = createNodeList(dataByte)
// 生成哈夫曼树
var huffTree:Node = createNodeTree(nodes)
// 生成哈夫曼编码对照表
var huffCodeTable:HashMap<Byte,String> = createHuffCode(huffTree)
// 对字符串进行编码
var huffByte:ByteArray = createHuffByte(someStr, 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 arr: 目标字符串
* @param huffCodeTable: 编码对照表
*
* @return 已完成哈夫曼编码的字符串的byte数组
* */
fun createHuffByte(someStr:String , huffCodeTable: HashMap<Byte, String>): ByteArray {
var strArr: ByteArray = someStr.toByteArray()
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与数据结构原创内容持续更新中~
期待您点击关注或点击头像浏览更多移动端开发技术干货！
