案例二十基于詞表的詞頻統(tǒng)計(jì).ppt

第1頁(yè) 共36頁(yè),案例二十 基于詞表的詞頻統(tǒng)計(jì),本案例知識(shí)要點(diǎn) 鏈表的使用 文件操作 哈希表的使用 快速排序法 類(lèi)的設(shè)計(jì)和使用,第2頁(yè) 共36頁(yè),一、案例需求,案例描述 詞頻統(tǒng)計(jì)就是統(tǒng)計(jì)一個(gè)句子或一篇文章中各種詞出現(xiàn)的頻率，它是中文信息處理的一項(xiàng)基本技術(shù)，在很多領(lǐng)域中都有重要的應(yīng)用。例如在中文搜索引擎（如Google、百度）中，除特別常用的詞以外，一篇文章中出現(xiàn)頻率較高的詞通常能反映這篇文章的主題，因此可以使用詞頻來(lái)對(duì)中文文章進(jìn)行歸類(lèi)。本案例實(shí)現(xiàn)按詞表對(duì)文章中的詞語(yǔ)進(jìn)行分析，并按字典序給出詞表中各詞語(yǔ)在文章中出現(xiàn)的次數(shù)。 案例效果圖 本案例需要一個(gè)待統(tǒng)計(jì)文本文件，如圖所示。,第3頁(yè) 共36頁(yè),待統(tǒng)計(jì)文本文件,第4頁(yè) 共36頁(yè),本案例需一個(gè)詞表文件，如圖所示。,詞表文件內(nèi)容,第5頁(yè) 共36頁(yè),本案例最終統(tǒng)計(jì)出每個(gè)詞在文本中出現(xiàn)的次數(shù)。運(yùn)行效果如圖所示。,運(yùn)行效果,第6頁(yè) 共36頁(yè),本案例最終統(tǒng)計(jì)出的結(jié)果保存在文件out.txt中。效果如圖所示。,out.txt文件,第7頁(yè) 共36頁(yè),功能說(shuō)明 （1）本案例需要一個(gè)文本和一個(gè)詞表，統(tǒng)計(jì)出每個(gè)詞在文本中出現(xiàn)的次數(shù)。統(tǒng)計(jì)的原則包括以下兩種： 交集型。例如“內(nèi)存在漲價(jià)”，需要統(tǒng)計(jì)“內(nèi)存”和“存在”兩個(gè)詞各一次（假設(shè)這兩個(gè)詞都在詞表中）。 組合型。例如“中美關(guān)系在發(fā)展”，需要統(tǒng)計(jì)“中美”、“關(guān)系”和“中美關(guān)系”（假設(shè)這3個(gè)詞都在詞表中）。,第8頁(yè) 共36頁(yè),文本和詞表的格式如下： 文本是一個(gè)長(zhǎng)句，句中只包含漢字，不包含數(shù)字、標(biāo)點(diǎn)、空格、回車(chē)以及其他任何特殊符號(hào)。文本規(guī)模小于或等于50 000漢字。 詞表的規(guī)模小于或等于100 000個(gè)詞，所有詞不重復(fù)，詞在27個(gè)漢字之間，每個(gè)詞占一行。 實(shí)現(xiàn)基于詞表的詞頻統(tǒng)計(jì)，從磁盤(pán)中讀取詞表和文本，將詞頻統(tǒng)計(jì)結(jié)果輸出到磁盤(pán)中，輸出結(jié)果要求按字典序排序，并計(jì)算出程序運(yùn)行時(shí)間。,第9頁(yè) 共36頁(yè),二、案例分析,根據(jù)需要構(gòu)造一個(gè)哈希表類(lèi)，在類(lèi)中實(shí)現(xiàn)如下操作： （1）建立哈希表，將詞表在內(nèi)存中存儲(chǔ)起來(lái)，這個(gè)存儲(chǔ)的過(guò)程就是類(lèi)的構(gòu)造函數(shù)。案例中的詞表是數(shù)量較大的詞組，詞與詞之間用空格隔開(kāi)。因此可用文件流函數(shù)getline來(lái)實(shí)現(xiàn)。每次調(diào)用getline函數(shù)便得到一個(gè)存有詞的字符串，然后將字符串按照某種散列函數(shù)插入到哈希表中，一直到詞表全部存儲(chǔ)為止。 （2）統(tǒng)計(jì)詞頻。從詞表中讀取文本文件，存儲(chǔ)在一個(gè)字符串中，因?yàn)槊總€(gè)漢字存儲(chǔ)在兩字節(jié)中，所以詞在414字節(jié)之間，用char word15即可表示一個(gè)詞。考慮到詞頻統(tǒng)計(jì)的交集性和組合性原則，可將在文本字符串中的每個(gè)漢字與其后的漢字分別組成27個(gè)漢字的詞，在詞表中進(jìn)行搜索，每被搜到一次，將統(tǒng)計(jì)次數(shù)加1。循環(huán)直到文本末尾。,第10頁(yè) 共36頁(yè),（3）哈希函數(shù)（散列函數(shù)）的實(shí)現(xiàn)。用char word15存儲(chǔ)的詞得到一個(gè)關(guān)鍵字，然后除以某個(gè)素?cái)?shù)，得到的余數(shù)為散列地址。由于數(shù)據(jù)較多，要高速完成搜索，散列到每個(gè)相同地址的元素要盡量少，因此素?cái)?shù)要很大，關(guān)鍵字的范圍也要很大而且不重疊。 （4）按字符的字典序排序輸出。哈希表是亂序存儲(chǔ)的，因此可先遍歷哈希表，將所有詞頻大于0的詞存入數(shù)組中，用快速排序法對(duì)這個(gè)數(shù)組中的元素進(jìn)行排序。,第11頁(yè) 共36頁(yè),三、案例設(shè)計(jì),1類(lèi)的設(shè)計(jì) 根據(jù)案例分析，需要設(shè)計(jì)出兩個(gè)結(jié)構(gòu)體NODE和TABLE，同時(shí)還需要設(shè)計(jì)一個(gè)類(lèi)SYMBOLTABLE。其中，結(jié)構(gòu)體NODE是哈希桶（哈希桶即哈希表中各個(gè)同地址值的元素構(gòu)成的鏈表）中節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)，TABLE是哈希表的結(jié)構(gòu)，SYMBOLTABLE類(lèi)提供了諸如哈希函數(shù)、查找詞匯、遍歷哈希表、將詞匯插入哈希表中、快速排序等功能。,第12頁(yè) 共36頁(yè),第13頁(yè) 共36頁(yè),第14頁(yè) 共36頁(yè),第15頁(yè) 共36頁(yè),第16頁(yè) 共36頁(yè),第17頁(yè) 共36頁(yè),2主程序設(shè)計(jì) 在主函數(shù)中聲明了一個(gè)SYMBOLTABLE類(lèi)的對(duì)象，依次調(diào)用哈希表類(lèi)的構(gòu)造函數(shù)、統(tǒng)計(jì)函數(shù)、輸出函數(shù)即可。另外，為了記錄程序的運(yùn)行時(shí)間，包含了time頭文件，調(diào)用clock函數(shù)，能精確到毫秒。主程序有詳細(xì)的注釋?zhuān)逦锥?，流程圖略。,第18頁(yè) 共36頁(yè),第19頁(yè) 共36頁(yè),第20頁(yè) 共36頁(yè),第21頁(yè) 共36頁(yè),第22頁(yè) 共36頁(yè),第23頁(yè) 共36頁(yè),第24頁(yè) 共36頁(yè),第25頁(yè) 共36頁(yè),第26頁(yè) 共36頁(yè),第27頁(yè) 共36頁(yè),第28頁(yè) 共36頁(yè),第29頁(yè) 共36頁(yè),第30頁(yè) 共36頁(yè),第31頁(yè) 共36頁(yè),第32頁(yè) 共36頁(yè),第33頁(yè) 共36頁(yè),第34頁(yè) 共36頁(yè),第35頁(yè) 共36頁(yè),第36頁(yè) 共36頁(yè),第37頁(yè) 共36頁(yè),五、案例總結(jié)與提高,案例總結(jié) 本案例類(lèi)的設(shè)計(jì)并不復(fù)雜，但是要求讀者除了具備C+基本知識(shí)和簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)知識(shí)以外，還要求讀者掌握文件流、哈希表、快速排序、算法設(shè)計(jì)、主函數(shù)接口等諸多知識(shí)點(diǎn)，否則案例理解起來(lái)比較困難。本案例用到的許多知識(shí)點(diǎn)在數(shù)據(jù)結(jié)構(gòu)教材中都有很詳細(xì)的講述，讀者可以查找相關(guān)書(shū)籍熟悉這些知識(shí)，對(duì)照程序來(lái)理解掌握這些知識(shí)，逐步提升程序設(shè)計(jì)水平。,第