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

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

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到num之间的一一映射运算符重载：下标运算符 : 运算对象为string值，返回对应string值的子 树所代表的val值。算术运算符 =：

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

4、到字符结束。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);初始条件：树

5、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失败，则操作失败。ADT Map2. 抽象数据类型图

6、定义如下ADT Graph  数据对象n：n是具有相同特征的数据元素集合，称为顶点集。 数据关系：DR = <v, w> | v, w n且 <v, w> 表示从v指向w的 弧  基本操作： CreateGraph (&G, V, VR) 初始条件：V是图的顶点集，VR是图中弧的集合 操作结果：按V和VR的定义构造图GDestroyGraph (&G);初始条件：图G存在 操作结果：销毁图G LocateVex (G, u);初始条件：图G已存在

7、，u和G中顶点有相同特征 操作结果：若G中存在顶点u，则返回该顶点在图中位置， 否则返回其它信息 GetVex (G, v); 初始条件：图G存在，v是G中某个顶点 操作结果：返回v的值 PutVex (&G, v, value); 初始条件：图G存在，v是G中某个顶点 操作结果：对v赋值value FirstAdjVex (G, v);初始条件：图G存在，v是G中某个顶点 操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻 接顶点，则返回“空” 

8、;NextAdjVex (G, v, w);初始条件：图G存在，v是G中某个顶点，w是v的邻接顶 点 操作结果：返回v的(相对于w的)下一个邻接顶点。若w是 v的最后一个邻接点，则返回"空” InsertVex (&G, v);初始条件：图G存在，v和G中顶点有相同特征 操作结果：在图中增添新顶点v DeleteVex (&G, v);初始条件：图G存在，v是G中某个顶点 操作结果：删除G中顶点v及其相关的弧 InsertArc (&G, v,

