文本关键词提取(TFIDF和TextRank)

基于关键词提取的TFIDF和TextRank方法的对比研究题目：开发一个程序，在该程序中，允许输入一段文本（以界面或者文件输入方式均可），该程序自动抽取出包含的关键词，并按照关键词的权重由高到低排序后输出。完成日期：2016.06.05一、需求分析1.以文本的形式读入数据，将每个单词抽象成一棵树，将单词与单词之间的关系抽象为图。2.TFIDF算法部分以EXCEL形式将所有数据输出，TextRank算法部分直接以窗口形式输出排名前十位的数据。3.本程序的目的是在提取文本关键词的同时，比较TFDIF和TextRank算法的准确性和性能方面的差异。4.测试数据（附后）。二、概要设计1.抽象数据类型映射树定义如下：ADTMap{数据对象ID：ID是类型为char的元素集合，即为一个单词中的单个字符，称为字符集。数据对象val：val是类型为double或int的元素集合，为每个单词对应的TF值或IDF值，称为频率集。数据对象is_end：is_end是类型为bool的元素集合，判断当前子结点是否为单词末尾数据关系R:R={IDVal}IDVal={word–num|wordID，numval，表示从word到num之间的一一映射}运算符重载：下标运算符[]:运算对象为string值，返回对应string值的子树所代表的val值。算术运算符=：运算对象为double或int值，等式左值的val值替换为等式右值，并返回当前子树。算术运算符+-*/:运算对象为double或int值，对其val值进行运算，并返回当前子树。相等运算符==和!=:运算对象为val值，判断其val值是否相等，返回对应的bool值。基本操作：InitMap(&T);操作结果：构造空树。DestroyMap(&T);初始条件：树T存在。操作结果：构造空树。CreateMap(&T,word);初始条件：树T存在且word为string值。操作结果：按照word的字符顺序自上而下遍历，如果有字符结点未创造，则构造新子结点，直到字符结束。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。Parent(&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一次且至多一次。一旦visit失败，则操作失败。}ADTMap2.抽象数据类型图定义如下ADTGraph{数据对象n：n是具有相同特征的数据元素集合，称为顶点集。数据关系：DR={v,w|v,w∈n且v,w表示从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存在，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中顶点有相同特征操作结果：在图中增添新顶点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中的弧v,w，若G是无向的，则还应删除对称弧DFSTraverse(G,v,visit())初始条件：图G存在，v是G中某个顶点，visit是对顶点的应用函数操作结果：从顶点v起深度优先遍历图G，并对每个顶点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败BFSTraverse(G,v,visit())初始条件：图G存在，v是G中某个顶点，visit是对顶点的应用函数操作结果：从顶点v起广度优先遍历图G，并对每个顶点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败}ADTGraph3.本程序包含两大模块，TF-IDF算法部分和TextRank算法部分1）主函数部分voidmain(){TF-IDF算法;TextRank算法;}2）TF-IDF算法i.构建语料库（语料库的原料来源于超过八亿词的文本）ii.导入语料库iii.读入文本iv.分析所读入的单词v.合并语料库vi.输出到EXCEL3）TextRank算法i.读入数据ii.分析所读入的单词iii.构造矩阵iv.套用公式v.结果排序vi.输出前十名各模块之间的调用关系如下：主程序模块构建语料库导入语料库分析所读入的单词读入数据三、详细设计1.设计思路本程序以实现关键词抽取为目的，选取了TF-IDF和TextRank关键词提取算法，进行两者的效率和准确性的比较研究。2.TFIDF算法2.1．TF-IDF算法简介TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一个词组或短语的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会读入文本合并语料库输出到EXCEL构造矩阵套用公式结果排序输出前十名随着它在语料库中出现的频率成反比下降。在一组文档中，刻画某一文档特征的特征项可以根据其在这组文档中出现的频率赋予相应的权重，只有在少数文档中出现的较特殊的词，权重要比在多篇文档中出现的词的权重要高。TF-IDF加权的各种形式常被搜索引擎应用，作为文件与用户查询之间相关程度的度量或评级。2.2．TF-IDF算法原理TF-IDF实际上是TF和IDF的组合。TF即词频（TermFrequency），IDF即逆向文档频率（InverseDocumentFrequency）。TF（词频）就是某个词在文章中出现的次数，此文章为需要分析的文本。为了统一标准，有如下两种计算方法【2】：（词频）某个词在文章中出现的次数该篇文章的总次数和(词频)某个词在文章中出现的次数该篇文章出现最多的单词的次数IDF（逆向文档频率）为该词的常见程度，需要构建一个语料库来模拟语言的使用环境。(逆向文档频率)(语料库的文档总数包含该词的文档总数)如果一个词越常见，那么其分母就越大，IDF值就越小。(词频)（逆文档频率）之后，将每个单词的TF-IDF值按从大到小降序排列，排在最前面的几个词即为关键词。2.3．TF-IDF算法实现2.3.1．构建一一映射Map类C++STL函数库中已经包含了map的库函数，但为了使用起来更加方便、更便于个性化定制操作，于是使用自己定制的Map类模板。这个类函数主要是构建单词的string值与其TF、IDF值的一一对应关系，方便直接用string值下标访问其int值或double值，简化写代码的工作量。同时模板类中主要采取树形结构，建立一棵查找树，利用vector的空间动态分配的灵活性，从string的第一个字母开始一个一个往下找。每个Map类代表一个字母，从根部开始向下遍历，利用bool值判断该处是否为一个单词结尾。代码如下：/***********************************************************************一一映射函数Map类*Type为存储的TF、IDF、TF-IDF值，如int、double等*旨在通过string类型下标访问其Type值**********************************************************************/templateclassTypeclassMap{public:Typeval=NULL;//Type值，类型为int、double/***********************************************************************下标运算符[]重载*[]中值为string类型*如果该string值已存在，则返回对应val*如果不存在则新建一个，返回初始值**********************************************************************/Type&operator[](stringitem){Map&temp=find(item);//引用类函数find()查找到的值if(temp!=NULL)//找到，则返回对应val{returntemp.val;}else//未找到，则用create()函数创建一个并返回新的值{create(item);returnfind(item).val;}}/***********************************************************************算术运算符=重载*左值为找到的Map.val引用*右值为对应的val值*返回当前Map的引用**********************************************************************/Map&operator=(Typeitem){val=item;returnthis;}/***********************************************************************类函数列表*find为查找函数，找到则返回其值，没找到则新建一个返回初值*create为创建新值得函数**********************************************************************/Mapfind(stringword);voidcreate(stringword);private:boolis_end=false;//是否为单词结尾charID;//代表当前类的字母vectorMap*childs;//子节点集合};/***********************************************************************find查找函数*如果该string值已存在，则返回对应值*如果不存在则新建一个，返回初始值****************************************