基于关键词提取的TFIDF和TextRank方法的对比研究

1、基于关键词提取的 TFIDF 和 TextRank 方法的对比研究题目：开发一个程序，在该程序中，允许输入一段文本（以界面或者文件输入方式均可）， 该程序自动抽取出包含的关键词，并按照关键词的权重由高到低排序后输出。完成日期： 2016.06.05一、需求分析以文本的形式读入数据，将每个单词抽象成一棵树，将单词与单词之间的关 系抽象为图。TFIDF算法部分以EXCEL形式将所有数据输出，TextRank算法部分直接以窗 口形式输出排名前十位的数据。本程序的目的是在提取文本关键词的同时，比较TFDIF和TextRank算法的准确性和性能方面的差异。测试数据（附后）。二、概要设计抽象数据类型映射树

2、定义如下：ADT Map 数据对象 ID： ID 是类型为 char 的元素集合，即为一个单词中的单个字 符，称为字符集。数据对象 val ：val 是类型为 double 或 int 的元素集合，为每个单词对应 的 TF 值或 IDF 值，称为频率集。数据对象 is_end ：is_end 是类型为 bool 的元素集合，判断当前子结点是 否为单词末尾数据关系 R :R= IDVal IDVal= word num| word ID , num val，表示从 word 至U num 之间的一一映射 运算符重载：下标运算符 :运算对象为 string 值，返回对应 string 值的子树所代

3、表的 val 值。算术运算符 = ：运算对象为 double 或 int 值，等式左值的 val 值 替换为等式右值，并返回当前子树。算术运算符 +-*/ :运算对象为 double 或 int 值，对其 val 值进行运算，并返回当前子树。相等运算符 = 和!= : 运算对象为 val 值，判断其 val 值是否相等， 返回对应的 bool 值。基本操作：InitMap(&T);操作结果：构造空树。DestroyMap(&T);初始条件：树 T 存在。操作结果：构造空树。CreateMap(&T, word);初始条件：树 T 存在且 word 为 string 值。 操作结果：按照 wor

4、d 的字符顺序自上而下遍历，如果有字 符结点未创造，则构造新子结点，直到字符结束。MapEmpty(T);初始条件：树 T 存在。操作结果：若T为空树，则返回True，否则False。MapDepth(&T);初始条件：树T存在。操作结果：返回树的深度。Root(&T);初始条件：树T存在。操作结果：返回 T 的根。Value(&T, value);初始条件：树T存在，value为T中某个结点的值。 操作结果：返回 value 的值。Assign(&T, word, value);初始条件：树T存在，且word结点也存在。操作结果：结点 word 的 value 值替换为当前 value 。P

5、arent(&T, word);初始条件：树T存在，且word结点也存在。操作结果：返回 word 结点的双亲。InsertWord (&T, word);初始条件：树 T 存在。操作结果：往树加入 word 值，并将其 value 值默认初始化DeleteChild(&T, word);初始条件：树 T 存在，且 word 结点也存在。操作结果：将 word 对应子节点的 is_end 值改为 false 。TraverseMap(&T, visit() );初始条件：树 T 存在， visit 是对结点操作的应用函数。操作结果：按某种次序对 T 的每个结点调用 visit 一次且至 多一次

6、。一旦 visit 失败，则操作失败。ADT Map抽象数据类型图定义如下ADT Graph数据对象 n：n 是具有相同特征的数据元素集合，称为顶点集。 数据关系：DR=|v,w n且表示从v指向w的 弧基本操作：CreateGraph(&G, V, VR) ;初始条件：V是图的顶点集，VR是图中弧的集合操作结果：按V和VR的定义构造图GDestroyGraph(&G);初始条件：图G存在操作结果：销毁图 GLocateVex (G,u);初始条件：图G已存在，u和G中顶点有相同特征 操作结果：若G中存在顶点u,则返回该顶点在图中位置， 否则返回其它信息GetVex(G, v);初始条件：图G

7、存在，v是G中某个顶点 操作结果：返回 v 的值PutVex(&G, v, value);初始条件：图G存在，v是G中某个顶点操作结果：对 v 赋值 valueFirstAdjVex(G, v);初始条件：图G存在，v是G中某个顶点操作结果：返回v的第一个邻接顶点。若顶点在 G中没有邻 接顶点，则返回“空”NextAdjVex(G, v, w);初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点操作结果：返回v的(相对于w的)下一个邻接顶点。若 w是 v 的最后一个邻接点，则返回 空”InsertVex (&G,v);初始条件：图G存在，v和G中顶点有相同特征 操作结果：在图中增添新顶点