9、0;w) 初始条件：图G存在，v和w是G中两个顶点 操作结果：在图G中增添弧<v,w>，若G是无向的，则还应 增添对称弧<w,v> DeleteArc (&G, v, w) 初始条件：图G存在，v和w是G中两个顶点 操作结果：删除G中的弧<v,w>，若G是无向的，则还应删 除对称弧 DFSTraverse (G, v, visit() 初始条件：图G存在，v是G中某个顶点，visit是对顶点 的应用函数 操作结果：从顶点v起深度优先

10、遍历图G，并对每个顶点调用函数visit()一次且至多一次。一旦visit()失败，则操作失败 BFSTraverse (G, v, visit() 初始条件：图G存在，v是G中某个顶点，visit是对顶点 的应用函数 操作结果：从顶点v起广度优先遍历图G，并对每个顶点调 用函数visit()一次且至多一次。一旦 visit()失败，则操作失败  ADT Graph3. 本程序包含两大模块，TF-IDF算法部分和TextRank算法部分1）主函数部分void main () TF-IDF算法;TextRank算法;2）TF-

11、IDF算法i. 构建语料库（语料库的原料来源于超过八亿词的文本）ii. 导入语料库iii. 读入文本iv. 分析所读入的单词v. 合并语料库vi. 输出到EXCEL3）TextRank算法i. 读入数据ii. 分析所读入的单词iii. 构造矩阵iv. 套用公式v. 结果排序vi. 输出前十名各模块之间的调用关系如下：主程序模块读入数据构建语料库语料库的原料来源于超过八亿词的文本）分析所读入的单词导入语料库读入文本构造矩阵合并语料库套用公式输出到EXCEL结果排序输出前十名三、 详细设计1. 设计思路 本程序以实现关键词抽取为目的，选取了TF-IDF和TextRank关键词提取算法，进行两者的效

12、率和准确性的比较研究。2. TFIDF算法2.1 TF-IDF算法简介 TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一个词组或短语的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。在一组文档中，刻画某一文档特征的特征项可以根据其在这组文档中出现的频率赋予相应的权重，只有在少数文档中出现的较特殊的词，权重要比在多篇文档中出现的词的权重要高。TF-IDF加权的各种形式常被搜索引擎应用，作为文件与用户查询之间相关程度的度量或评级。2.2 TF-IDF算法原理TF-IDF实际上是TF和IDF的组合。TF即词频（Te

13、rm Frequency），IDF即逆向文档频率（Inverse Document Frequency）。TF（词频）就是某个词在文章中出现的次数，此文章为需要分析的文本。为了统一标准，有如下两种计算方法【2】：TF（词频） = 某个词在文章中出现的次数该篇文章的总次数和TF词频= 某个词在文章中出现的次数该篇文章出现最多的单词的次数IDF（逆向文档频率）为该词的常见程度，需要构建一个语料库来模拟语言的使用环境。IDF逆向文档频率= log语料库的文档总数包含该词的文档总数+1如果一个词越常见，那么其分母就越大，IDF值就越小。TF-IDF=TF词频×IDF（逆文档频率）之后，将每个

14、单词的TF-IDF值按从大到小降序排列，排在最前面的几个词即为关键词。2.3 TF-IDF算法实现2.3.1 构建一一映射Map类C+STL函数库中已经包含了map的库函数，但为了使用起来更加方便、更便于个性化定制操作，于是使用自己定制的Map类模板。这个类函数主要是构建单词的string值与其TF、IDF值的一一对应关系，方便直接用string值下标访问其int值或double值，简化写代码的工作量。同时模板类中主要采取树形结构，建立一棵查找树，利用vector的空间动态分配的灵活性，从string的第一个字母开始一个一个往下找。每个Map类代表一个字母，从根部开始向下遍历，利用bool值判

15、断该处是否为一个单词结尾。代码如下：/*一一映射函数Map类*Type为存储的TF、IDF、TF-IDF值，如int、double等*旨在通过string类型下标访问其Type值*/template<class Type>class Mappublic:Type val = NULL;/Type值，类型为int、double/*下标运算符重载*中值为string类型*如果该string值已存在，则返回对应val*如果不存在则新建一个，返回初始值*/Type& operator (string item)Map &temp = find(item);/引用类函数fin

16、d()查找到的值if (temp != NULL)/找到，则返回对应valreturn temp.val;else/未找到，则用create()函数创建一个并返回新的值create(item);return find(item).val;/*算术运算符=重载*左值为找到的Map.val引用*右值为对应的val值*返回当前Map的引用*/Map& operator =(Type item)val = item;return this;/*类函数列表*find为查找函数，找到则返回其值，没找到则新建一个返回初值*create为创建新值得函数*/Map find(string word);v

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

18、r->is_end)/如果相等且为单词末尾if (word.size() = 1)/大小为一说明已找到return this;/返回当前类return r->find(word.substr(1, word.size() - 1);/递归调用find函数，一次减少一个字符return NULL;/返回空类/*create创建函数*递归创建字母树*/template<class Type>void Map<Type>:create(string word)if (word.size() = 0)/如果大小为0，说明所有字母都已创建完毕is_end = true

19、;/标记单词结尾为truereturn;for (auto &r : childs)/遍历所有子节点if (r->ID = word0)/如果找到，则减少第一个字符，继续递归向下遍历r->creat(word.substr(1, word.size() - 1);return;Map *temp = new Map;/没找到，则新建一个Maptemp->ID = word0;/将其所代表的字符ID设为当前word的第一个字符childs.push_back(temp);/子节点中增加这一Maptemp->creat(word.substr(1, word.siz

20、e() - 1);/继续递归创建后续字符return;2.3.2 构建语料库为了使语料库更符合本程序的应用场景，语料库采用自己构建的语料库。语料库素材来源于小说新闻等，总词数超过8亿词。因为每篇文档有几十万字，为了使词语的ITF更具普遍性，假设每1000词为一篇文章。然后每次将文章先存入一个临时语料库中，进行分析处理后，将处理后的词加入临时语料库。之后再将临时语料库合并入总的语料库，流程图如下：正序遍历去除前缀逆序遍历去除后缀保留中间必要的符号全部读完后输出到文件保存每读入1000个字符将临时语料库与总语料库合并并清空临时语料库对读入的每一个单词进行处理使其前后都没有不必要的字符并将其转化为小

21、写定义语料库定义临时语料库循环读入文件 /建立语料库map<string, double> corpus;/语料库，由字母string到出现频率double的映射long long int times = 0;/文章总数，作为计算频率的基数ofstream output("corpus.csv");/输出到excel表格中存储/*导入制作好的语料库*存在一一映射corpus中*/void buildCorpus()ifstream input("corpus.csv");/打开文件string item;/定义临时存储变量string和dou

22、bledouble val;while (!input.eof()/读入文件，存储到语料库映射中input >> item >> val;corpusitem = val;/*分析处理读入的string短语*先删去字符前的不必要符号 如数字、标点"(<等等*将剩下的大写字符转化为小写*保留字符中的标点，如Mr.Bill等*再删除字符后的不必要标点，如.,"':等等*返回修改后的字符*/string analysis(string item)string temp = ""/定义空字符bool flag = false

23、;/flag标记，当碰到第一个字母时，flag变为true，否则为false，滤过不必要的前缀for (auto &r : item)/遍历string中每一个字符if (r = ',' | r = '')/滤过,;等符号continue;if (r <= 'z' && r >= 'a')/碰到字母标记trueflag = true;if (r <= 'Z' && r >= 'A')/转化大小写flag = true;r += 32;i

24、f (flag)/如果已碰到字母，则在缓存string中加入该字符temp += r;if (temp.size() = 0)/如果是空字符，直接returnreturn temp;for (auto i = temp.rbegin(); i <= temp.rend(); i+)/从尾开始遍历string，删去string中不必要的后缀if (*i <= 'z' && *i >= 'a')/若碰到字母，则跳出循环break;temp.pop_back();/删去后缀return temp;/返回处理过的字符string/*遍历

25、临时语料库的数值*将其合并到总的语料库*/void print(map<string, double> &frequency)for (auto &r : frequency)/遍历临时语料库if (corpus.find(r.first) = corpus.end()/第一次出现则将在总语料库中新建一个，并将其初始化corpusr.first = 0.0;corpusr.first+;/合并语料库中对应数值/*创建语料库*通过文件读入文章*由于部分文章为小说，有几十万字，于是统一按每1000字为一篇文章*语料库素材中所有文章的总次数大概有8亿词*将该文章中出现的单

26、词存入临时语料库中*每一千字更新总语料库corpus，清空临时语料库frequency*最后计算每个单词的IDF值*/void readDictEn()int words = 0;/记录当前已读入的word词数，每一千字更新一次map<string, double> frequency;/临时语料库，存放string单词到double频率的一一映射long long int cnt = 0;/临时变量，记录临时语料库被清零多少次for (int i = 1; i <= 633; i+)/遍历语料库素材TXT文档，共有633个TXT文档，每篇文档平均12万词/*每篇文档的命名方

27、式为"EN(i)",i为文档编号*先利用stringstream流创建文件名的字符串*再用ifstream流打开对应文件*/cout << i << ":"/输出当前读入文件状态ostringstream out;/stringstream流，存储文件名字符串out << "EN (" << i << ").txt"ifstream file(out.str();/打开文件string item;/临时存储变量while (!file.eof()/读入文件

28、file >> item;item = analysis(item);/将读入字符串处理成所需要求if (item.empty()/空字符串则略过continue;if (frequency.find(item) = frequency.end()/如果是新的字符串，则在语料库里新建一个并初始化frequencyitem = 0.0;frequencyitem+;/增加出现次数words+;if (words = 1000)/读入一千词时，即读入一篇文章时，合并语料库并清空临时语料库print(frequency);frequency.clear();cnt+;words = 0;

29、for (auto &r : corpus)/打印每个单词的IDF值r.second /= (cnt + 1);r.second = abs(log(r.second);output << r.first << " " << r.second << endl;2.3.3 计算TF-IDF值 计算TF值时，只需要将所抽取的文章对象全部遍历一遍，对每个词计算其词频，再将词频乘以对应的IDF值，按照从大到小排序即可输出结果。/*提取关键词*对读入文章的每一个单词计算TF值*再分别计算TF-IDF值*将每个单词的结果输出到ex

30、cel表格中*/void extract(string name)ifstream file(name);/打开文件string item;long long int words = 0;/单词总数，包括相同的单词map<string, double> frequency;/这篇文章的语料库while (!file.eof()/循环读入文章中所有单词/以下过程与构建语料库过程类似file >> item;item = analysis(item);if (item.empty()continue;if (idle.find(item) != idle.end()cont

31、inue;if (frequency.find(item) = frequency.end()frequencyitem = 0.0;frequencyitem+;words+;output.open("data.csv");for (auto &r : frequency)/输出数据到Excelr.second /= words;r.second *= corpusr.first;output << r.first << "," << r.second << endl;3TextRank算法3.1

32、算法简介TextRank也是一种用于文本排序的算法，它主要运用了矩阵迭代的代数知识来对每个文本词语进行分析，最后得出数值越高则越重要。其思想来源于网页排序算法PageRank。PageRank的基本思想主要是：一个网页的重要程度取决于链接到它的网页的数量以及这些网页的重要程度。比如有n个网页，对于其中一个网页Webi，所有链接到Webi的页面集合记为InWebi，所有Webi链接到的页面集合记为OutWebi，则其重要程度为：ImportanceWebi=WebjInWebj1OutWebjImportanceWebi此处的求和号可以通过矩阵计算来模拟实现，并通过不断地迭代，重要性的值会不断收

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

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

35、看出，经过多次迭代后，该重要性的值会逐渐收敛为一常数。3.3 TextRank算法实现对读入的每一个单词进行处理使其前后都没有不必要的字符并将其转化为小写去除停用词TextRank所主要用到的主要是图的邻接矩阵存储，矩阵相乘合并等数据结构算法。流程图如下：对读入的每一个单词进行处理使其前后都没有不必要的字符并将其转化为小写正序遍历去除前缀逆序遍历去除后缀保留中间必要的符号设置迭代次数进行矩阵迭代运算将处理好的词存入string流中将单词存入语料库中构造单词图的邻接矩阵定义邻接矩阵阻尼向量读入文件 打印前十个结果作为关键词抽取结果构造结构体将矩阵结果信息转存到结构体中对其进行排序算法代码如下：i

36、fstream EnFile;ofstream output;stringstream tempFile;set<string> idle;map<string, int> EnMatr;int EnRank = 0;const int k = 8;int key1000010000;double d1510000;double ans10000;/*读入文件并去除停用词*仿造TF-IDF的方法，对读入的词进行分析处理*将文章中处理过的词按照原来的顺序存入stringstream流tempFile中*将每个词按照构造语料库的方法，存入语料库中*构建单词图的邻接矩阵*/v

37、oid scan(string name)ifstream stop("Stop.txt");while (!stop.eof()string temp;stop >> temp;idle.insert(temp);EnFile.open(name);string temp;while (!EnFile.eof()EnFile >> temp;temp = analysis(temp);if (idle.find(temp) != idle.end()continue;if (temp = "")continue;if (EnMa

38、tr.find(temp) = EnMatr.end()EnMatrtemp = EnRank+;tempFile << temp << " "/*读入文件并去除停用词*仿造TF-IDF的方法，对读入的词进行分析处理*将文章中处理过的词按照原来的顺序存入stringstream流tempFile中*将每个词按照构造语料库的方法，存入语料库中*构建单词图的邻接矩阵*/void build()string bufferk;for (int i = 0; i < k; i+)tempFile >> bufferi;for (int i =

39、 0; !tempFile.eof(); i = (i + 1) % k)/将string流中的数据读入循环数组中/为节省空间，数组只开k项，利用循环数组存储更新string temp = bufferi;for (auto &r : buffer)/构造邻接矩阵if (r = temp)continue;keyEnMatrtempEnMatrr+;tempFile >> bufferi;/*矩阵相乘运算*套用求TextRank公式*/void multiple()double temp10000;const size_t size = EnMatr.size();for

40、(int i = 0; i < size; i+)/矩阵相乘double sum = 0;for (int j = 0; j < size; j+)sum += keyij * ansj;tempi = sum * 0.85;for (int i = 0; i < size; i+)/向量相加ansi = tempi + 0.15;/*设置迭代次数*对每个单词进行迭代操作*/void solve(int times)/迭代times次const int size = EnMatr.size();for (int i = 0; i <= size; i+)ansi = 1

41、.0;for (int i = 0; i < times; i+)multiple();/*结果输出排序时需要用到的结构体变量*/struct sortAnspublic:double ans;/TextRank值string item;/对应单词值out10000;/*排序时用到的比较函数*/bool compare(const sortAns a, const sortAns b)return a.ans > b.ans;/*将map中的值转移到结构体进行排序*输出排在前十位的词作为关键词*/void printAns()const int size = EnMatr.size

42、();int i = 0;for (auto &r : EnMatr)outi.item = r.first;outi+.ans = ansr.second;sort(out, out + size, compare);for (int i = 0; i < 10; i+)cout << outi.item << endl;四、 调试分析1. 考虑到程序的健壮性与运行效率，本次程序的一一映射关系采用了C+ STL的map和set库。2. 为了使数据更直观地呈现出来，本程序将TFIDF算法的输出数据直接输入到EXCEL中，更加方便后期的数据分析。3. 从程序

43、运行结果可以看出，TF-IDF算法和TextRank算法的准确性相差不算太大，但其时间与空间复杂度却存在差异。4. 从时间复杂度上来看，TF-IDF因为要构建语料库，其中需要不断用到字符串查找匹配等操作，耗费大量时间，光构建语料库的过程就要花费大约两个多小时的时间。而且之后的试验中还要再读取现有的庞大语料库，要花很多时间，时间主要花在文件读取转存的过程中，不过计算速度较快，但总体来看时间复杂度较高。TextRank因为只需要对单词进行迭代计算，对于大部分文本来说，速度较快。但对于长文本来说，两者的时间复杂度可能就比较接近。总之，一般情况下，处理短文章时TF-IDF要的时间复杂度远高于TextR

44、ank算法的时间复杂度，但处理较长的文章时，TF-IDF算法和TextRank算法的时间复杂度差不多，甚至TF-IDF算法会快于TextRank算法。5. 从空间复杂度上来看，TF-IDF显然要花不少存储空间，在读入文章的过程中，其占用内存空间接近0.5G。TextRank因为要存图链接矩阵，其空间复杂度也不低，但其空间复杂度与文中特异的单词数有关，大部分情况下其内存较TF-IDF低，但如果文章很长且其中生僻字词较多，内存也会以平方的速度增长，甚至会出现不够用的情况。所以，两者在内存方面要求都较高，空间复杂度都极其高。6. 总的来说，TFIDF算法和TextRank算法的差距并不大，其空间与时

45、间复杂度也较为接近，在实际应用中，可以将这两种做法结合在一起，相辅相成。从中也明显感受到，算法对解决问题的重要性，能将一个很实际的问题转化成抽象代数，从而通过计算而获得结论。五、 用户手册1. 本程序由Visual Studio 2015 professional编译，IDE要求以上。2. 进入程序后输入想要读入的文档名字，带上后缀名即可读入文件，若不在同一目录下要加上地址。3. TFIDF算法的结果将全部输出到EXCEL中，TextRank算法的结果将选取前十名输出到控制台窗口中六、 测试结果第一组测试数据：When I was a kid, I thought I would grow up to be an actress. I thought I would live in New York City, in a high-rise apartment building, with my husband and family of, oh, five or six kids. I thought I'd live an urban, impossibly sophisticated1 life. Money would