TextRank算法的基本原理及textrank4zh使⽤实例
TextRank算法是⼀种⽂本排序算法，由⾕歌的⽹页重要性排序算法PageRank算法改进⽽来，它能够从⼀个给定的⽂本中提取出该⽂本的关键词、关键词组，并使⽤抽取式的⾃动⽂摘⽅法提取出该⽂本的关键句。其提出论⽂是： Mihalcea R, Tarau P. TextRank: Bringing order into texts[C]. Association for Computational Linguistics, 2004. 论⽂的百度学术下载地址为：。本⽂将⾸先介绍TextRank算法的基本原理，然后给出Python中TextRank算法的中⽂⽂本实现模块textrank4zh的使⽤实例。
1 TextRank算法的基本原理
TextRank算法是由⽹页重要性排序算法PageRank算法迁移⽽来：PageRank算法根据万维⽹上页⾯之间的链接关系计算每个页⾯的重要性；TextRank算法将词视为“万维⽹上的节点”，根据词之间的共现关系计算每个词的重要性，并将PageRank中的有向边变为⽆向边。所以，在介绍TextRank算法之前，先介绍⼀下PageRank算法。
1.1 PageRank算法的基本概念和原理
PageRank算法的起源要从搜索引擎的发展讲起。早期的搜索引擎普遍采⽤分类⽬录⽅法，即通过⼈⼯对⽹页进⾏分类，整理出⾼质量的⽹站。随着⽹页的增多，⼈⼯分类的⽅法变得不现实，⼈们开始尝试
使⽤⽂本检索的⽅法，即通过计算⽤户查询的关键词与⽹页内容的相关程度来返回搜索结果。这种⽅法突破了⽹页数量的限制，但是这种⽅法的效果并不总是很好，因为某些⽹站会刻意“操作”某些关键词从⽽使⾃⼰的搜索排名靠前。这⼀问题在1998年4⽉的第七届国际万维⽹⼤会上得以解决——Larry Page和Sergey Brin提出了PageRank算法。该算法通过计算⽹页链接的数量和质量来粗略估计⽹页的重要性，算法创⽴之初即应⽤在⾕歌的搜索引擎中，对⽹页进⾏排名。
PageRank算法的核⼼思想如下：
如果⼀个⽹页被很多其他⽹页链接到，说明这个⽹页⽐较重要，即该⽹页的PR值（PageRank值）会相对较⾼；
如果⼀个PR值很⾼的⽹页链接到⼀个其他⽹页，那么被链接到的⽹页的PR值会相应地因此⽽提⾼。
以投票机制的观点来看，⼀个⽹页的得票数由所有链向它的⽹页的得票数经过递归算法来得到，有到⼀个⽹页的超链接相当于对该⽹页投了⼀票。
为了便于理解，考虑以下情境：
1）如上左图，假设⼀个只由4个⽹页组成的集合：A、B、C和D，如果⽹页B、C、D都链向⽹页A，且⽹页B、C、D均没有链出，那么⽹页A的PR值将是⽹页B、C、D的PR值之和:
2）如上右图，继续假设在上述情境下，⽹页B有链接链向⽹页C，⽹页D有链接链向⽹页A、B、C，⼀个⽹页不能多次投票，所以⽹页B投给它链向的⽹页1/2票，⽹页D投给它链向的⽹页1/3票，计算此情境下⽹页A的PR值为：
即，在⼀个⽹页为其他⽹页投票时，根据链出总数平分该⽹页的PR值，将其作为该⽹页为其链向⽹页所投票数，即：
3）再抽象⼀下，建⽴⼀个简化模型，对于任意的⽹页i，它的PR值可以表⽰如下：
：⽹页i的PR值
：⽹页j的PR值
：所有链接到⽹页i的⽹页集合
：
⽹页j的对外链出数
以上讲的是PageRank算法的简单模型，但是简单模型并不适⽤于只链出⾃⼰的⽹页或⼏个⽹页的链出形成⼀个循环的情况，所以考虑更具普遍性的PageRank算法模型——随机浏览模型。
随机浏览模型的假设是这样的：假定⼀个⽹页浏览者从⼀个随机页⾯开始浏览，浏览者不断点击当前⽹页的链接开始下⼀次浏览。但是，浏览者会逐渐厌倦并开始随机浏览⽹页。随机浏览的⽅式更符合⽤户的真实浏览⾏为，避免了上述情况的发⽣，由此产⽣了随机浏览模型，随机浏览模型中每个⽹页的PR值通过以下公式计算：
：⽹页i的PR值
：⽹页j的PR值
：⽹页j的对外链出数
：所有链接到⽹页i的⽹页集合
：⽹络中⽹页的总数
：阻尼系数，即按照超链接进⾏浏览的概率，⼀般取经验值为0.85
：浏览者随机跳转到⼀个新⽹页的概率
⼀个⽹页的PR值是由其他⽹页的PR值计算得到的。由于PR=A*PR（A为概率转移矩阵）满⾜马尔科夫链的性质，那么通过迭代可以得到所有⽹页的PR值。经过重复计算，这些⽹页的PR值会趋于正常和稳定。
随着研究的深⼊，⽬前PageRank算法被⼴泛应⽤于众多⽅⾯，例如学术论⽂的重要性排名、学术论⽂作者的重要性排序、⽹络爬⾍、关键词与关键句的抽取等。
1.2 从PageRank算法到TextRank算法
TextRank算法是由PageRank算法改进⽽来的，⼆者的思想有相同之处，区别在于：PageRank算法根据⽹页之间的链接关系构造⽹络，⽽TextRank算法根据词之间的共现关系构造⽹络；PageRank算法构造的⽹络中的边是有向⽆权边，⽽TextRank算法构造的⽹络中的边是
⽆向有权边。TextRank算法的核⼼公式如下，其中⽤于表⽰两个节点之间的边连接具有不同的重要程度：
为了便于理解，给出使⽤TextRank算法提取关键词和关键词组的具体步骤如下：
1）将给定的⽂本按照整句进⾏分割，即；
谢娜和张杰年龄
2）对于每个句⼦，对其进⾏分词和词性标注，然后剔除停⽤词，只保留指定词性的词，如名词、动词、形容词等，即
，其中为句⼦i中保留下的词；
3）构建词图，其中V为节点集合，由以上步骤⽣成的词组成，然后采⽤共现关系构造任意两个节点之间的边：两个节点之间存在边仅当它们对应的词在长度为K的窗⼝中共现，K表⽰窗⼝⼤⼩，即最多共现K个单词，⼀般K取2；
4）根据上⾯的公式，迭代计算各节点的权重，直⾄收敛；
5）对节点的权重进⾏倒序排序，从中得到最重要的t个单词，作为top-t关键词；
6）对于得到的top-t关键词，在原始⽂本中进⾏标记，若它们之间形成了相邻词组，则作为关键词组提取出来。
从给定⽂本中提取关键句时，将⽂本中的每个句⼦分别看作⼀个节点，如果两个句⼦有相似性，则认为这两个句⼦对应的节点之间存在⼀条⽆向有权边，衡量句⼦之间相似性的公式如下：
：两个句⼦
：句⼦中的词
分⼦部分的意思是同时出现在两个句⼦中的同⼀个词的数量，分母是对句⼦中词的个数求对数后求和，这样设计可以遏制较长的句⼦在相似度计算上的优势。
根据以上相似度计算公式循环计算任意两个节点之间的相似度，设置阈值去掉两个节点之间相似度较低的边连接，构建出节点连接图，然后迭代计算每个节点的TextRank值，排序后选出TextRank值最⾼的⼏个节点对应的句⼦作为关键句。
1.3 textrank4zh模块源码解读
textrank4zh模块是针对中⽂⽂本的TextRank算法的python算法实现，该模块的下载地址为：
对其源码解读如下：
util.py：textrank4zh模块的⼯具包，TextRank算法的核⼼思想在该⽂件中实现。
# -*- encoding:utf-8 -*-
"""
@author:  letian
@homepage:
@github:  github/someus/
"""
from __future__ import (absolute_import, division, print_function,
unicode_literals)
import os
import math
import networkx as nx
import numpy as np
import sys
try:
reload(sys)
sys.setdefaultencoding('utf-8')
except:
pass
sentence_delimiters = ['?', '!', ';', '？', '！', '。', '；', '……', '…', '\n']
allow_speech_tags = ['an', 'i', 'j', 'l', 'n', 'nr', 'nrfg', 'ns', 'nt', 'nz', 't', 'v', 'vd', 'vn', 'eng']
PY2 = sys.version_info[0] == 2
if not PY2:
# Python 3.x and up
text_type = str
string_types = (str,)
xrange = range
def as_text(v):  ## ⽣成unicode字符串
if v is None:
return None
elif isinstance(v, bytes):
return v.decode('utf-8', errors='ignore')
elif isinstance(v, str):
return v
return v
else:
raise ValueError('Unknown type %r' % type(v))
def is_text(v):
return isinstance(v, text_type)
else:
# Python 2.x
text_type = unicode
string_types = (str, unicode)
xrange = xrange
def as_text(v):
if v is None:
return None
elif isinstance(v, unicode):
return v
elif isinstance(v, str):
return v.decode('utf-8', errors='ignore')
else:
raise ValueError('Invalid type %r' % type(v))
def is_text(v):
return isinstance(v, text_type)
__DEBUG = None
def debug(*args):
global __DEBUG
if __DEBUG is None:
try:
viron['DEBUG'] == '1':
__DEBUG = True
else:
__DEBUG = False
except:
__DEBUG = False
if __DEBUG:
print(' '.join([str(arg) for arg in args]))
class AttrDict(dict):
"""Dict that can get attribute by dot"""
def __init__(self, *args, **kwargs):
super(AttrDict, self).__init__(*args, **kwargs)
self.__dict__ = self
def combine(word_list, window=2):
"""构造在window下的单词组合，⽤来构造单词之间的边。
Keyword arguments:
word_list  --  list of str, 由单词组成的列表。
windows    --  int, 窗⼝⼤⼩。
"""
if window < 2: window = 2
for x in xrange(1, window):
if x >= len(word_list):
break
word_list2 = word_list[x:]
word_list2 = word_list[x:]
res = zip(word_list, word_list2)
for r in res:
yield r
def get_similarity(word_list1, word_list2):
"""默认的⽤于计算两个句⼦相似度的函数。
Keyword arguments:
word_list1, word_list2  --  分别代表两个句⼦，都是由单词组成的列表
"""
words = list(set(word_list1 + word_list2))
vector1 = [float(unt(word)) for word in words]
vector2 = [float(unt(word)) for word in words]
vector3 = [vector1[x] * vector2[x] for x in xrange(len(vector1))]
vector4 = [1 for num in vector3 if num > 0.]
co_occur_num = sum(vector4)
if abs(co_occur_num) <= 1e-12:
return 0.
denominator = math.log(float(len(word_list1))) + math.log(float(len(word_list2)))  # 分母
if abs(denominator) < 1e-12:
return 0.
return co_occur_num / denominator
def sort_words(vertex_source, edge_source, window=2, pagerank_config={'alpha': 0.85, }):
"""将单词按关键程度从⼤到⼩排序
Keyword arguments:
vertex_source  --  ⼆维列表，⼦列表代表句⼦，⼦列表的元素是单词，这些单词⽤来构造pagerank中的节点 edge_source    --  ⼆维列表，⼦列表代表句⼦，⼦列表的元素是单词，根据单词位置关系构造pagerank中的边 window          --  ⼀个句⼦中相邻的window个单词，两两之间认为有边
pagerank_config --  pagerank的设置
"""
sorted_words = []
word_index = {}
index_word = {}
_vertex_source = vertex_source
_edge_source = edge_source
words_number = 0
for word_list in _vertex_source:
for word in word_list:
if not word in word_index:
word_index[word] = words_number
index_word[words_number] = word
words_number += 1
graph = np.zeros((words_number, words_number))
for word_list in _edge_source:
for w1, w2 in combine(word_list, window):
if w1 in word_index and w2 in word_index:
index1 = word_index[w1]
index2 = word_index[w2]
graph[index1][index2] = 1.0
graph[index2][index1] = 1.0
debug('graph:\n', graph)
nx_graph = nx.from_numpy_matrix(graph)