数据在计算机中的表现形式

在计算机中所有的数据都是以二进制的形式存储的。

先使用C语言去读取一个视频文件：如下，该视频是某动漫的MP4文件，位置在 D:\c 。

下面是代码：代码中以二进制的形式去读取该文件。

#include<stdio.h>
#include<stdlib.h>
int main(void){
	FILE *fp; //定义一个文件指针。
	
	char *charPoint; 
	//定义一个字符型的指针，用于指向字符数据，一个字符占一个字节，8位。计算机能够处理的最小数据类型就是一个字节byte。
	if((charPoint = (char*)calloc(210406885, 1))==NULL){
	//使用calloc函数申请内存，calloc函数的声明在 stdlib.h 头文件中。
	//该视频文件是210406880个字节，所以申请210406885个单位为1字节的空间，多申请5个字节防止内存溢出。
	//将申请后得到的内存类型强制转换成char型，然后将申请的这块内存的首地址赋值给字符指针。
		printf("Not able to allocate memory.\n");     //如果申请的内存首地址 等于 NULL 空（值为0），则打印错误信息。
		exit(0);     //退出程序，exit()函数的声明在头文件 stdlib.h 中
	} 
	
	//文件打开 
	if((fp = fopen("D:\\c\\画江湖之灵主21集.mp4","rb"))==NULL){
	// "rb" 以二进制的形式读取
	// 文件所在的地址，反斜杠需要用双反斜杠 \\ 转义
	//如果视频文件的地址和该C语言代码的源文件在同一个文件目录下，可以不用详细地址，直接使用视频的文件名。
		printf("File open error!\n");  //如果文件指针fp 等于 NULL 空，说明文件打开失败，打印失败信息。如果不打印，万一出错，你就不知道程序哪里出了问题
		exit(0);
	}
	
	fread(charPoint, 1, 1000, fp);
	//fread 函数读取数据，从fp文件指针中读取1000个单位为1字节的数据到charPoint字符型指针中。
	//由于视频文件太大，这里只读取1000个字节
	
	for(int i = 0; i < 1000; i++){
		printf("%d ", *(charPoint+i));    //以%d整型数据的形式打印出来
	}
	
	fclose(fp);     //关闭文件指针
	free(charPoint);     //释放申请的内存资源
	
	return 0;
}

最后读取的结果如下：

因为是以二进制的数据读取，读到的内容再以整型数据的形式输出，所以就得到了这样的结果，有正数也有负数。下面我们手动转换以下，把前面几个数还原成二进制形式：
105 转换成二进制是 0110 1001
19 转换成二进制是 0001 0011
-67 转换成二进制有点麻烦，先将67转换成二进制，得到 100 0011，然后再填充到8位的字符型数据中，因为是有符号的字符型，最高位为 0 代表正数，1 代表负数，这里-67为负数，所以是 1100 0011。而计算机中负数以补码的形式存储，所以这里还要将 1100 0011 转换成补码，转换规则是 最高位即符号位不变，其他位取反 1011 1100，然后再加一，于是得到 1011 1101 即-67在计算机中的二进制形式。
-100 二进制：1001 1100
后面的数依此类推。

所以我们可以知道这个二进制的视频文件在计算机中的二进制数据流大概长下面这个样子：
0110 1001 0001 0011 1011 1101 1001 1100 .... .... .... .... .... ....

为了不考虑正负号，可以把 char 定义为无符号型的，即 unsigned char ：

