技術(shù)應(yīng)用論文基于單鏈表和散列表比較的詞頻統(tǒng)計研究

1、技術(shù)應(yīng)用論文：基于單鏈表和散列表比較的詞頻統(tǒng)計研究摘要:針對操作系統(tǒng)課程中的詞頻統(tǒng)計實驗,介紹兩種分別采用單鏈表和散列表進(jìn)行詞頻統(tǒng)計的方法,并著重說明后一種方法在效率方面的優(yōu)越性。 關(guān)鍵詞:單鏈表;散列表;詞頻統(tǒng)計;效率 在操作系統(tǒng)課程中,詞頻統(tǒng)計實驗具有重要的理論價值和實用價值,一直受到廣大師生的重視。該實驗要求編寫程序,讀取一個文件,對該文件中的英文文章進(jìn)行詞頻統(tǒng)計,并把統(tǒng)計結(jié)果存放到另一個文件中。程序的功能并不復(fù)雜,大多數(shù)學(xué)生都能完成,但是程序的效率往往不盡如人意。采用單鏈表和散列表進(jìn)行詞頻統(tǒng)計都是該實驗常用的方法。從效率方面來看,后一種方法明顯優(yōu)于前一種方法。 1采用單鏈表進(jìn)行詞頻統(tǒng)計

2、 1.1概述 在該實驗中,大多數(shù)學(xué)生采用單鏈表進(jìn)行詞頻統(tǒng)計。這種方法簡潔明了,易于理解,但是程序每次從文件中讀取一個單詞后,都要在單鏈表中順序查找該單詞,這就大大降低了程序的效率。下面通過程序流程圖和部分代碼來說明采用單鏈表進(jìn)行詞頻統(tǒng)計的具體過程。 1.2解決方案 1.2.1數(shù)據(jù)結(jié)構(gòu) 由于程序最后要輸出各單詞及其出現(xiàn)的次數(shù),因此要聲明一個結(jié)構(gòu)體類型。分別使用char型數(shù)組和int型變量存儲單詞及其出現(xiàn)的次數(shù)。這樣在輸出統(tǒng)計結(jié)果時,只要遍歷單鏈表即可。 typedef struct wordNode char wordlength; int iWordCount; wordNode *pNext

3、; wordNode; 1.2.2程序流程圖 程序每次從文件中讀取一個單詞,刪除該單詞末尾可能帶有的標(biāo)點符號后,在單鏈表中順序查找該單詞。如果查找到該單詞,那么把該單詞出現(xiàn)的次數(shù)加1,不再繼續(xù)查找。如果沒有查找到該單詞,那么把該單詞插入到單鏈表的尾部,并把該單詞出現(xiàn)的次數(shù)置1。等到文件中的所有單詞都處理完畢后,輸出統(tǒng)計結(jié)果。程序流程圖如圖1所示。 1.2.3處理單詞細(xì)節(jié) 按照英文書寫習(xí)慣,標(biāo)點符號一般緊跟在前一個單詞之后。當(dāng)程序從文件中讀取一個單詞時,由于一旦遇到空格或換行即認(rèn)為單詞讀取完畢,因此會出現(xiàn)單詞和標(biāo)點符號一并讀取的情況。所以要定義一個函數(shù)Clip(),刪除單詞末尾的標(biāo)點符號。對讀取

