TextRank算法实现

TextRank算法主要用于文档的关键词抽取或者摘要抽取（本质是关键句抽取），原理就是PageRank的那一套思想，只不过构建图模型的时候稍有区别。

抽取关键词的时候，图的节点为词，边为滑动窗口中共现的词对，边的权重为两个词在滑动窗口中的共现次数。不是所有的词都考虑，一般只选取特定词性的词，如名词，形容词和动词。同时，滑动窗口也有一个长度，比如连续5个词。

抽取关键句的时候，图的节点为句子，边为文档中所有句子的两两组合，边的权重为两个句子的相似度，可分词后计算Jaccard相似度，或者更复杂点的提取语义向量计算余弦相似度，前者是原始论文[1]中的做法:

\begin{align*} Similarity(S_i,S_j)=\frac {|\{w_k|w_k\in S_i \& w_k\in S_j\}|}{log(|{S_i}|)+log(|S_j|)} \end{align*}

有了图模型，就可以迭代计算每个节点的权重，然后对节点进行排序。[1]中给出的公式为：

\begin{align*} WS(V_i) = (1 - d) + d * \sum_{V_j\in In(V_i)} \frac{w_{ji}}{\sum_{V_k\in Out(V_j)} w_{jk}}WS(V_j) \end{align*}

原始PageRank公式为：

\begin{align*} S(V_i) = (1 - d) + d * \sum_{j\in In(V_i)} \frac{1}{|Out(V_j)|}S(V_j) \end{align*}

可以看出主要区别为：在PageRank中边的权重都是1，而在TextRank中边的权重是变化的。

由于算法原理比较简单，实现起来也比较容易，用C++实现了一个版本，github地址为：https://github.com/lostfish/textrank

实现的关键是构建图。为了简化，同时原始论文中的实验也说明有向图和无向图得到的结果相差不大，所以这里构建的是无向加权图。

为节省空间，将词都映射为size_t类型的词ID。同时，用pair 表示边，用map, double> 存储边的权重。为计算方便，需要保留一个节点所有出度边的权重和，用map来表示。

核心rank的过程见text_rank.cpp中的函数CalcWordScore()，终止条件为两个：一个是两次迭代词权重的变化值小于预先设定的阈值，如0.0001，另一个是达到最大迭代次数，如100次。满足任一条件都终止继续迭代，实验中发现一般迭代几十次就会终止。

仅仅和tf抽取的结果做了对比，没和tf-idf作对比是因为idf先验的获取依赖具体应用。实验数据集为新闻长文档，发现text_rank的效果比按照tf排序的结果稍好。

具体实验数据待整理。

貌似在具体的应用上，现在还没有特别好的关键词抽取算法，就是那种比经典的tf-idf算法效果好很多的。在一般抽取关键词的场景下，根据具体应用的数据，整理一份idf先验词表，然后用tf-idf算法其实就可以了。当然候选词要精心筛选，至少有根据词性过滤。