哈夫曼树与编码

一、哈夫曼树

定义:

给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman
Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

例:在数据通信中,需要将传送的文字转换成二进制的字符串,用0,1码的不同排列来表示字符。例如,需传送的报文为“AFTER DATA EAR ARE ART AREA”,这里用到的字符集为“A,E,R,T,F,D”,各字母出现的次数为{8,4,5,3,1,1}。现要求为这些字母设计编码。要区别6个字母,最简单的二进制编码方式是等长编码,固定采用3位二进制,可分别用000、001、010、011、100、101对“A,E,R,T,F,D”进行编码发送,当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。

二、哈夫曼树创建方法

摘自:《详细图解哈夫曼Huffman编码树》

2.1 初始队列

  我们按出现频率高低将其放入一个优先级队列中,从左到右依次为频率逐渐增加。
 
在这里插入图片描述

  下面我们需要将这个队列转换成哈夫曼二叉树,哈夫曼二叉树是一颗带权重的二叉树,权重是由队列中每个字符出现的次数所决定的。并且哈夫曼二叉树始终保证权重越大的字符出现在越高的地方。

2.2 第一步合并

  首先我们从左到右进行合并,依次构建二叉树。第一步取前两个字符u和r来构造初始二叉树,第一个字符作为左节点,第二个元素作为右节点,然后两个元素相加作为新空元素,并且两者权重相加作为新元素的权重。
  
在这里插入图片描述

  同理,新元素可以和字符i再合并,如下:

在这里插入图片描述

2.3 重新调整队列

  上图新元素权重相加后结果是变大了,需要对权重进行重新排序。
  
在这里插入图片描述

  然后再依次从左到右合并,每合并一次则进行一次队列重新排序调整。如下:

在这里插入图片描述

  经过多步操作之后,得到以下的哈夫曼二叉树结构,也就是一个带有权重的二叉树:

在这里插入图片描述

2.4 哈夫曼编码

  有了上面带权重的二叉树之后,我们就可以进行编码了。我们把二叉树分支中左边的支路编码为0,右边分支表示为1,如下图:  

在这里插入图片描述

  这样依次遍历这颗二叉树就可以获取得到所有字符的编码了。例如:‘ ’的编码为10,‘l’的编码为00,‘u’的编码为11100等等。经过这个编码设置之后我们可以发现,出现频率越高的字符越会在上层,这样它的编码越短;出现频率越低的字符越会在下层,编码越短。经过这样的设计,最终整个文本存储空间才会最大化的缩减。
  最终我们可以得到下面这张编码表:
在这里插入图片描述

2.5 字符串编码

  有了上面的编码表之后,”we will we will r u”这句重新进行编码就可以得到很大的压缩,编码表示为:01 110 10 01 1111 00 00 10 01 110 10 01 1111 00 00 10 11101 10 11100。这样最终我们只需50位内存,比原ASCII码表示节约了2/3空间,效果还是很理想的。当然现实中不是简单这样表示的,还需要考虑很多问题。

三、哈夫曼编码的压缩与解压

1、使用IO流逐字节读取文档。用一个数组(0~255,下标表示ASCII码)来保存不同字符出现的次数
2、建一个节点类,保存节点对象的信息。将数组每一位表示的字符和出现频次存入创建的节点,把所有节点存入一个链表。
3、根据节点存储的频次值,对链表进行从小到大排序
4、从链表中取出并删除最小的两个节点,创建一个他们的父节点,父节点不存字符,值为那两个节点的和,把那两个节点分别作为其左子节点和右子节点,最后把这个父节点存入链表。再次排序,取出并删除最小的两个节点,生成父节点,再存入…以此类推,最终生成一棵哈夫曼树。
5、对哈夫曼树进行遍历,使得叶子结点获得相应编码,同时把字符和它对应的哈夫曼编码存入HashMap

四、疑问

4.1对于字符频率相等的情况

我们在构建哈夫曼树的时候在想,如果我们的字符出现的频率相等的情况,那哈夫曼树岂不是很糟?
我们假设原来字符串长度为N,那么对于普通的ASCII编码得到的长度为8N,如果利用哈夫曼编码,对于每一个字符,最大的长度不会超过8层树因为ASCII编码总共只有2^8个字符,也就是说最极端的情况:一个文件中所有字符串中出现256个字符且重复次数是一样的,但这仍然对原来的文本有进行过压缩(毕竟出现次数相等的话,构造的哈夫曼树在8层之前还是有数据的,那些数据的位数<8)最终的编码数一定是会<8N

4.2解码冲突问题

