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

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

二、 概要设计
1. 抽象数据类型映射树定义如下：
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值。
算术运算符 =：运算对象为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失败，则操作失败。
}ADT Map
2. 抽象数据类型图定义如下
ADT Graph { 
数据对象n：n是具有相同特征的数据元素集合，称为顶点集。 
数据关系：DR = { <v, w> | v, w ∈ n且 <v, w> 表示从v指向w的
弧 } 
基本操作： 
CreateGraph (&G, V, VR) ;
初始条件：V是图的顶点集，VR是图中弧的集合 
操作结果：按V和VR的定义构造图G
DestroyGraph (&G);
初始条件：图G存在 
操作结果：销毁图G 
LocateVex (G, u);
初始条件：图G已存在，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中没有邻
接顶点，则返回“空” 
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, 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起深度优先遍历图G，并对每个顶点调
用函数visit()一次且至多一次。一旦visit()失败，则操作失败 
BFSTraverse (G, v, visit()) 
初始条件：图G存在，v是G中某个顶点，visit是对顶点
的应用函数 
操作结果：从顶点v起广度优先遍历图G，并对每个顶点调
用函数visit()一次且至多一次。一旦
visit()失败，则操作失败 
} ADT Graph
3. 本程序包含两大模块，TF-IDF算法部分和TextRank算法部分
1）主函数部分
void main () {
TF-IDF算法;
TextRank算法;
}
2）TF-IDF算法
i. 构建语料库（语料库的原料来源于超过八亿词的文本）
ii. 导入语料库
iii. 读入文本
iv. 分析所读入的单词
v. 合并语料库
vi. 输出到EXCEL
3）TextRank算法
i. 读入数据
ii. 分析所读入的单词
iii. 构造矩阵
iv. 套用公式
v. 结果排序
vi. 输出前十名
各模块之间的调用关系如下：
主程序模块

读入数据
构建语料库
语料库的原料来源于超过八亿词的文本）

分析所读入的单词
导入语料库

读入文本

构造矩阵

合并语料库

套用公式

输出到EXCEL

结果排序

输出前十名

三、 详细设计
1. 设计思路
本程序以实现关键词抽取为目的，选取了TF-IDF和TextRank关键词提取算法，进行两者的效率和准确性的比较研究。
2. TFIDF算法
2.1． TF-IDF算法简介
TF-IDF是一种统计方法，用以评估一字词对于一个文件集或一个语料库中的其中一个词组或短语的重要程度。字词的重要性随着它在文件中出现的次数成正比增加，但同时会随着它在语料库中出现的频率成反比下降。在一组文档中，刻画某一文档特征的特征项可以根据其在这组文档中出现的频率赋予相应的权重，只有在少数文档中出现的较特殊的词，权重要比在多篇文档中出现的词的权重要高。TF-IDF加权的各种形式常被搜索引擎应用，作为文件与用户查询之间相关程度的度量或评级。
2.2． TF-IDF算法原理
TF-IDF实际上是TF和IDF的组合。TF即词频（Term Frequency），IDF即逆向文档频率（Inverse Document Frequency）。
TF（词频）就是某个词在文章中出现的次数，此文章为需要分析的文本。为了统一标准，有如下两种计算方法【2】：
TF（词频） = 某个词在文章中出现的次数该篇文章的总次数
和
TF词频= 某个词在文章中出现的次数该篇文章出现最多的单词的次数
IDF（逆向文档频率）为该词的常见程度，需要构建一个语料库来模拟语言的使用环境。
IDF逆向文档频率= log语料库的文档总数包含该词的文档总数+1
如果一个词越常见，那么其分母就越大，IDF值就越小。
TF-IDF=TF词频×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值
*
*********************************************************************/
template<class Type>
class Map
{
public:
Type val = NULL; //Type值，类型为int、double

/*********************************************************************
*
* 下标运算符[]重载
* []中值为string类型
* 如果该string值已存在，则返回对应val
* 如果不存在则新建一个，返回初始值
*
*********************************************************************/
Type& operator [](string item)
{
Map &temp = find(item); //引用类函数find()查找到的值

if (temp != NULL) //找到，则返回对应val
{
return 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);
void 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 == word[0] && 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; //标记单词结尾为true
return;
}
for (auto &r : childs) //遍历所有子节点
{
if (r->ID == word[0]) //如果找到，则减少第一个字符，继续递归向下遍历
{
r->creat(word.substr(1, word.size() - 1));
return;
}
}
Map *temp = new Map; //没找到，则新建一个Map
temp->ID = word[0]; //将其所代表的字符ID设为当前word的第一个字符
childs.push_back(temp); //子节点中增加这一Map
temp->creat(word.substr(1, word.size() - 1)); //继续递归创建后续字符
return;
}
2.3.2． 构建语料库
为了使语料库更符合本程序的应用场景，语料库采用自己构建的语料库。语料库素材来源于小说新闻等，总词数超过8亿词。因为每篇文档有几十万字，为了使词语的ITF更具普遍性，假设每1000词为一篇文章。然后每次将文章先存入一个临时语料库中，进行分析处理后，将处理后的词加入临时语料库。之后再将临时语料库合并入总的语料库，流程图如下：

正序遍历去除前缀
逆序遍历去除后缀
保留中间必要的符号
全部读完后
输出到文件保存
每读入1000个字符
将临时语料库与总语料库合并
并清空临时语料库
对读入的每一个单词进行处理
使其前后都没有不必要的字符
并将其转化为小写
定义语料库
定义临时语料库
循环读入文件

//建立语料库
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和double
double val;

while (!input.eof()) //读入文件，存储到语料库映射中
{
input >> item >> val;
corpus[item] = val;
}
}

/*********************************************************************
*
* 分析处理读入的string短语
* 先删去字符前的不必要符号 如数字、标点"([{<等等
* 将剩下的大写字符转化为小写
* 保留字符中的标点，如Mr.Bill等
* 再删除字符后的不必要标点，如.,"':等等
* 返回修改后的字符
*
*********************************************************************/
string analysis(string item)
{
string temp = ""; //定义空字符
bool flag = false; //flag标记，当碰到第一个字母时，flag变为true，否则为false，滤过不必要的前缀
for (auto &r : item) //遍历string中每一个字符
{
if (r == ',' || r == ';') //滤过,;等符号
{
continue;
}
if (r <= 'z' && r >= 'a') //碰到字母标记true
{
flag = true;
}
if (r <= 'Z' && r >= 'A') //转化大小写
{
flag = true;
r += 32;
}
if (flag) //如果已碰到字母，则在缓存string中加入该字符
{
temp += r;
}
}
if (temp.size() == 0) //如果是空字符，直接return
{
return temp;
}
for (auto i = temp.rbegin(); i <= temp.rend(); i++) //从尾开始遍历string，删去string中不必要的后缀
{
if (*i <= 'z' && *i >= 'a') //若碰到字母，则跳出循环
{
break;
}
temp.pop_back(); //删去后缀
}
return temp; //返回处理过的字符string
}

/*********************************************************************
*
* 遍历临时语料库的数值
* 将其合并到总的语料库
*
*********************************************************************/
void print(map<string, double> &frequency)
{
for (auto &r : frequency) //遍历临时语料库
{
if (corpus.find(r.first) == corpus.end()) //第一次出现则将在总语料库中新建一个，并将其初始化
{
corpus[r.first] = 0.0;
}
corpus[r.first]++; //合并语料库中对应数值
}
}

/*********************************************************************
*
* 创建语料库
* 通过文件读入文章
* 由于部分文章为小说，有几十万字，于是统一按每1000字为一篇文章
* 语料库素材中所有文章的总次数大概有8亿词
* 将该文章中出现的单词存入临时语料库中
* 每一千字更新总语料库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万词
{
/*********************************************************************
*
* 每篇文档的命名方式为"EN(i)",i为文档编号
* 先利用stringstream流创建文件名的字符串
* 再用ifstream流打开对应文件
*
*********************************************************************/
cout << i << ":"; //输出当前读入文件状态
ostringstream out; //stringstream流，存储文件名字符串
out << "EN (" << i << ").txt";
ifstream file(out.str()); //打开文件

string item; //临时存储变量
while (!file.eof()) //读入文件
{
file >> item;
item = analysis(item); //将读入字符串处理成所需要求

if (item.empty()) //空字符串则略过
{
continue;
}

if (frequency.find(item) == frequency.end())//如果是新的字符串，则在语料库里新建一个并初始化
{
frequency[item] = 0.0;
}

frequency[item]++; //增加出现次数
words++;
if (words == 1000) //读入一千词时，即读入一篇文章时，合并语料库并清空临时语料库
{
print(frequency);
frequency.clear();
cnt++;
words = 0;
}
}
}

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值
* 将每个单词的结果输出到excel表格中
*
*********************************************************************/
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())
{
continue;
}

if (frequency.find(item) == frequency.end())
{
frequency[item] = 0.0;
}

