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

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