我们在解压遍历哈夫曼的时候,最终的编码不会冲突么?举例:上面我们得到得最终的编码是
01 110 10 01 1111 00 00 10 01 110 10 01 1111 00 00 10 11101 10 11100但是在实际的压缩中我们不会有分隔符最终的情况将会是:
0111010 0111110000100111010011111000010111011011100
于是我们怎么知道:前面的01是一个编码,为什那么0111就是一个编码呢?也就是说01是0111的前缀 。其实我们从这张图就能看出来:对于上述的字符串一定不会存在一个叫0111的编码,因为“w”字母代表的01已经没有子节点。其实中也可以看出一些区域是空着的比如:11、111、111、1110 没有数据,其实这都是满足了哈夫曼树的 左起字串不冲突原则

在这里插入图片描述

想统计自己总共提交了多少行代码?

作为一名程序员,我们很想知道自己到底提交了多少行代码到远程仓库,有没有什么工具能够帮我们统计自己写过的代码行数呢?答案是有的。这是本次博文的最终效果。
在这里插入图片描述

对于代码提交行数统计,通过git 的系统命令就能做到,如下代码所示

1
2
git log --author='username' --pretty=tformat: --numstat | awk '
{add += $1; subs += $2; loc += $1 - $2 } END { printf "添加了%s,删除了%s,合计%s\n", add, subs, loc }' -

只需要在如下命令输入自己的username就行了,效果如图所示·
在这里插入图片描述

但是有的人由于环境原因,为了区分一些环境,比如办公司叫:username.office 在家的电脑上叫做: user.home 诸如此类,难道得手动一个一个统计么?当然不行了。

众所周知,由于工程项目变得更越来越大,拆库也说见不鲜,于是自己的代码分布不同的项目工程,我们想要利用git的统计命令的话就有点吃力了,需要一个一个地进入相应目录进行命令输入?当然不行了。

今天自己写了一份脚本主要用于统计分布在某个文件夹下所有的代码提交行数,git开源地址:https://github.com/VomPom/ForFun源码如下

如何使用?

0、将自己需要统计的项目文件目录整理到一个文件夹

1、讲users_name换成自己的的用户名

2、由于文件夹下可能有一些例外的不需要统计,添加该文件夹名

3、讲该shell脚本移动到某个名录下

4、最后利用 sh codeLine.sh 执行命令

在这里插入图片描述

在这里插入图片描述

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
########################################################
#
# Created by https://julis.wang on 2020/02/28
#
# Description : 统计代码提交行数
#
########################################################

#!/bin/bash

#这里添加你的git常用用户名。考虑到每个人的账号可能有很多个,所以定义成数组
users_name=("julis" "julis.wang" "julis.wang.hp")

#过滤一些不需要去遍历的文件夹
filter_path=("Backend" "test" "sdk" "fork" "ArProject")




########################################################
# 以下代码不需动
########################################################

export index=0 #记录当前的位置
export add_line_count=0 #添加的line总行数
export remove_line_count=0 #删除的总行数

export array_git_repositories=() #用于记录仓库名
export add_code=() #记录所有用户对某个库的添加的行数
export remove_code=() #记录所有用户对某个库的删除的行数