frequency[item]++;
words++;
}

output.open("data.csv");
for (auto &r : frequency) //输出数据到Excel
{
r.second /= words;
r.second *= corpus[r.first];
output << r.first << "," << r.second << endl;
}
}
3．TextRank算法
3.1．算法简介
TextRank也是一种用于文本排序的算法，它主要运用了矩阵迭代的代数知识来对每个文本词语进行分析，最后得出数值越高则越重要。
其思想来源于网页排序算法PageRank。PageRank的基本思想主要是：一个网页的重要程度取决于链接到它的网页的数量以及这些网页的重要程度。比如有n个网页，对于其中一个网页Webi，所有链接到Webi的页面集合记为InWebi，所有Webi链接到的页面集合记为OutWebi，则其重要程度为：
ImportanceWebi=Webj∈InWebj1OutWebjImportanceWebi
此处的求和号可以通过矩阵计算来模拟实现，并通过不断地迭代，重要性的值会不断收敛为一常值，最后可以求出最后的网页重要性。TextRank就是仿造这算法设计。【3】
3.2．算法思路
TextRank总体思路与PageRank类似。因为文本中不存在窗口与链接，所以要模拟造出窗口。在这里不妨设k个词为一个窗口，其中每个单词为一个链接，当一个窗口中的单词与另一个窗口中的单词一样时，即视为两个窗口有链接。
当然也可以脱离PageRank的思想来解释这一算法。对于一个句子，其中的一个单词与这个句子的剩余单词都有关联性。同时，这个句子中的每一个单词又与另外其他句子中相同的单词也有关联性。也就是说，一个单词的重要性不仅仅取决于单词的重要性，还与该句子中其他单词的重要性相关。
但为了使构造出来的矩阵运算更为简便，在此将单词句子假定为长度为k，每个单词为k的第一个单词。这样，每k个单词就构成一个句子，句子与句子中任意两个单词之间就构成一条边，最后形成的图是一个无向图。为了加快运算速度，图采用邻接矩阵的方式存储。而且，经过实际检验可以发现，该矩阵并不稀疏，所以直接转化为二维数组。每次计算时就不断按照公式迭代。如此循环遍历下去，这样不仅得到的矩阵运算方便计算，而且对结果的准确性也没有影响。
迭代公式如下：
ImportanceWordi=1-d + d *Wordj∈InWord1OutWordjImportanceWordi
其中d是阻尼系数，一般设置为0.85。初始时，可以先设重要性为1。容易看出，经过多次迭代后，该重要性的值会逐渐收敛为一常数。
3.3． TextRank算法实现
对读入的每一个单词进行处理
使其前后都没有不必要的字符
并将其转化为小写
去除停用词
TextRank所主要用到的主要是图的邻接矩阵存储，矩阵相乘合并等数据结构算法。流程图如下：
对读入的每一个单词进行处理
使其前后都没有不必要的字符
并将其转化为小写
正序遍历去除前缀
逆序遍历去除后缀
保留中间必要的符号
设置迭代次数
进行矩阵迭代运算
将处理好的词存入string流中
将单词存入语料库中
构造单词图的邻接矩阵
定义邻接矩阵
阻尼向量
读入文件

打印前十个结果
作为关键词抽取结果

构造结构体
将矩阵结果信息转存到结构体中
对其进行排序

算法代码如下：
ifstream EnFile;
ofstream output;
stringstream tempFile;
set<string> idle;
map<string, int> EnMatr;
int EnRank = 0;
const int k = 8;
int key[10000][10000];
double d15[10000];
double ans[10000];

/*********************************************************************
*
* 读入文件并去除停用词
* 仿造TF-IDF的方法，对读入的词进行分析处理
* 将文章中处理过的词按照原来的顺序存入stringstream流tempFile中
* 将每个词按照构造语料库的方法，存入语料库中
* 构建单词图的邻接矩阵
*
*********************************************************************/
void 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 (EnMatr.find(temp) == EnMatr.end())
{
EnMatr[temp] = EnRank++;
}

tempFile << temp << " ";
}
}

/*********************************************************************
*
* 读入文件并去除停用词
* 仿造TF-IDF的方法，对读入的词进行分析处理
* 将文章中处理过的词按照原来的顺序存入stringstream流tempFile中
* 将每个词按照构造语料库的方法，存入语料库中
* 构建单词图的邻接矩阵
*
*********************************************************************/
void build()
{
string buffer[k];
for (int i = 0; i < k; i++)
{