首页
登录 | 注册

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年在斯坦福大学开发的,适用于新兴搜索引擎的内核算法部分之一.谢尔盖布林认为,互联网中的所有页面都适用于一种特殊的层次结构:在一个页面中有越多的指向其他网页的链接, ...
  • Floyd算法(三)之 Java详解
    前面分别通过C和C++实现了弗洛伊德算法,本文介绍弗洛伊德算法的Java实现. 目录 1. 弗洛伊德算法介绍 2. 弗洛伊德算法图解 3. 弗洛伊德算法的代码说明 4. 弗洛伊德算法的源码 转载请注明出处:http://www.cnblog ...
  • Dijkstra算法(三)之 Java详解
    前面分别通过C和C++实现了迪杰斯特拉算法,本文介绍迪杰斯特拉算法的Java实现. 目录 1. 迪杰斯特拉算法介绍 2. 迪杰斯特拉算法图解 3. 迪杰斯特拉算法的代码说明 4. 迪杰斯特拉算法的源码 转载请注明出处:http://www. ...
  • Prim算法(三)之 Java详解
    前面分别通过C和C++实现了普里姆,本文介绍普里姆的Java实现. 目录 1. 普里姆算法介绍 2. 普里姆算法图解 3. 普里姆算法的代码说明 4. 普里姆算法的源码 转载请注明出处:http://www.cnblogs.com/skyw ...
  • Kruskal算法(三)之 Java详解
    前面分别通过C和C++实现了克鲁斯卡尔,本文介绍克鲁斯卡尔的Java实现. 目录 1. 最小生成树 2. 克鲁斯卡尔算法介绍 3. 克鲁斯卡尔算法图解 4. 克鲁斯卡尔算法分析 5. 克鲁斯卡尔算法的代码说明 6. 克鲁斯卡尔算法的源码 转 ...
  • Java Stack 类栈是Vector的一个子类,它实现了一个标准的后进先出的栈.堆栈只定义了默认构造函数,用来创建一个空栈. 常用方法1 boolean empty() 测试堆栈是否为空. 2 Object peek( )查看堆栈顶部的 ...
  • [toc] 快速排序 程序代码 package com.uplooking.bigdata.datastructure; import java.util.Arrays; public class QuickSort { public st ...
  • [toc] 插入排序 程序代码 package com.uplooking.bigdata.datastructure; import java.util.Arrays; public class InsertSort { public s ...