8、vDeleteVex (&G,v);初始条件：图G存在，v是G中某个顶点 操作结果：删除G中顶点v及其相关的弧InsertArc(&G, v, w)初始条件：图G存在，v和w是G中两个顶点 操作结果：在图G中增添弧v,w，若G是无向的，则还应 增添对称弧 w,vDeleteArc(&G, v, w)初始条件：图G存在，v和w是G中两个顶点操作结果：删除G中的弧vv,w，若G是无向的，则还应删 除对称弧DFSTraverse(G, v, visit()初始条件：图G存在，v是G中某个顶点，visit是对顶点 的应用函数操作结果：从顶点v起深度优先遍历图 G,并对每个顶点调 用函数 visit()

9、 一次且至多一次。一旦 visit() 失败，则操作失败BFSTraverse(G, v, visit()初始条件：图G存在，v是G中某个顶点，visit是对顶点 的应用函数操作结果：从顶点v起广度优先遍历图 G,并对每个顶点调 用函数 visit() 一次且至多一次。一旦visit() 失败，则操作失败ADT Graph本程序包含两大模块， TF-IDF 算法部分和 TextRank 算法部分主函数部分void mai n () TF-IDF 算法；TextRank 算法;TF-IDF 算法构建语料库（语料库的原料来源于超过八亿词的文本）导入语料库读入文本分析所读入的单词合并语料库输出到EX

10、CELTextRank 算法读入数据分析所读入的单词构造矩阵套用公式结果排序输出前十名各模块之间的调用关系如下:导入语料库分析所读入的单词读入文本f、合并语料库构造矩阵7套用公式fX输出到EXCEL结果排序输出前十名三、详细设计设计思路TF-IDF和TextRank关键词提取算法，进本程序以实现关键词抽取为目的，选取了 行两者的效率和准确性的比较研究。TFIDF 算法. TF-IDF算法简介TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一个词组 或短语的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。在一组文

11、档中，刻画某一文档特征的特征项可以根 据其在这组文档中出现的频率赋予相应的权重，只有在少数文档中出现的较特殊的词，权 重要比在多篇文档中出现的词的权重要高。TF-IDF加权的各种形式常被搜索引擎应用，作为文件与用户查询之间相关程度的度量或评级。. TF-IDF算法原理TF-IDF实际上是 TF和IDF的组合。TF即词频（Term Frequency），IDF即逆向文档）。频率（In verse Docume nt Freque ncyTF （词频）就是某个词在文章中出现的次数，此文章为需要分析的文本。为了统一标准，有如下两种计算方法TF （词频）某个词在文章中出现的次数该篇文章的总次数TF词频

12、_某个词在文章中出现的次数_ 该篇文章出现最多的单词的次数IDF （逆向文档频率）为该词的常见程度，需要构建一个语料库来模拟语言的使用环境。IDF逆向文档频率语料库的文档总数包含该词的文档总数+ 1【2】如果一个词越常见，那么其分母就越大，IDF值就越小。? ?=?司频 X?逆文档频率）之后，将每个单词的 TF-IDF值按从大到小降序排列，排在最前面的几个词即为关键!词。. TF-IDF算法实现. 构建映射Map类C+STL函数库中已经包含了 map的库函数，但为了使用起来更加方便、更便于个性化定制操作，于是使用自己定制的Map类模板。这个类函数主要是构建单词的stri ng 值与其TF、ID

13、F值的一一对应关系，方便直接用string 值下标访问其int值或double值，简化写代码的工作量。同时模板类中主要采取树形结构，建立一棵查找树，利用vector的空间动态分配的灵活性，从stri ng 的第一个字母开始一个一个往下找。每个Map类代表*一个字母，从根部开始向下遍历，利用bool值判断该处是否为一个单词结尾。代码如下：映射函数Map类Type为存储的 TF、IDF、TF-IDF值，如 int、double 等 旨在通过string类型下标访问其Type值template class Mappublic :/Type 值，类型为 int、doubleType val = NUL

14、L/*下标运算符重载中值为string类型如果该string值已存在，则返回对应val如果不存在则新建一个，返回初始值*/Type&operator (string item)Map&temp = find( item );/引用类函数find()查找到的值if (temp != NULL/找到，则返回对应val一个并返回新的值create( item); return find( item ).val;/*算术运算符=重载左值为找到的Map.val引用右值为对应的val值返回当前Map勺引用*Map&operator = (Typeitem ):*类函数列表find为查找函数，找到则返回其值

15、，没找到则新建一个返回初值create为创建新值得函数*/Mapfi nd( stri ng word);void create( stringword);private :/是否为单词结尾/代表当前类的字母/子节点集合bool is_e nd = false char ID;vector childs;/*find查找函数如果该string值已存在，则返回对应值如果不存在则新建一个，返回初始值*/template Map Map:fi nd(stri ng word)for ( auto &r : childs)/遍历类函数的所有子节点直到找到对应项if (r-ID = word0 & r-

16、is_end)/如果相等且为单词末尾return r-find(word.substr(1, word.size() - 1);/ 递归调用 find函数，一次减少一个字符return NULL/返回空类|/*create创建函数递归创建字母树*template vclass Typevoid Map:create( string word) return/如果找到，则减少第一个字符，继续递归向下遍历r-creat( word.substr(1, word.size() - 1);return ;Map*temp = n ewMap/没找到，则新建一个Maptemp-ID = word 0;/

17、将其所代表的字符ID设为当前word的第一个字符childs.push_back(temp);/子节点中增加这一 Maptemp-creat( word.substr(1, word.size() - 1);/ 继续递归创建后续字符return ;构建语料库为了使语料库更符合本程序的应用场景，语料库采用自己构建的语料库。语料库素材来源于小说新闻等，总词数超过8亿词。因为每篇文档有几十万字，为了使词语的ITF更具普遍性，假设每1000词为一篇文章。然后每次将文章先存入一个临时语料库中，进行分析处理后，将处理后的词加入临时语料库。之后再将临时语料库合并入总的语料库，流程图如下：定义语料库 定义临时

18、语料库 循环读入文件corpus r.first +;/合并语料库中对应数值/建立语料库/语料库，由字/文章总数，作为计算频mapstring , double corpus; 母string到岀现频率double的映射 longlongint times = 0;率的基数ofstreamoutput( corpus.csv);/输岀到excel表格中存储吠*导入制作好的语料库存在一一映射corpus中*/void buildCorpus() |ifstream input( corpus.csv );/ 打开文件stri ng item;/定义临时存储变量string和doubledoubl

19、e val;while (!input.eof()库映射中in put item val; corpus item = val; 丁/读入文件，存储到语料/*分析处理读入的string短语先删去字符前的不必要符号如数字、标点(等等将剩下的大写字符转化为小写|_保留字符中的标点，女口 Mr.Bill等再删除字符后的不必要标点，如.,:等等返回修改后的字符*/string analysis(string item )string temp =;bool flag = false ;个字母时，flag变为true，否则为false，滤过不必要的前缀for ( auto &r : item )/遍历s

20、tring中每一个字符if (r =,| r =;)continue ;/定义空字符/flag标记，当碰到第/滤过,;等符号if (r = a )/ 碰到字母标记 trueflag = true ;if (r = A )/ 转化大小写flag = true ;r += 32;if (flag)/如果已碰到字母，则在缓存string中加入该字符temp += r;if (temp.size() = 0)/如果是空字符，直接returnreturn temp;for ( auto i = temp.rbegin(); i= temp.rend(); i+)/从尾开始遍历string ,删去stri

21、ng中不必要的后缀 1if ( *i = a)/若碰到字母，则跳岀循break;temp.pop_back();/ 删去后缀return temp;/返回处理过的字符str ing/*遍历临时语料库的数值将其合并到总的语料库*/void print(mapstring , double &frequency )for ( auto &r : frequency )/ 遍历临时语料库if (corpus.find(r.first)= corpus.end()/ 第一次岀现则将在总语料库中新建一个，并将其初始化corpus r.first = 0.0;/*创建语料库通过文件读入文章由于部分文章为小

22、说，有几十万字，于是统一按每1000字为一篇文章语料库素材中所有文章的总次数大概有8亿词将该文章中出现的单词存入临时语料库中每一千字更新总语料库corpus，清空临时语料库frequency |最后计算每个单词的IDF值 */void readDictEn()int words = 0;/记录当前已读入的 word词数，每一千字更新一次maestri ng , double freque ncy;/ 临时语料库，存放string单词到double频率的一一映射Ion glo ngintent = 0;临时变量，记录临时语料库被清零多少次for ( int i = 1; i = 633; i+)

23、/ 遍历语料库素材 TXT文档，共有633个TXT文档，每篇文档平均12万词/*每篇文档的命名方式为EN(i),i为文档编号先利用stringstream流创建文件名的字符串再用ifstream流打开对应文件*/cout i : ;/输岀当前读入文件状态ostr in gstream out;/stri ngstream流，存储文件名字符串/打开文件/临时存储变量/读入文件/将读入字符串处理成所out EN ( i item;item = an alysis(item);需要求if (item.empty()/空字符串则略过continue ;if (frequency.find(item)=

24、 frequency.end()/ 女口果是新的字符串，则在语料库里新建一个并初始化frequency item = 0.0;frequency item +; words+;if (words = 1000)篇文章时，合并语料库并清空临时语料库pr in t(freque ncy); freque ncy.clear(); cn t+;words = 0;/增加岀现次数/读入一千词时，即读入for ( auto &r : corpus)r.sec ond /= (ent + 1);r.sec ond = abs(log(r.sec on d); output r.first r.second

25、 freque ncy;/打开文件/单词总数，包括相同的单词/这篇文章的语料库while (!file.eof()/循环读入文章中所有单过程类似/以下过程与构建语料库file item; item = an alysis(item);if (item.empty()continue ;if (idle.find(item)!= idle.end()continue ;if (frequency.find(item)= frequency.end()frequency item = 0.0;frequency item +; words+;/输岀数据到Exceloutput.open( data

26、.csv);for ( auto &r : frequency)r.sec ond /= words;r.second *= corpus r.first ;output r.first, r.second PageRank的基本思想主要是：一个网页的重要程度取决于链接到它的网页的数量以及这些网页的重要程度。比如有n个网页，对于其中一个网页？?，所有链接到？?的页面集合记为In ?所有?链接到的页面集 合记为Out ?，则其重要程度为：1Importanee ?=Importanee ?Out ?3n ?此处的求和号可以通过矩阵计算来模拟实现，并通过不断地迭代，重要性的值会不断 收敛为一常值，

27、最后可以求出最后的网页重要性。TextRank就是仿造这算法设计。【3】算法思路TextRank总体思路与PageRank类似。因为文本中不存在窗口与链接，所以要模拟造 出窗口。在这里不妨设 k个词为一个窗口，其中每个单词为一个链接，当一个窗口中的单 词与另一个窗口中的单词一样时，即视为两个窗口有链接。当然也可以脱离PageRa nk的思想来解释这一算法。对于一个句子，其中的一个单词 与这个句子的剩余单词都有关联性。同时，这个句子中的每一个单词又与另外其他句子中 相同的单词也有关联性。也就是说，一个单词的重要性不仅仅取决于单词的重要性，还与 该句子中其他单词的重要性相关。但为了使构造出来的矩阵

28、运算更为简便，在此将单词句子假定为长度为k，每个单词为k的第一个单词。这样，每k个单词就构成一个句子，句子与句子中任意两个单词之间就构成一条边，最后形成的图是一个无向图。为了加快运算速度，图采用邻接矩阵的方式 存储。而且，经过实际检验可以发现，该矩阵并不稀疏，所以直接转化为二维数组。每次 计算时就不断按照公式迭代。如此循环遍历下去，这样不仅得到的矩阵运算方便计算，而 且对结果的准确性也没有影响。迭代公式如下：Importanee ?1=1- ?+?Importanee ?Out ?In Word其中d是阻尼系数，一般设置为0.85。初始时，可以先设重要性为1。容易看出，经过多次迭代后，该重要性

29、的值会逐渐收敛为一常数。. TextRank算法实现TextRank所主要用到的主要是图的邻接矩阵存储，矩阵相乘合并等数据结构算法。流 程图如下：定义邻接矩阵阻尼向量读入文件正序遍历去除前缀构造结构体将矩阵结果信息转存到结构体中对其进行排序算法代码如下:ifstream EnF ile; ofstream output; str in gstream tempFile;set idle;mapstring , int EnMatr打印前十个结果 int EnRank = 0;con sti nt k = 8;int key1000010000;作为关键词抽取结果double d 510000;

30、double ans10000;/*读入文件并去除停用词仿造TF-IDF的方法，对读入的词进行分析处理将文章中处理过的词按照原来的顺序存入stringstream流tempFile中将每个词按照构造语料库的方法，存入语料库中构建单词图的邻接矩阵*/void scan( string namifstream stop( Stop.txt);while (!stop.eof()stri ng temp;stop temp;idle.i nsert(temp);EnFile.open( nam; stri ng temp;while (!EnFile.eof()keyEnMatr temp EnMa

31、tr r +;keyEnMatr temp EnMatr r +;EnF ile temp; temp = an alysis(temp);if (idle.find(temp)!= idle.end()continue ;if (temp =)continue ;if (EnMatr.find(temp)= EnMatr.end()EnMatr temp = EnRank+; tempFile temp /*读入文件并去除停用词仿造TF-IDF的方法，对读入的词进行分析处理将文章中处理过的词按照原来的顺序存入stringstream流tempFile中将每个词按照构造语料库的方法，存入语料库中构建单词图的邻接矩阵*/void build()stri ng bufferk;fc)r ( int i = 0; i bufferi;for ( int i = 0; !tempFile.eof(); i = (i + 1) % k)/ 将string 流中的数据读入循环数组中/为节省空间，数组只开k项，利用循环数组存储更新stri ng temp = bufferi;for ( auto &r : buffer)/ 构造邻接矩阵if (r = temp)con ti nuetempFile