C语言中压缩字符串的简单算法小结

C语言中压缩字符串的简单算法小结语言中压缩字符串的简单算法小结

主要介绍了C语言中可用于实现字符串压缩的简单算法小结,列举了包括哈夫曼算法等三个核心的程序实现算法,

需要的朋友可以参考下

应用中，经常需要将字符串压缩成一个整数，即字符串散列。比如下面这些问题：

（1）搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。请找出最热

门的10个检索串。

（2）有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100

个词。

小文件，而对于小文件，就可以用常规的方法处理，内排序、hash_map等等。最后将这些小文件的处理结果综合起来，就可

以求得原问题的解。

下面介绍一些字符串压缩的算法。

方法方法1：：最简单就是将所有字符加起来，代码如下：

unsigned long HashString(const char *pString, unsigned long tableSize)

{

unsigned long hashValue = 0;

while(*pString)

hashValue += *pString++;

return hashValue % tableSize;

unsigned long hashValue = 0;

while (*pString)

hashValue = (hashValue << 5) + *pString++;

return hashValue % tableSize;

}

分析：这种方法需要遍历整个字符串，如果字符串比较大，效率比较低。

方法方法3：：利用哈夫曼算法，假设只有0-9这十个字符组成的字符串，我们借助哈夫曼算法，直接来看实例：

#define Size 10

int freq[Size];

string code[Size];

Node *right;

Node(int freq_in):id(-1), freq(freq_in)

{

left = right = NULL;

}

};

struct NodeLess

{

bool operator()(const Node *a, const Node *b) const

{

for(int i = 0; i < Size; ++i)

freq[i] = 0;