快捷導(dǎo)航

C語言中壓縮字符串的簡單算法小結(jié)

更新時間：2016年03月15日 14:35:20 作者：wuzhekai1985

這篇文章主要介紹了C語言中可用于實現(xiàn)字符串壓縮的簡單算法小結(jié),列舉了包括哈夫曼算法等三個核心的程序?qū)崿F(xiàn)算法,需要的朋友可以參考下

應(yīng)用中，經(jīng)常需要將字符串壓縮成一個整數(shù)，即字符串散列。比如下面這些問題：
（1）搜索引擎會通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個查詢串的長度為1-255字節(jié)。請找出最熱門的10個檢索串。
（2）有一個1G大小的一個文件，里面每一行是一個詞，詞的大小不超過16字節(jié)，內(nèi)存限制大小是1M。返回頻數(shù)最高的100個詞。
（3）有10個文件，每個文件1G，每個文件的每一行存放的都是用戶的query，每個文件的query都可能重復(fù)。要求你按照query的頻度排序。
（4）給定a、b兩個文件，各存放50億個url，每個url各占64字節(jié)，內(nèi)存限制是4G，讓你找出a、b文件共同的url。
（5）一個文本文件，大約有一萬行，每行一個詞，要求統(tǒng)計出其中最頻繁出現(xiàn)的前10個詞。

這些問題都需要將字符串壓縮成一個整數(shù)，或者說是散列到某個整數(shù) M 。然后再進行取余操作，比如 M%16，就可以將該字符串放到編號為M%16的文件中，相同的字符串肯定是在同一個文件中。通過這種處理，就可以將一個大文件等價劃分成若干小文件，而對于小文件，就可以用常規(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;
}

分析：如果字符串的長度有限，而散列表比較大的話，浪費比較大。例如，如果字符串最長為16字節(jié)，那么用到的僅僅是散列表的前16*127=2032。假如散列表含2729項，那么2032以后的項都用不到。

方法2：將上次計算出來的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;
}

分析：這種方法需要遍歷整個字符串，如果字符串比較大，效率比較低。

方法3：利用哈夫曼算法，假設(shè)只有0-9這十個字符組成的字符串，我們借助哈夫曼算法，直接來看實例：

#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 deleteNodes(Node *root) 
{ 
 if(NULL == root) 
  return ; 
 if(NULL == root->left && NULL == root->right) 
  delete root; 
 else 
 { 
  deleteNodes(root->left); 
  deleteNodes(root->right); 
  delete root; 
 } 
} 
void BuildTree() 
{ 
 priority_queue<Node*, vector<Node*>, NodeLess> nodes; 
 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("")); 
 deleteNodes(root); 
}

您可能感興趣的文章: