首页
登录 | 注册

TextRank算法自动摘要的Java实现

http://www.hankcs.com/nlp/textrank-algorithm-java-implementation-of-automatic-abstract.html

上次写过《TextRank算法提取关键词的Java实现》,这次用TextRank实现文章的自动摘要。

所谓自动摘要,就是从文章中自动抽取关键句。何谓关键句?人类的理解是能够概括文章中心的句子,机器的理解只能模拟人类的理解,即拟定一个权重的评分标准,给每个句子打分,之后给出排名靠前的几个句子。

TextRank公式

TextRank的打分思想依然是从PageRank的迭代思想衍生过来的,如下公式所示:

等式左边表示一个句子的权重(WS是weight_sum的缩写),右侧的求和表示每个相邻句子对本句子的贡献程度。与提取关键字的时候不同,一般认为全部句子都是相邻的,不再提取窗口。

求和的分母wji表示两个句子的相似程度,分母又是一个weight_sum,而WS(Vj)代表上次迭代j的权重。整个公式是一个迭代的过程。

相似程度的计算

而相似程度wji的计算,推荐使用BM25

BM25算法,通常用来作搜索相关性平分。一句话概况其主要思想:对Query进行语素解析,生成语素qi;然后,对于每个搜索结果D,计算每个语素qi与D的相关性得分,最后,将qi相对于D的相关性得分进行加权求和,从而得到Query与D的相关性得分。

测试用例

算法可大致分为基本算法、数据结构的算法、数论算法、计算几何的算法、图的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法、厄米变形模型、随机森林算法。

算法可以宽泛的分为三类,

一,有限的确定性算法,这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务,但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。

二,有限的非确定算法,这类算法在有限的时间内终止。然而,对于一个(或一些)给定的数值,算法的结果并不是唯一的或确定的。

三,无限的算法,是那些由于没有定义终止定义条件,或定义的条件无法由输入的数据满足而不终止运行的算法。通常,无限算法的产生是由于未能确定的定义终止条件。

断句

  1. 算法可大致分为基本算法、数据结构的算法、数论算法、计算几何的算法、图的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法、厄米变形模型、随机森林算法
  2. 算法可以宽泛的分为三类
  3. 有限的确定性算法
  4. 这类算法在有限的一段时间内终止
  5. 他们可能要花很长时间来执行指定的任务
  6. 但仍将在一定的时间内终止
  7. 这类算法得出的结果常取决于输入值
  8. 有限的非确定算法
  9. 这类算法在有限的时间内终止
  10. 然而
  11. 对于一个(或一些)给定的数值
  12. 算法的结果并不是唯一的或确定的
  13. 无限的算法
  14. 是那些由于没有定义终止定义条件
  15. 或定义的条件无法由输入的数据满足而不终止运行的算法
  16. 通常
  17. 无限算法的产生是由于未能确定的定义终止条件

分词并过滤停用词

  1. [算法, 大致, 分, 基本, 算法, 数据, 结构, 算法, 数论, 算法, 计算, 几何, 算法, 图, 算法, 动态, 规划, 数值, 分析, 加密, 算法, 排序, 算法, 检索, 算法, 随机, 化, 算法, 并行, 算法, 厄, 米, 变形, 模型, 随机, 森林, 算法]
  2. [算法, 宽泛, 分为, 三类]
  3. []
  4. [有限, 确定性, 算法]
  5. [类, 算法, 有限, 一段, 时间, 终止]
  6. [可能, 花, 长, 时间, 执行, 指定, 任务]
  7. [一定, 时间, 终止]
  8. [类, 算法, 得出, 常, 取决, 输入, 值]
  9. [二]
  10. [有限, 非, 确定, 算法]
  11. [类, 算法, 有限, 时间, 终止]
  12. []
  13. [一个, 定, 数值]
  14. [算法, 唯一, 确定]
  15. [三]
  16. [无限, 算法]
  17. [没有, 定义, 终止, 定义, 条件]
  18. [定义, 条件, 无法, 输入, 数据, 满足, 终止, 运行, 算法]
  19. [通常]
  20. [无限, 算法, 产生, 未, 确定, 定义, 终止, 条件]

计算BM25相关性矩阵

  1. [15.176530737482341, -2.604484103028904, 0.0, -2.8740684265166565, -2.1930693258940175, 0.0, 0.0, -2.0325355810136103, 0.0, -2.604484103028904, -2.3811362523642052, 0.0, 2.509043358515279, -2.8740684265166565, 0.0, -3.2059044218809922, 0.0, -0.22517864251663589, 0.0, -1.8939010965185548]
  2. [-0.2864022115473306, 8.52437122545896, 0.0, -0.23950570220972142, -0.18275577715783484, 0.0, 0.0, -0.1693779650844675, 0.0, -0.21704034191907534, -0.19842802103035043, 0.0, 0.0, -0.23950570220972142, 0.0, -0.267158701823416, 0.0, -0.1477475757866994, 0.0, -0.15782509137654627]
  3. [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
  4. [-0.2864022115473306, -0.21704034191907534, 0.0, 4.604672851367114, 1.060086217315166, 0.0, 0.0, -0.1693779650844675, 0.0, 1.2589559610532894, 1.1509940396671094, 0.0, 0.0, -0.23950570220972142, 0.0, -0.267158701823416, 0.0, -0.1477475757866994, 0.0, -0.15782509137654627]
  5. [-0.2864022115473306, -0.21704034191907534, 0.0, 1.3892676764009562, 7.063472116341414, 1.1518653539666401, 2.634590118176154, 1.2574519044179069, 0.0, 1.2589559610532894, 5.005270773642655, 0.0, 0.0, -0.23950570220972142, 0.0, -0.267158701823416, 0.8333088661764476, 0.4727261064071153, 0.0, 0.504969645305668]
  6. [0.0, 0.0, 0.0, 0.0, 1.2428419944730007, 14.795434933306574, 1.6287733786106775, 0.0, 0.0, 0.0, 1.3494220606974598, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
  7. [0.0, 0.0, 0.0, 0.0, 2.010334451736872, 1.1518653539666401, 5.849995293142312, 0.0, 0.0, 0.0, 2.1827309268739077, 0.0, 0.0, 0.0, 0.0, 0.0, 0.8333088661764476, 0.6204736821938147, 0.0, 0.6627947366822143]
  8. [-0.2864022115473306, -0.21704034191907534, 0.0, -0.23950570220972142, 1.356767982871274, 0.0, 0.0, 12.127555522767913, 0.0, -0.21704034191907534, 1.4731177860712878, 0.0, 0.0, -0.23950570220972142, 0.0, -0.267158701823416, 0.0, 1.4000446911370572, 0.0, -0.15782509137654627]
  9. [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 4.054814792796337, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
  10. [-0.2864022115473306, -0.21704034191907534, 0.0, 1.3892676764009562, 1.060086217315166, 0.0, 0.0, -0.1693779650844675, 0.0, 6.001094704342757, 1.1509940396671094, 0.0, 0.0, 1.7780760396570634, 0.0, -0.267158701823416, 0.0, -0.1477475757866994, 0.0, 1.1716840594784514]
  11. [-0.2864022115473306, -0.21704034191907534, 0.0, 1.3892676764009562, 4.609944429081147, 1.1518653539666401, 2.634590118176154, 1.2574519044179069, 0.0, 1.2589559610532894, 5.005270773642655, 0.0, 0.0, -0.23950570220972142, 0.0, -0.267158701823416, 0.8333088661764476, 0.4727261064071153, 0.0, 0.504969645305668]
  12. [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
  13. [0.5551884973225691, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 8.939853708447595, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
  14. [-0.2864022115473306, -0.21704034191907534, 0.0, -0.23950570220972142, -0.18275577715783484, 0.0, 0.0, -0.1693779650844675, 0.0, 1.611294545577714, -0.19842802103035043, 0.0, 0.0, 4.9934812146232215, 0.0, -0.267158701823416, 0.0, -0.1477475757866994, 0.0, 1.1716840594784514]
  15. [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 4.054814792796337, 0.0, 0.0, 0.0, 0.0, 0.0]
  16. [-0.2864022115473306, -0.21704034191907534, 0.0, -0.23950570220972142, -0.18275577715783484, 0.0, 0.0, -0.1693779650844675, 0.0, -0.21704034191907534, -0.19842802103035043, 0.0, 0.0, -0.23950570220972142, 0.0, 2.531575358765468, 0.0, -0.1477475757866994, 0.0, 1.4955384555950606]
  17. [0.0, 0.0, 0.0, 0.0, 0.7674924572638717, 0.0, 1.0058167395654765, 0.0, 0.0, 0.0, 0.8333088661764476, 0.0, 0.0, 0.0, 0.0, 0.0, 9.892547495751218, 4.354323965031352, 0.0, 4.651322189247207]
  18. [0.26878628577523855, -0.21704034191907534, 0.0, -0.23950570220972142, 0.5847366801060369, 0.0, 1.0058167395654765, 1.6050126003722507, 0.0, -0.21704034191907534, 0.6348808451460972, 0.0, 0.0, -0.23950570220972142, 0.0, -0.267158701823416, 4.866735958438866, 12.008153881124132, 0.0, 3.1639879470156633]
  19. [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 4.054814792796337, 0.0]
  20. [-0.2864022115473306, -0.21704034191907534, 0.0, -0.23950570220972142, 0.5847366801060369, 0.0, 1.0058167395654765, -0.1693779650844675, 0.0, 1.611294545577714, 0.6348808451460972, 0.0, 0.0, 1.7780760396570634, 0.0, 2.531575358765468, 4.866735958438866, 2.9619596282988065, 0.0, 10.38451854500608]

迭代投票

  1.         for (int _ = 0; _ < max_iter; ++_)
  2.         {
  3.             double[] m = new double[D];
  4.             double max_diff = 0;
  5.             for (int i = 0; i < D; ++i)
  6.             {
  7.                 m[i] = 1 - d;
  8.                 for (int j = 0; j < D; ++j)
  9.                 {
  10.                     if (== i || weight_sum[j] == 0) continue;
  11.                     m[i] += (* weight[j][i] / weight_sum[j] * vertex[j]);
  12.                 }
  13.                 double diff = Math.abs(m[i] - vertex[i]);
  14.                 if (diff > max_diff)
  15.                 {
  16.                     max_diff = diff;
  17.                 }
  18.             }
  19.             vertex = m;
  20.             if (max_diff <= min_diff) break;
  21.         }

排序输出结果

  1. 这类算法在有限的时间内终止
  2. 这类算法在有限的一段时间内终止
  3. 无限算法的产生是由于未能确定的定义终止条件

分别对应于原文

算法可大致分为基本算法、数据结构的算法、数论算法、计算几何的算法、图的算法、动态规划以及数值分析、加密算法、排序算法、检索算法、随机化算法、并行算法、厄米变形模型、随机森林算法。

算法可以宽泛的分为三类,

一,有限的确定性算法,这类算法在有限的一段时间内终止。他们可能要花很长时间来执行指定的任务,但仍将在一定的时间内终止。这类算法得出的结果常取决于输入值。

二,有限的非确定算法,这类算法在有限的时间内终止。然而,对于一个(或一些)给定的数值,算法的结果并不是唯一的或确定的。

三,无限的算法,是那些由于没有定义终止定义条件,或定义的条件无法由输入的数据满足而不终止运行的算法。通常,无限算法的产生是由于未能确定的定义终止条件

效果还行,对于三种算法的介绍,分别提取出了一句话概括语句,就我个人感觉来讲,如果我来人工选关键句,大概也就这三句了。

开源项目地址

本文代码已集成到HanLP中开源:http://www.hankcs.com/nlp/hanlp.html

目前能够提供分词、词性标注、命名实体识别、关键字提取、短语提取、自动摘要、自动推荐,依存关系、句法树等功能。

本文网址:http://www.bnee.net/article/1353871.html

相关文章

  • 简易中文自动文摘系统(四):TextRank算法实现
    PageRank算法    PageRank是由拉里佩奇和谢尔盖布林于1996年在斯坦福大学开发的,适用于新兴搜索引擎的内核算法部分之一.谢尔盖布林认为,互联网中的所有页面都适用于一种特殊的层次结构:在一个页面中有越多的指向其他网页的链接, ...
  • (算法)组合的递归算法Java实现过程
    (算法)组合的递归算法Java实现过程 一.无重复项的组合  对于无重复项的组合问题的递归思路可从以下几个步骤入手(以数组为例,如对其他元素排列,将元素编号放入数组即可):  以数组a[5]={1,2,3,4,5}为例,用C(5,num)表 ...
  • [toc] 选择排序 程序代码 package com.uplooking.bigdata.datastructure; import java.util.Arrays; public class SelectSort { public s ...
  • 源码和说明如下:https://github.com/liuluyeah/TextRank4ZH-master
  • Java垃圾回收之标记清除算法详解
    Java垃圾回收之标记清除算法详解java垃圾回收算法之-引用计数器,这个算法其中一个优点便是,实时性,只要对象的引用计数器的值为0,则立刻回收.接下来介绍的标记清除算法,当对象的引用计数器的值为0时,不会立刻被回收的.概念介绍root对象 ...
  • "作为一名C++程序员,我们早已掌握了面向对象程序设计的基本概念,而且Java的语法无疑是非常熟悉的.事实上,Java本来就是从C++衍生出来的." 然而,C++和Java之间仍存在一些显著的差异.可以这样说,这些差异代 ...
  • 1 java 是运行在jvm上的,之所以说它的可移植性强,是因为jvm可以安装到任何的系统   c++不是不能在其他系统运行,而是c++在不同的系统上运行,需要不同的编码(这一点不如java,只编写一次代码,到处运行) 2 java 在we ...
  • Textrank学习
    TextRankTextRank 公式在 PageRank 公式的基础上,为图中的边引入了权值的概念:wijwij 就是是为图中节点 ViVi 到 VjVj 的边的权值 .dd 依然为阻尼系数,代表从图中某一节点指向其他任意节点的概率,一般 ...

2019 bnee小站 webmaster#bnee.net
12 q. 0.035 s.
湘ICP备19013596号-2