4、的單詞,要判斷最后一個字符是否為字母,若不是字母則將其刪除。不過單詞末尾的標(biāo)點符號也存在一些特殊情況。例如,“a.m.”和“Mr.”等是特定的縮寫,最后的“.”不能刪除;“students”最后的“”表示復(fù)數(shù)所有格,也不能刪除。以下是函數(shù)Clip()的具體代碼,對有些特殊情況無法一一列舉,這也是該函數(shù)不完善之處。 void Clip(char *current) int i; i = strlen(current); if (!strcmp(current, "a.m.") return; else if (!strcmp(current, "Dr.")

5、 return; else if (!strcmp(current, "Mr.") return; else if (!strcmp(current, "Mrs.") return; else if (!strcmp(current, "Ms.") return; else if (!strcmp(current, "p.m.") return; else if (!isalpha(currenti - 1) && (currenti - 1 != ''') currenti

6、 - 1 = '0' 此外,當(dāng)某個單詞出現(xiàn)在句首和句中時,首字母有大小寫之分,這會導(dǎo)致使用函數(shù)strcmp()判斷它們是否相同時,把它們誤判為不相同。所以要定義一個函數(shù)Change(),把單詞中的大寫字母轉(zhuǎn)化為小寫字母,以消除由于大小寫不一致而導(dǎo)致的誤判。以下是函數(shù)Change()的具體代碼。 void Change(char *current) for (; *current != '0' current+) if (*current >= 'A') && (*current <= 'Z') *cur

7、rent += 32; 1.3分析 采用單鏈表進(jìn)行詞頻統(tǒng)計的主要操作是在單鏈表中進(jìn)行順序查找和在單鏈表尾部進(jìn)行插入。程序每次從文件中讀取一個單詞后,都要在單鏈表中順序查找該單詞。反復(fù)在單鏈表中進(jìn)行順序查找,會大大降低程序的效率。以一篇300詞的英文文章為例,在最壞情況下,即300個單詞都不一樣,單詞之間所進(jìn)行的比較次數(shù)達(dá)到0 + 1 + 2 + + 298 + 299 = 44850。在該實驗中,發(fā)現(xiàn)大多數(shù)學(xué)生使用短篇英文文章來測試程序,所以雖然程序的效率較低,但是在運(yùn)行時間上體現(xiàn)得并不十分明顯。若使用10M大小的英文文章來測試程序,則運(yùn)行時間會長達(dá)半分鐘之久。因此,如果要對長篇英文文章進(jìn)行詞

8、頻統(tǒng)計,那么采用單鏈表是不太合適的。 2采用散列表進(jìn)行詞頻統(tǒng)計 2.1概述 查找的效率取決于查找過程中關(guān)鍵字之間所進(jìn)行的比較次數(shù)。散列表是表示集合的一種有效方法,它提供了一種特殊的存儲和查找方式,通過把記錄的關(guān)鍵字映射到表中的地址來存儲記錄,并根據(jù)記錄的關(guān)鍵字用同樣的方式直接查找1279。 在該實驗中,采用散列表進(jìn)行詞頻統(tǒng)計可以明顯減少查找過程中單詞之間所進(jìn)行的比較次數(shù),大大提高查找的效率。 2.2散列與散列函數(shù)簡介 以往考慮的查找方法,是以關(guān)鍵字之間所進(jìn)行的比較為基礎(chǔ),根據(jù)它們的大小來進(jìn)行判定的2。由于查找是不少程序運(yùn)行時最耗時的部分,因此使用好的查找方法常會明顯減少運(yùn)行時間。理想的查找方法

9、是,根據(jù)待查記錄的關(guān)鍵字直接得到它的存儲地址,而不必把待查記錄的關(guān)鍵字和集合中某些記錄的關(guān)鍵字逐個比較。在記錄的關(guān)鍵字和它的存儲地址之間建立一個確定的對應(yīng)關(guān)系hash(),使關(guān)鍵字key和存儲地址address相對應(yīng): address = hash(key) 在存儲時,按該函數(shù)計算存儲地址并按該存儲地址存儲。在查找時,對待查記錄的關(guān)鍵字進(jìn)行同樣的函數(shù)計算,把求得的函數(shù)值當(dāng)作存儲地址,按該存儲地址取出記錄進(jìn)行比較,若關(guān)鍵字相等則查找成功。這種方法稱為散列,在散列中使用的函數(shù)則稱為散列函數(shù)3。 如果有多個記錄的存儲地址相同,那么就會產(chǎn)生沖突。由于沖突過多的話會降低查找的效率,因此要構(gòu)造地址分布比較

10、均勻的散列函數(shù)來有效地減少沖突。在實際情況中,關(guān)鍵字集合要比地址集合大得多,沖突難以避免,所以還要采取措施來處理沖突。 2.3解決方案 2.3.1數(shù)據(jù)結(jié)構(gòu) 和采用單鏈表進(jìn)行詞頻統(tǒng)計相同,仍然使用結(jié)構(gòu)體來存儲單詞及其出現(xiàn)的次數(shù)。散列表則是結(jié)構(gòu)體類型一維數(shù)組。 typedef struct wordNode char wordlength;int iWordCount; wordNode *pNext; wordNode; wordNode *hashtabHASHSIZE; 其中,HASHSIZE在宏定義中定義為100。 2.3.2構(gòu)造散列函數(shù) 散列函數(shù)有多種構(gòu)造方法。在該實驗中,使用除留余數(shù)法

11、來構(gòu)造散列函數(shù)。先把單詞中所有字符的ASCII碼相加,再把所得到的和除以質(zhì)數(shù)p,最后把所得到的余數(shù)當(dāng)作散列表中的地址。設(shè)m為散列表的長度,為了盡量減少沖突,p應(yīng)取一個不大于m且最接近于m的質(zhì)數(shù),由于是整數(shù)求模運(yùn)算,因此p不能接近于2的冪1280。在該實驗中,m所取的值和HASHSIZE相同,為100。以下是散列函數(shù)Hash()的具體代碼。 int Hash(char *current) int hashval; for (hashval = 0; *current != '0' current+) hashval += *current; return hashval % 97

12、; 其中,97是不大于100且最接近于100的質(zhì)數(shù)。 2.3.3使用開散列法處理沖突 在該實驗中,使用開散列法來處理沖突。開散列法又稱鏈地址法。根據(jù)統(tǒng)計,開散列法優(yōu)于閉散列法。開散列法把通過散列函數(shù)計算得到的具有相同存儲地址的記錄歸于同一個子集,每個子集稱為一個桶。桶又稱為同義詞子表1291。桶是和某個存儲地址相對應(yīng)的存儲空間。桶可以是一個單元,存儲一個記錄;也可以是多個單元,存儲多個記錄。桶號和存儲地址相對應(yīng)4。使用開散列法處理沖突的散列表示意圖如圖2所示。 2.3.4查找單詞 在查找單詞時,只要先確定該單詞所在的桶,再在該桶中順序查找該單詞即可,而桶號則是通過散列函數(shù)計算得到的。這可以明顯

13、減少單詞之間所進(jìn)行的比較次數(shù),大大提高查找的效率。如果采用單鏈表進(jìn)行詞頻統(tǒng)計,判斷一個單詞是否存在時,最壞的情況下要把單鏈表中的所有單詞都和該單詞進(jìn)行比較。而如果采用散列表進(jìn)行詞頻統(tǒng)計,在最壞情況下只要把某個桶中的所有單詞都和該單詞進(jìn)行比較即可,其在效率方面的優(yōu)越性顯而易見。 2.4分析 散列表是一種直接計算記錄存儲地址的數(shù)據(jù)結(jié)構(gòu),它在關(guān)鍵字和存儲地址之間直接建立映像,所以在查找過程中,可以明顯減少關(guān)鍵字之間所進(jìn)行的比較次數(shù),大大提高查找的效率。 在該實驗中,所使用的除留余數(shù)法散列函數(shù)和開散列法處理沖突方法都具有相對較優(yōu)的性能。同樣使用10M大小的英文文章來測試程序,運(yùn)行時間只有1秒鐘左右,與

14、之前的半分鐘之久相比,采用散列表進(jìn)行詞頻統(tǒng)計在效率方面明顯優(yōu)于采用單鏈表進(jìn)行詞頻統(tǒng)計。 3結(jié)語 通過對采用單鏈表和散列表進(jìn)行詞頻統(tǒng)計的比較,我們不難看出,如果要對長篇英文文章進(jìn)行詞頻統(tǒng)計,采用散列表更為合適。采用散列表進(jìn)行詞頻統(tǒng)計具有分類的思想,即根據(jù)散列值對單詞進(jìn)行分類。例如,把散列值為0的單詞分為一類,也就是前面所提到的桶。在查找單詞時,先確定該單詞所在的類,再在該類中順序查找該單詞。這在很大程度上縮小了查找的范圍,減少了單詞之間所進(jìn)行的比較次數(shù)。借鑒分類的思想,我們可以對采用單鏈表進(jìn)行詞頻統(tǒng)計加以改進(jìn)。例如,可以根據(jù)單詞的首字母把單詞分為26個類,每個類為一個單鏈表。在查找單詞時,先根據(jù)該單詞的首字母確定該單詞所在的類,再在該類中順序查找該單詞。這也在較大程度上縮小了查找的范圍,減少了單詞之間所進(jìn)行的比較次數(shù)。 對散列表所進(jìn)行的實驗評估表明,它具有很好的平均性能,優(yōu)于一些傳統(tǒng)的技術(shù)1293。散列表可以使用常數(shù)階的平均時間進(jìn)行查找5。不過散列表在最壞情況下的性能并不好。對有n個記錄的散列表進(jìn)行一次查找,在最壞情況下,要花費(fèi)O(n)的時間1293。但是綜合來看,采用散列表進(jìn)行詞頻統(tǒng)計無疑是非常合適的。 參考文獻(xiàn): 1 殷人昆. 數(shù)據(jù)結(jié)構(gòu)(用面向?qū)ο蠓椒ㄅcC+