#判断是否需要过滤该目录
function is_fileter_dir() {
for i in "${!filter_path[@]}"; do
if [ $1 == "${filter_path[$i]}" ]; then
return 1
fi
done
return 0
}
#对命令执行的返回值进行数据切割
function get_add_remove_count() {
string=$1
array=(${string//,/ })
if [ ! ${array[0]} ]; then
add_line=0
else
add_line=${array[0]}
fi

if [ ! ${array[1]} ]; then
remove_line=0
else
remove_line=${array[1]}
fi

if [ ! ${add_code[$index]} ]; then
add_code[$index]=0

fi
if [ ! ${remove_code[$index]} ]; then
remove_code[$index]=0

fi
remove_code[$index]=`expr ${remove_code[$index]} + $remove_line`
add_code[$index]=`expr ${add_code[$index]} + $add_line`

echo "用户"$2"添加了="$add_line"行 删除了"$add_line"行"

}
#获取该用户在该文件夹下的提交代码数
function get_user_line() {
# output分别去接收 该文件夹下的提交以及删除行数
output=$(git log --author=${1} --pretty=tformat: --numstat | awk '
{add += $1; subs += $2; loc += $1 - $2 } END { printf "添加了%s,删除了%s,合计%s\n", add, subs, loc }' -)
get_add_remove_count $output ${1}
}

#遍历每个用户名
function trans_every_user() {
for i in "${!users_name[@]}"; do
get_user_line "${users_name[$i]}"
done
cd ..
}

# 整体流程,从文件夹出发
for path in `ls -l $(dirname $0)|awk -F " " '{print $9}'`
do
if [ -d $path ]
then
is_fileter_dir $path
if [ $? == 1 ]
then
echo "<=========过滤了【"$path"】======>"
else
echo "<=========获取【"$path"】的Git代码提交数据======>"
index=${#array_git_repositories[@]} #用于记录当前在第几个文件夹下处理
array_git_repositories=(${array_git_repositories[@]} $path)

cd $path
trans_every_user
fi
fi
done
all_add_line=0
all_remove_line=0
echo '==============================================================================='
echo " 本次共统计了【"${#array_git_repositories[@]}"】个仓库 by julis.wang "
echo '==============================================================================='
printf "%-30s %10s %10s %10s\n" "Folder" "Add" "Remove" "All"
echo '-------------------------------------------------------------------------------'
for ((i=0;i<${#array_git_repositories[@]};i++))
do
all_add_line=`expr $all_add_line + ${add_code[$i]}`
all_remove_line=`expr $all_remove_line + ${remove_code[$i]}`
printf "%-30s %10s %10s %10s\n" ${array_git_repositories[$i]} ${add_code[$i]} ${remove_code[$i]} `expr ${add_code[$i]} - ${remove_code[$i]}`
done
echo '-------------------------------------------------------------------------------'
printf "%-30s %10s %10s %10s\n" "Total" $all_add_line $all_remove_line `expr $all_add_line - $all_remove_line`
echo '==============================================================================='

写在最后:
由于本人不太擅长编写shell脚本,所有其中的代码实现方式可能比较粗糙,望理解。

Java反射中getGenericInterfaces和getInterfaces的解读

今天在做解析网络请求后得到的数据的转化的时候用到了:getGenericInterfaces这个方法。

 /**
  * 获取回调接口中 T 的具体类型
  *
  * @param clazz
  * @return
  */
   public static Type getTType(Class clazz) {
    //以Type的形式返回本类直接实现的接口.
    Type[] types = clazz.getGenericInterfaces();
    if (types.length > 0) {
        //返回表示此类型实际类型参数的 Type 对象的数组
        Type[] interfacesTypes = ((ParameterizedType) types[0]).getActualTypeArguments();
        return interfacesTypes[0];
    }
    return null;
}

其中回调接口为:

new RequestListener>() {
   @Override
    public void onSuccess(List result) {}

在解析数据的时候这样操作,目的是为了对所有返回的数据进行数据转化为所指定的类型:

Type type = getTType(requestListener.getClass());
     //泛型是实体或者List等类型
     T t = JsonUtils.fromJson(resultString, type);
     requestListener.onSuccess(t);`

类RequestListener为:

public interface RequestListener {
    void onSuccess(T result);
    void onError(Exception e);
}

使用Gson进行json的解析,T fromJson(String json, Type typeOfT);那么怎么才能获取到RequestListener中的的类型呢?
于是我们从接口获取参数化类型处理。

官方文档解释

getGenericInterfaces:

Returns the {@code Type}s representing the interfaces directly implemented by the class or interface represented by this object.释意:返回表示由此对象表示的类或接口直接实现的接口的{@code Type}。

getInterfaces:

Determines the interfaces implemented by the class or interface represented by this object.
释意:返回由此对象表示的类或接口实现的接口。

从解释上面来看出来了,差异在于“接口实现的接口的Type”,接下来用具体示例来解释区别

private class Food{
    String foodName;
}
private interface Eat{
    void eat(String things);
}
private interface Run{
    void run();
}
private class Dog implements Eat,Run{
    @Override
    public void run() { }
    @Override
    public void eat(String things) { }
}
private void main() {
    Class clazz = Dog.class;
    Type[] genericInterfaces = clazz.getGenericInterfaces();
    Class[] interfaces = clazz.getInterfaces();
}
运行结果
![](https://oscimg.oschina.net/oscnet/245442107557694aef0f07c25be0740187c.jpg)

我们可以看到,clazz.getGenericInterfaces()与clazz.getInterfaces()并没有任何差异。因为 并没有:“实现的接口的Type”

接下来看另一段代码,我们对Eat接口改造一下,增加一个参数化类型

private class Food{
    String foodName;
}
private interface Eat{
    void eat(T things);
}
private interface Run{
    void run();
}

private class Dog implements Eat,Run{
    @Override
    public void run() { }
    @Override
    public void eat(Food things) { }
}
private void main() {
    Class clazz = Dog.class;
    Type[] genericInterfaces = clazz.getGenericInterfaces();
    Class[] interfaces = clazz.getInterfaces();
}
运行结果:

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×