EricJJ' Blog

TextRank 提取摘要

2017-07-14

  1. 1. 预处理
  2. 2. 分析关系
  3. 3. 使用 PageRank 公式收敛结果

接上篇所述, 我们实现了提取一段句子的关键字, 接下来实现提取摘要,

我们可以接着根据 PageRank 算法, 按照我们划分出来的关键字生成权重, 语料:

程序员(英文Programmer)是从事程序开发、维护的专业人员。一般将程序员分为程序设计人员和程序编码人员,但两者的界限并不非常清楚,特别是在中国。软件从业人员分为初级程序员、高级程序员、系统分析员和项目经理四大类。

预处理

  1. 进行文本分段, 这里按照 ,|。 切分,, 实际情况因人而异;
  2. 去空白, 分词, 提取关键字, 结果如下:
[ 算法可大致分为基本算法、数据结构的算法、数论算法、计算几何的算法、图的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法、厄米变形模型、随机森林算法 ]:  算法,数值,分析,加密算法,规划
[ 算法可以宽泛的分为三类 ]:  算法,分为
[ 一 ]:
[ 有限的确定性算法 ]:  算法,确定性
[ 这类算法在有限的一段时间内终止 ]:  终止,算法,内,一段时间
[ 他们可能要花很长时间来执行指定的任务 ]:  长时间,执行,花,指定,任务
[ 但仍将在一定的时间内终止 ]:  终止,时间,内
[ 这类算法得出的结果常取决于输入值 ]:  输入,得出,取决于,算法,值
[ 二 ]:
[ 有限的非确定算法 ]:  算法,确定
[ 这类算法在有限的时间内终止 ]:  终止,算法,时间,内
[ 然而 ]:
[ 对于一个(或一些)给定的数值 ]:  给定,数值
[ 算法的结果并不是唯一的或确定的 ]:  算法,确定
[ 三 ]:
[ 无限的算法 ]:  算法,无限
[ 是那些由于没有定义终止定义条件 ]:  定义,终止,没有,条件
[ 或定义的条件无法由输入的数据满足而不终止运行的算法 ]:  输入,满足,数据,无法,终止
[ 通常 ]:
[ 无限算法的产生是由于未能确定的定义终止条件 ]:  未能,确定,定义,产生,算法

分析关系

两层 for-loop, 根据关键词生成每段话之间的关系, 代码

for sentence,kw in sentence_kw.items():
    temp = {}
    for sent_check, kw_check in sentence_kw.items():
      temp[sent_check] = len([word for word in kw if word in kw_check])
    cooc_dict[sentence] = temp

使用 PageRank 公式收敛结果

这次就更简单了, 和上一篇的提取关键字代码可以说是大同小异了,
这里祭出公式

while (iter_no > index and  error > err):
    error = 0
    TR_copy = TR.copy()
    for sent,cooc in graph.items():
        temp = 0
        for link_sent,weight in cooc.items():
          t = sum(graph[link_sent].values())
          t = 1 if t == 0 else t
          temp += TR[link_sent] * weight / t
        TR[sent] = 1 - d + d * temp
    error += (TR[sent] - TR_copy[sent])**2
    index += 1

对结果排个序, 取前三个:

这类算法在有限的一段时间内终止
这类算法在有限的时间内终止
算法可大致分为基本算法、数据结构的算法、数论算法、计算几何的算法、图的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法、厄米变形模型、随机森林算法

相关文章 :
http://www.hankcs.com/nlp/textrank-algorithm-to-extract-the-keywords-java-implementation.html
http://www.letiantian.me/2014-12-01-text-rank/