unsigned char *charPoint; 
if((charPoint = (unsigned char*)calloc(210406885, 1))==NULL){

最后打印的结果为：

这样每一个字节的值就是 0~255 中的某一个值。

下面我们将读取视频的二进制数据以十六进制的形式输出：
十六进制逢16进1，十六进制的一位正好对应二进制的四位如下：
0000 ~ 0
0001 ~ 1
0010 ~ 2
0011 ~ 3
0100 ~ 4
0101 ~ 5
0110 ~ 6
0111 ~ 7
1000 ~ 8
1001 ~ 9
1010 ~ a
1011 ~ b
1100 ~ c
1101 ~ d
1110 ~ e
1111 ~ f ，共16种状态。
一个字节占8位，前4位后4位，一共就有 $16\times 16=256$ 种状态，正好对应 0000 0000 (0) ~ 1111 1111 (255)。
这样可以用 switch 语句写 256 个分支，来对应这256个状态，但是手动写的话肯定会非常麻烦，所以我写了一个 python 程序，这个程序自动帮我生成C语言的 switch 语句：（因为这个switch语句是有规律可循的，如果我手动去写，要写很多重复代码，所以我要写一个程序，然后让这个程序去自动帮我写代码。任何有规律可循的东西，都可以用程序去简化过程。其实不一定就用python，也可以用C语言或者Java，使用python主要是因为它的语法简单。）

tab = "    "   # 定义一个tab，即4个空格

li = ['0','1','2','3','4','5','6','7','8','9','a','b','c','d','e','f']    # 十六进制的数字总共16个

with open("switch.txt", "w") as fiob:    # 打开一个switch.txt文本文件
    fiob.write(tab+"switch(){\n")     # 先写一个switch开头
    a = 0    # 这个 a 就是 0~255个数，初值为0，for循环中会给它自动加1
    for i in li:
        for j in li:    # 两层for循环，16*16=256
            fiob.write(tab*2 + "case " + str(a) + ":\n" + tab * 3 + "chs[0]=\'" + i + "\';\n" + tab * 3 + "chs[1]=\'" + j + "\';\n" + tab * 3 + "chs[2]=0;\n" + tab * 3 + "break;\n")
            # 写入有规律的语句
            a += 1   # a自动加1，然后进入下一次循环

运行这个python程序，会生成一个 switch.txt 的文本文件，里面就是想要的C语言 switch 代码，最后再和上面的C语言代码整合一下：

#include<stdio.h>
#include<stdlib.h>

char* trans(unsigned char ch);     //用这个函数进行二进制到十六进制的转换

int main(void){
	FILE *fp;
	
	unsigned char *charPoint;
	if((charPoint = (unsigned char*)calloc(210406885, 1))==NULL){
		printf("Not able to allocate memory.\n");
		exit(0);
	} 
	
	//文件打开 
	if((fp = fopen("画江湖之灵主21集.mp4","rb"))==NULL){
		printf("File open error!\n");
		exit(0);
	}
	
	fread(charPoint, 1, 10000, fp);       // 视频文件过大，这里先只读取前10000个字节
	
	for(int i = 0; i < 10000; i++){
		printf("%s ", trans(*(charPoint+i)));
	}
	
	
	fclose(fp); 
	free(charPoint);
	
	
	
	return 0;
}

char* trans(unsigned char ch){
	static char chs[3];        
	//static变量的生命周期更长，当该函数执行完毕后，内存不会被立即释放，这样就可以用指针将它的内存地址返回给主函数使用。
    switch(ch){     //这段switch语句由python程序生成的
        case 0:
            chs[0]='0';
            chs[1]='0';
            chs[2]=0;
            break;
        case 1:
            chs[0]='0';
            chs[1]='1';
            chs[2]=0;
            break;
        case 2:
            chs[0]='0';
            chs[1]='2';
            chs[2]=0;
            break;
       	/****
					中间内容过长，省略
				*********/
        case 254:
            chs[0]='f';
            chs[1]='e';
            chs[2]=0;
            break;
        case 255:
            chs[0]='f';
            chs[1]='f';
            chs[2]=0;
            break;
	}
	return chs;
}

运行结果为如下：（将结果输出到屏幕是一个比较慢的过程，如果将输出结果写入一个文件的话会快很多）

然后我们使用Hex Editor Neo打开该视频文件来验证输出结果的正确性：

通过对比我们就可以看出输出的结果是完全正确的。

下面再给出一个将输出结果写入文件的代码：

#include<stdio.h>
#include<stdlib.h>

char* trans(unsigned char ch);     
//由于这个函数的函数体太长了，这里省略，其函数体的代码和上面的一样

int main(void){
	FILE *fp;
	FILE *f;

	unsigned char *charPoint;
	if((charPoint = (unsigned char*)calloc(210406885, 1))==NULL){
		printf("Not able to allocate memory.\n");
		exit(0);
	} 
	
	//文件打开 
	if((fp = fopen("画江湖之灵主21集.mp4","rb"))==NULL){
		printf("File open error!\n");
		exit(0);
	}
	
	//将结果输出到hex.txt文件
	if((f = fopen("hex.txt","a"))==NULL){
		printf("hex.txt open error!\n");
		exit(0);
	}
	
	fread(charPoint, 1, 210406880, fp);
	
	for(int i = 0; i < 210406880; i++){
		fprintf(f, "%s ", trans(*(charPoint+i)));     // 文件格式化写入
	}
	
	fclose(f); 
	fclose(fp); 
	free(charPoint);

	return 0;
}

上面两个代码使用 switch 语句进行十六进制转换，是为了让读者更好地理解二进制。下面使用更简洁的方法进行十六进制输出：（使用 %x 以十六进制输出）

#include<stdio.h>
#include<stdlib.h>

int main(void){
	FILE *fp;
	FILE *f;
	
	
	//文件打开 
	if((fp = fopen("画江湖之灵主21集.mp4","rb"))==NULL){
		printf("File open error!\n");
		exit(0);
	}
	
	fseek(fp, 0, 2);    //将文件指针定位到文件的末尾
	
	int fsize = ftell(fp); //ftell函数返回文件指针当前所在的位置，前面已经定位到文件末尾，这里返回的值就是文件的大小	
	
	unsigned char *charPoint;
	if((charPoint = (unsigned char*)calloc(fsize + 2, 1))==NULL){
		printf("Not able to allocate memory.\n");
		exit(0);
	} 
	
	
	
	if((f = fopen("hex1.txt","a"))==NULL){
		printf("hex.txt open error!\n");
		exit(0);
	}
	
	fseek(fp, 0, 0);   //将文件指针重新定位到文件开头，以便下面读取数据 
	fread(charPoint, 1, fsize, fp);
	

//	for(int i = 0; i < fsize; i++){
//		printf("%02x ", *(charPoint+i));      //直接使用 %x 输出，会出现小于16的数输出的结果会少一个左边的0
//	}        //全部输出到显示会比较慢

	for(int i = 0; i < fsize; i++){
		fprintf(f, "%02x ", *(charPoint+i));     //每两个十六进制位之间用空格隔开是为了可读性更强，其实也可以省去空格
		//注意 %02x 的意思是以十六进制输出，占 2 个长度，不够两个长度的左边补0
	} 
	
	printf("文件大小：%d个字节。\n",fsize);        
	
	printf("over.\n"); 
	
	
	fclose(f); 
	fclose(fp); 
	free(charPoint);

		
	return 0;
}

通过以上几个例子，我们就已经清楚文件在计算机中的二进制表现形式，下面我们考虑如何使用C语言写一个压缩程序。

huffman 编码

下面我们考虑这样一个例子：
一个文件，总共有400bit，我们按照4位划分，可以得到100个4位二进制，由于一个4位二进制对应一位十六进制数，于是我们得到100个十六进制位数。然后我们对这100个十六进制位数进行统计，发现各个十六进制位出现的次数如下表：

十六进制位	出现的次数	频率
0	10	10%
1	7	7%
2	6	6%
3	2	2%
4	8	8%
5	6	6%
6	5	5%
7	12	12%
8	4	4%
9	2	2%
a	1	1%
b	10	10%
c	19	19%
d	3	3%
e	3	3%
f	2	2%

为了让压缩后的文件比特数量更少，我们要对这些十六进制数重新进行二进制编码，让出现频率最大的十六进制位的二进制比特数量最少，让出现频率小的二进制比特数量多一些，并且每个十六进制位对应唯一的二进制数。然后再将新的编码写入文件，这样得到文件比特数量就会更少。

现在考虑如何对这些十六进制位重新进行二进制编码：可以使用离散数学中的Huffman编码。步骤如下：

• 先将频率从小到大排列：1% 2% 2% 2% 3% 3% 4% 5% 6% 6% 7% 8% 10% 10% 12% 19%
• 然后选择最小的两个合成一个二叉树：得到了一个3%
  
• 然后再重新排列：2% 2% 3% 3% 3% 4% 5% 6% 6% 7% 8% 10% 10% 12% 19%，这时候再选最小的两个合成二叉树：得到一个 4%
  
• 然后再重新排列：3% 3% 3% 4% 4% 5% 6% 6% 7% 8% 10% 10% 12% 19%，这时候再选最小的两个合成二叉树：得到一个 6%
  
• 然后再重新排列：3% 4% 4% 5% 6% 6% 6% 7% 8% 10% 10% 12% 19%，这时候再选最小的两个合成二叉树：得到一个 7%
  
• 然后再重新排列：4% 5% 6% 6% 6% 7% 7% 8% 10% 10% 12% 19%，这时候再选最小的两个合成二叉树：得到一个 9%
  
• 然后再重新排列：6% 6% 6% 7% 7% 8% 9% 10% 10% 12% 19%，这时候再选最小的两个合成二叉树：得到一个 12%
  
• 然后再重新排列：6% 7% 7% 8% 9% 10% 10% 12% 12% 19%，这时候再选最小的两个合成二叉树：得到一个 13%
  
• 然后再重新排列：7% 8% 9% 10% 10% 12% 12% 13% 19%，这时候再选最小的两个合成二叉树：得到一个 15%
  
• 然后再重新排列：9% 10% 10% 12% 12% 13% 15% 19%，这时候再选最小的两个合成二叉树：得到一个 19%
  
• 然后再重新排列：10% 12% 12% 13% 15% 19% 19%，这时候再选最小的两个合成二叉树：得到一个 22%
  
• 然后再重新排列：12% 13% 15% 19% 19% 22%，这时候再选最小的两个合成二叉树：得到一个 25%
  
• 然后再重新排列：15% 19% 19% 22% 25%，这时候再选最小的两个合成二叉树：得到一个 34%
  
• 然后再重新排列：19% 22% 25% 34%，这时候再选最小的两个合成二叉树：得到一个 41%
  
  最后可以得到一个二叉树：这个二叉树总共有16个末梢，每一个末梢对应一个十六进制位（图中黄色方块）。统一规定：往左边的分支为0，往右边的分支为1，那么可以为十六进制位重新编码如下：
  
  0 : 1011
1 : 1000
2 : 0000
3 : 110001
4 : 1001
5 : 0001
6 : 10101
7 : 111
8 : 10100
9 : 110010
a : 110000
b : 001
c : 01
d : 11010
e : 11011
f : 110011
  将原来的400bit的文件按照这个新的编码重新写入，将会有
  $$4\times 10+4\times 7+4\times 6+6\times 2+4\times 8+4\times 6+5\times 5$$
  $$+3\times 12+5\times$$