【字符】压缩文本文件

【字符】压缩文本文件

如果感觉我的文章对您有帮助的话，请不要吝啬您的点赞哦awa

压缩是一种有效的减小数据量的方法，目前已经被广泛应用于各种类型的信息系统之中。
一种压缩文本文件（假设文件中不包含数字）的方法如下：

1. 原始文本文件中的非字母的字符，直接拷贝到压缩文件中；
2. 原始文件中的词（全部由字母组成），如果是第一次出现，则将该词加入到一个词的列表中，并拷贝到压缩文件中；否则该词不拷贝到压缩文件中，而是将该词在词的列表中的位置拷贝到压缩文件中。
3. 词的列表的起始位置为 1 。 词的定义为文本中由大小写字母组成的最大序列。大写字母和小写字母认为是不同的字母，即 abc 和 Abc 是不同的词。词的例子如下： x-ray 包括两个词 x 和 ray；mary’s 包括两个词 mary 和 s；a c-Dec 包括三个词 a 和 c 和 Dec 编写一个程序，输入为一组字符串，输出为压缩后的文本。

输入：

输入为一段文本，可以假设输入中不会出现数字、每行的长度不会超过 80 个字符，并且输入文本的大小不会超过 10M。

输出：

压缩后的文本。

样例：

思路

其实思路上很简单，这段程序主要就包含三部分
读入、查找/插入、输出
其中读入部分主要负责读入文本和判断单词
查找/输入部分顾名思义主要负责查找当前单词是否存在和如果存在给出对应的key，如果不存在则创建一个
输出部分最为简单，直接输出压缩后的文本即可

读入

本文中读入文本采用的是较为简单的双指针算法，即求输入文本中的字母段，再将其存储进一个临时字符串中

while(gets(temp))
    {
    	for(int i = 0,j;temp[i];i ++)
    	{
    		if(!letter(temp[i]))
    		{
    			printf("%c",temp[i]);
    			continue;
			}
    		char word[90] = {0},k = 0;
    		for(j = i;temp[j] && letter(temp[j]);j ++) word[k++] = temp[j];
    		i = j - 1;
		}
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

查找/插入

首先最为直接的，我们可以创建一个单词列表，每一次查找都遍历一次，找到相同的则返回对应的key
否则就存储

int find(char* x) 
{ 
	for(int i = 1;i <= cnt;i ++) //此处cnt为单词总数
	{ 
		if(!strcmp(x,words[i])) return i; 
	} 
	strcpy(words[++cnt],x); 
	return 0; 
} 
1
2
3
4
5
6
7
8
9

其次，为了提升运算速度，我们可以使用字典树

int find(char str[])
{
	int p = 0;
	for(int i = 0;str[i];i ++)
	{
		int u = str[i] < 'a' ? str[i] - 'A' + 26 : str[i] - 'a';
		if(!son[p][u])
		{
			son[p][u] = ++idx;
		}
		p = son[p][u];
	}
	if(key[p]) return key[p];
	key[p] = ++key[0];
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

输出

这部分就极为简单了

if(i = find(word)) printf("%d",i);
else printf("%s",word);
1
2

或者直接把这部分嵌入find函数中也是可以的
别忘了每一行结束要输出一个换行符

else

使用字典树的情况下，速度可以达到0.01秒，已经非常快了