C語言中壓縮字符串的簡單算法
在C應用中,經常需要將字符串壓縮成一個整數,即字符串散列。本文是本站小編搜索整理的關於C語言中壓縮字符串的簡單算法,供參考學習,希望對大家有所幫助!想了解更多相關信息請持續關注我們應屆畢業生考試網!
比如下面這些問題:
(1)搜索引擎會通過日誌文件把用户每次檢索使用的所有檢索串都記錄下來,每個查詢串的長度為1-255字節。請找出最熱門的10個檢索串。
(2)有一個1G大小的一個文件,裏面每一行是一個詞,詞的大小不超過16字節,內存限制大小是1M。返回頻數最高的100個詞。
(3)有10個文件,每個文件1G,每個文件的每一行存放的都是用户的query,每個文件的query都可能重複。要求你按照query的頻度排序。
(4)給定a、b兩個文件,各存放50億個url,每個url各佔64字節,內存限制是4G,讓你找出a、b文件共同的url。
(5)一個文本文件,大約有一萬行,每行一個詞,要求統計出其中最頻繁出現的`前10個詞。
這些問題都需要將字符串壓縮成一個整數,或者説是散列到某個整數 M 。然後再進行取餘操作,比如 M%16,就可以將該字符串放到編號為M%16的文件中,相同的字符串肯定是在同一個文件中。通過這種處理,就可以將一個大文件等價劃分成若干小文件,而對於小文件,就可以用常規的方法處理,內排序、hash_map等等。最後將這些小文件的處理結果綜合起來,就可以求得原問題的解。
下面介紹一些字符串壓縮的算法。
方法1:最簡單就是將所有字符加起來,代碼如下:
unsigned long HashString(const char *pString, unsigned long tableSize)
{
unsigned long hashValue = 0;
while(*pString)
hashValue += *pString++;
return hashValue % tableSize;
}
分析:如果字符串的長度有限,而散列表比較大的話,浪費比較大。例如,如果字符串最長為16字節,那麼用到的僅僅是散列表的前16*127=2032。假如散列表含2729項,那麼2032以後的項都用不到。
方法2:將上次計算出來的hash值左移5位(乘以32),再和當前關鍵字相加,能得到較好的均勻分佈的效果。
unsigned long HashString(const char *pString,unsigned long 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];
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 < (); ++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;
(newNode);
}
while(() > 1)
{
Node *left = ();
();
Node *right = ();
();
Node *newNode = new Node(left->freq + right->freq);
newNode->left = left;
newNode->right = right;
(newNode);
}
Node *root = ();
dfs(root, string(""));
deleteNodes(root);
}
-
淺談高職C語言課程的教學分析與設計
C語言作為學院網絡技術專業的人門課程,旨在通過鍛鍊學生的邏輯思維,牆養學生在職業崗位中實際應用的能力.目前,該專業的學生畢業後主要從事網站開發和網絡管理等方面的工作,而在這些領域幾乎都以C語言作為應用的開發工具.但從歷年教學實踐來看,教師往往付出的精力多...
-
2017全國計算機二級《C語言》考試題及答案
在備考複習階段,需通過大量試題練習,加深對考點的理解和掌握。以下是本站小編搜索整理的一份全國計算機二級《C語言》考試題及答案,供參考練習,希望對大家有所幫助!想了解更多相關信息請持續關注我們應屆畢業生考試網!一、選擇題1).我們所寫的每條C語句,經過編譯最...
-
C語言新人常見問題與錯誤
不知不覺,學習C語言也快一年了。雖然有C語言課,但是老師完全讓我們自己看書,在自學的過程中,和周圍同學交流中,以及後來在CSDN,BCCN,百度知道看帖回帖中,也看到許多C語言新人常遇到的問題與常犯的錯誤。不妨看看吧。以下僅供參考!對於完整的修正後的程序都在code::block...
-
如何在c語言中調用Linux腳本
如何在c語言中調用Linux腳本呢?你知道如何在c語言中調用Linux腳本嗎?下面是小編為大家帶來的如何在c語言中調用Linux腳本的知識,歡迎閲讀。一、引言對於沒有接觸過Unix/Linux操作系統的人來説,fork是最難理解的概念之一:它執行一次卻返回兩個值。fork函數是Unix系...