共计 5578 个字符，预计需要花费 14 分钟才能阅读完成。
作者：LogM
本文原载于 https://segmentfault.com/u/logm/articles，不允许转载~
1. 源码来源
comoody 大佬的源码：https://github.com/comoody/TextRank.git
本文对应的源码版本：Commits on Oct 23, 2018, 9736be10593b99adc1ea614c5d83f1bfeca17b94
lostfish 大佬的源码：https://github.com/lostfish/textrank.git
本文对应的源码版本：Commits on Sep 29, 2016, e89084374ae0e08490c9cc0fa79f8ae4bb10ad5b
TextRank 论文地址：https://www.aclweb.org/anthology/W04-3252
2. 概述
C++ 版本的 TextRank 还没有发现点赞超级多的代码，这里我找了两个不同的实现来分析。
在上一篇博客：TextRank Python 版本，我们知道，看 TextRank 的源码有两个重点需要看，重点 1：句子与句子的相似度是如何计算的；重点 2：PageRank 的实现。
这里，考虑到篇幅，我直接给出对应的函数所在的位置。
3. comoody 大佬的源码
先看看大佬是怎么计算句子与句子之间的相似度的。配合我写的那几行中文注释，应该很容易看懂。大致和论文里的公式是一致的，但是分母和论文的公式不一样。具体为什么用这个分母，我就不得而知了。
// 文件：src/TextRanker.cpp
// 行数：153
float TextRanker::getSimilarity(std::string a, std::string b) const
{
// no two equivalent sentences should ever be compared, but this logic is included just in case
if(a == b)
return 0.f;
// 大小写转换 -> 分词 -> 把词放到 set 里
std::transform(a.begin(), a.end(), a.begin(), ::tolower);
std::vector<std::string> aWords = stringSplit(a, ' ');
std::set<std::string> aWordSet;
for(auto word : aWords)
aWordSet.insert(word);
std::transform(b.begin(), b.end(), b.begin(), ::tolower);
std::vector<std::string> bWords = stringSplit(b, ' ');
std::set<std::string> bWordSet;
for(auto word : bWords)
bWordSet.insert(word);
// 求两个 set 的交集，相当于两个句子共有的词语
std::vector<std::string> commonWords;
std::set_intersection
(aWordSet.begin(),
aWordSet.end(),
bWordSet.begin(),
bWordSet.end(),
std::back_inserter(commonWords)
);
// 这个分母和论文的公式不一样，论文里是带 log 的
float avgWords = (aWords.size() + bWords.size()) / 2;
return commonWords.size() / avgWords;}然后，我们来看看 PageRank 的实现。哦！看来 comoody 大佬没有使用 PageRank 的公式，而是在图中随机游走，某个点游走经过的次数越多，这个点得分越高。
讲道理，这种随机游走的效果和用 PageRank 的公式求得的效果是差不多的。了解 PageRank 的同学应该清楚，PageRank 这个算法的本质，就是模拟用户在网页间的随机游走。
// 文件：src/TextRanker.cpp
// 行数：77
// does a single walk that visits sentences around the graph according to probabilities defined in the similarity matrix
// after each iteration inside the walk, there is a 1 - kNewWalkThreshold probability that the walk will end and this
// method will return
// during the walk, the visits map is updated accoridingly
void TextRanker::doSentenceGraphWalk
(
const FloatMatrix& similarityMatrix,
const std::vector<std::string>& sentences,
std::map<std::string, int>& visits
) const
{const int kDim = sentences.size();
bool continueWalk = true;
// start walk at a random node in the sentence graph
int curSentenceIndex = rand() % kDim;
while (continueWalk)
{
// visit the curSentence
std::string curSentence = sentences[curSentenceIndex];
visits[curSentence]++;
// the row of the similarity matrix corresponding to the current sentence represents the probabilites
// of transferring to all ofther sentences from the current sentence
std::vector<float> probabilites;
std::copy_if
(similarityMatrix[curSentenceIndex].begin(),
similarityMatrix[curSentenceIndex].end(),
std::back_inserter(probabilites),
[](float f) {return f != 0.f;}
);
if (probabilites.size() == 0)
break; // no possible neighbor to visit
// normalize probabilites
float sum = std::accumulate(probabilites.begin(), probabilites.end(), 0.f);
std::transform(probabilites.begin(), probabilites.end(), probabilites.begin(), [sum](float probability)
{return probability / sum;});
// stack probabilites
std::vector<float> probabilityDistribution;
for(std::vector<float>::iterator j = probabilites.begin(); j < probabilites.end(); j++)
probabilityDistribution.push_back(std::accumulate(probabilites.begin(), j+1, 0.f));
// get a random number betweeon 0 and 1
float selector = (rand() % 1000) / 1000.f;
int selectedIndex = 0;
while(probabilityDistribution[selectedIndex] <= selector)
selectedIndex++;
// the selected index maps to a probability from a distribution with all 0 entries removed
// iterate through the original probabilites to map back the selected index to its true index from the list
int trueIndex = 0;
int nonZeroCount = 0;
do
{if(similarityMatrix[curSentenceIndex][trueIndex] != 0)
nonZeroCount++;
}
while((nonZeroCount < selectedIndex + 1) && ++trueIndex);
// update the curSentence index so that it can be visited in the next iter of the current walk
curSentenceIndex = trueIndex;
// randomly test for the end of a walk, if the random number is above kNkNewWalkThreshold, start a new walk
float newWalkSelector = (rand() % 1000) / 1000.f;
if(newWalkSelector > kNewWalkThreshold)
continueWalk = false;
}
}4. lostfish 大佬的源码
我们再来看看 lostfish 大佬的源码。同样的，先看看是如何计算句子与句子之间相似度的。
emmm. 也是和论文公式有些不一样：统计两个句子共同出现的词语时，没有对每个句子先做一次去重。
// 文件：src/sentence_rank.cpp
// 行数：47
double SentenceRank::CalcDist(const vector<string> &token_vec1, const vector<string> &token_vec2)
{
size_t both_num = 0;
size_t n1 = token_vec1.size();
size_t n2 = token_vec2.size();
if (n1 < 2 || n2 < 2)
return 0;
// 统计两句话共同出现的词语数
for (size_t i = 0; i < n1; ++i)
{const string &token = token_vec1[i];
for(size_t j = 0; j < n2; ++j)
{if (token == token_vec2[j])
{
both_num++;
break;
}
}
}
double dist = both_num / (log(n1) + log(n2) );
return dist;
}再来看看 PageRank 的实现吧。和论文里给出的公式一样。我写了一些注释，应该还是容易看懂的。
void SentenceRank::CalcSentenceScore(map<size_t, double> &score_map)
{score_map.clear();
// initialize
size_t n = m_sentence_vec.size();
for (size_t id = 0; id < n; ++id)
score_map.insert(make_pair(id, 1.0));
// iterate
for (size_t i = 0; i < m_max_iter_num; ++i)
{
double max_delta = 0;
map<size_t, double> new_score_map; // 这里记录了每个句子的得分
for (size_t id1 = 0; id1 < n; ++id1)
{
double new_score = 1 - m_d; // 当前迭代轮次中，每个句子的得分，这里先把论文公式的左边部分加上
// 计算论文公式的右边部分
double sum_weight = 0.0;
for (size_t id2 = 0; id2 < n; ++id2)
{if (id1 == id2 || m_out_sum_map[id2] < 1e-6)
continue;
double weight = GetWeight(id2, id1); // 节点 2 -> 节点 1 的权重
sum_weight += weight/m_out_sum_map.at(id2)*score_map[id2];
}
new_score += m_d * sum_weight; // 把论文公式的右边部分加上
new_score_map.insert(make_pair(id1, new_score));
// 监测每两轮迭代之间 score 的差值，差值足够小就不用继续迭代
double delta = fabs(new_score - score_map[id1]);
max_delta = max(max_delta, delta);
}
score_map = new_score_map;
if (max_delta < m_least_delta)
{break;}
}
}5. 总结
两位大佬实现的 TextRank C++ 版本，还是有一定的改进空间：
comoody 大佬使用的 节点随机游走 的方式可行，用在个人项目上是可以的；但是工程上来说，rand() 函数导致每次结果都是随机的，无法复现，是比较致命的。
lostfish 大佬的 PageRank 部分，和论文是一致的，但是运算过程还有一些优化空间。
另外，两位大佬计算句子与句子之间相似度的函数与论文有点不同，当然这个计算相似度的方法不是定死的，是可以自己创作的，比如用 word2vec 等等。
我打算自己也实现一个 C++ 的版本。
正文完
