C語言中壓縮字符串的算法
在C應(yīng)用中，經(jīng)常需要將字符串壓縮成一個(gè)整數(shù)，即字符串散列。下面是小編為大家整理的C語言中壓縮字符串的算法，歡迎參考~
比如下面這些問題：
(1)搜索引擎會(huì)通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個(gè)查詢串的長度為1-255字節(jié)。請找出最熱門的10個(gè)檢索串。
(2)有一個(gè)1G大小的一個(gè)文件，里面每一行是一個(gè)詞，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個(gè)詞。
(3)有10個(gè)文件，每個(gè)文件1G，每個(gè)文件的'每一行存放的都是用戶的query，每個(gè)文件的query都可能重復(fù)。要求你按照query的頻度排序。
(4)給定a、b兩個(gè)文件，各存放50億個(gè)url，每個(gè)url各占64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的url。
(5)一個(gè)文本文件，大約有一萬行，每行一個(gè)詞，要求統(tǒng)計(jì)出其中最頻繁出現(xiàn)的前10個(gè)詞。
這些問題都需要將字符串壓縮成一個(gè)整數(shù)，或者說是散列到某個(gè)整數(shù) M 。然后再進(jìn)行取余操作，比如 M%16，就可以將該字符串放到編號為M%16的文件中，相同的字符串肯定是在同一個(gè)文件中。通過這種處理，就可以將一個(gè)大文件等價(jià)劃分成若干小文件，而對于小文件，就可以用常規(guī)的方法處理，內(nèi)排序、hash_map等等。最后將這些小文件的處理結(jié)果綜合起來，就可以求得原問題的解。
下面介紹一些字符串壓縮的算法。
方法1：最簡單就是將所有字符加起來，代碼如下：
unsigned long HashString(const char *pString, unsigned long tableSize)
{
unsigned long hashValue = 0;
while(*pString)
hashValue += *pString++;
return hashValue % tableSize;
}
分析：如果字符串的長度有限，而散列表比較大的話，浪費(fèi)比較大。例如，如果字符串最長為16字節(jié)，那么用到的僅僅是散列表的前16*127=2032。假如散列表含2729項(xiàng)，那么2032以后的項(xiàng)都用不到。
方法2：將上次計(jì)算出來的hash值左移5位（乘以32），再和當(dāng)前關(guān)鍵字相加，能得到較好的均勻分布的效果。
unsigned long HashString(const char *pString,unsigned long tableSize)
{
unsigned long hashValue = 0;
while (*pString)
hashValue = (hashValue << 5) + *pString++;
return hashValue % tableSize;
}
分析：這種方法需要遍歷整個(gè)字符串，如果字符串比較大，效率比較低。
方法3：利用哈夫曼算法，假設(shè)只有0-9這十個(gè)字符組成的字符串，我們借助哈夫曼算法，直接來看實(shí)例：
#define Size 10
int freq[Size];
string code[Size];
string word;
struct Node
{
int id;
int freq;
Node *left;
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
{
return a->freq < b->freq;
}
};
void init()
{
for(int i = 0; i < Size; ++i)
freq[i] = 0;
for(int i = 0; i < word.size(); ++i)
++freq[word[i]];
}
void dfs(Node *root, string res)
{
if(root->id >= 0)
code[root->id] = res;
else
{
if(NULL != root->left)
dfs(root->left, res+"0");
if(NULL != root->right)
dfs(root->right, res+"1");
}
}
void Nodes(Node *root)
{
if(NULL == root)
return ;
if(NULL == root->left && NULL == root->right)
root;
else
{
Nodes(root->left);
Nodes(root->right);
root;
}
}
void BuildTree()
{
priority_queue<Node*, vector
for(int i = 0; i < Size; ++i)
{
//0 == freq[i] 的情況未處理
Node *newNode = new Node(freq[i]);
newNode->id = i;
nodes.push(newNode);
}
while(nodes.size() > 1)
{
Node *left = nodes.top();
nodes.pop();
Node *right = nodes.top();
nodes.pop();
Node *newNode = new Node(left->freq + right->freq);
newNode->left = left;
newNode->right = right;
nodes.push(newNode);
}
Node *root = nodes.top();
dfs(root, string(""));
Nodes(root);
}
【C語言中壓縮字符串的算法】相關(guān)文章：
C語言字符串快速壓縮算法代碼12-23
C語言中實(shí)現(xiàn)KMP算法實(shí)例11-19
C語言中返回字符串函數(shù)的實(shí)現(xiàn)方法12-15
c語言中關(guān)于使用BF-KMP算法實(shí)例11-21
c語言中用字符串?dāng)?shù)組寫菜單的代碼11-19
C語言中三種常見排序算法分析12-13
C 語言中返回字符串函數(shù)的四種實(shí)現(xiàn)方法11-16