深入理解并行编程设计（并行编程应用计算文章相似度）

今天给大家介绍下并行编程在实际场景中的应用

给定一篇文章A，从备选的1000份文章中找出和文章A相似度最高的一篇。如果相似度大于50%，则认为该文章有抄袭嫌疑，将文章提取出来进行人工筛查。而且效率要足够高。

这里请大家暂停10分钟，思考下如果换做是你，你将如何实现这个需求。

我来讲下方法，如果大家有更好的想法，小豆君希望大家在评论区讨论。每个人积极交换思想，才能碰撞出更亮的火花。

在数据分析中，有个叫做余弦相似度的概念

其公式为：

余弦相似度公式

其中，a·b表示向量点积

向量点积

||a||*||b||表示：

距离乘积

举例：

• 文章A内容：中国人民都爱喝牛奶
• 文章B内容：我们中国百姓都喜欢喝牛奶
• 文章C内容：外国人不喜欢牛奶

然后将三篇文章做成一个矩阵表格，其中每个单元格的数字表示这个字在文章中出现的次数

字矩阵

那么

• A·B=6 (A和B对应每列相乘再求和)
• sqrt(A^2)=3
• sqrt(B^2)=3.46
• cos(A,B)=6/(3*3.46)=0.58

你可以尝试求一下cos(A,C)，我这里就不给答案了，你可以将答案写到评论区。

故文章A与B的余弦相似度为0.58

解释：

余弦相似度实际上是两个向量之间的夹角余弦值，夹角越小越相似。在用点积除以距离时，实际上是将它们进行了归一化处理，这时我们就不需要考虑向量的长度了。

在取点积时，如果乘数中有0，则相当于是将彼此间互不包含的字符去掉了，这会使得整个分子变小，而分子变小，余弦值减小，角度增大，其相似度也就增大了。当余弦值为0时，角度为90度，说明它们之间不包含任何相同的文字了。

通过上面的解释，你应该已经弄懂了什么是余弦相似度了。接下来我们用代码实现之

上代码：

#include <QDebug> //获取字符串a和字符串b每个字的出现次数 QMap<QString, QList<int> > get_dict(const QString& a, const QString& b) { QMap<QString, QList<int> > dict; QList<int> empty_list; //空的一位列表，索引0为a的字符次数，索引1为b的字符次数 empty_list.append(0); empty_list.append(0); //找到所有的字，并初始化为空列表 foreach (const QString& v, a b) { if (!dict.contains(v)) { dict[v] = empty_list; } } //计算a中字符出现次数 foreach (const QString& v, a) { if (dict.contains(v)) { dict[v][0] =1; } } //计算b中字符出现次数 foreach (const QString& v, b) { if (dict.contains(v)) { dict[v][1] = 1; } } return dict; } double cos_ab(const QString& a, const QString& b) { int ab = 0; //点积 int a_distance2 = 0; //a距离平方 int b_distance2 = 0; //b距离平方 QMap<QString, QList<int> > dict = get_dict(a, b); QMapIterator<QString, QList<int> > i(dict); while (i.hasNext()) { i.next(); const QList<int>& v = i.value(); ab = v[0]*v[1]; a_distance2 = v[0]*v[0]; b_distance2 = v[1]*v[1]; } double s_a = sqrt(a_distance2); double s_b = sqrt(b_distance2); return ab/(s_a*s_b); } int main() { double result = cos_ab(QString("中国人民都爱喝牛奶"), QString("我们中国百姓都喜欢喝牛奶")); qDebug() << result; }

以上，我们已经解决了比较文章相似度的问题了，但需求是需要从1000篇文章中进行筛选，所以我们要充分发挥计算机的资源，尽快找出相似度最高的文章，所以需要用到多线程。

在Qt中，QtConcurrent提供了并行处理方案。

上代码：

#include <QApplication> #include <QDebug> #include <QTextStream> #include <QFile> #include <QDir> #include <qtconcurrentmap.h> // 查找指定目录下的所有文件，并指定过滤条件，返回文件路径列表 QStringList find_files(const QString &startDir, QStringList filters) { QStringList names; QDir dir(startDir); foreach (QString file, dir.entryList(filters, QDir::Files)) names = startDir '/' file; foreach (QString subdir, dir.entryList(QDir::AllDirs | QDir::NoDotAndDotDot)) names = find_files(startDir '/' subdir, filters); return names; } // 读取文件中的所有内容 QString read_file(const QString& file) { QFile f(file); f.open(QIODevice::ReadOnly); return f.readAll(); } // 余弦函数代理，用于在mappedReduced中计算余弦相似度 double cos_ab_proxy(const QString& file) { static QString src = read_file("./src.txt"); // 存放原始文件内容，"中国人民都爱喝牛奶" QString compare = read_file(file); // 读取被比较的文件内容 double res = cos_ab(src, compare); qDebug() <<QString("原字符串[%1] 被比较字符串[%2] 相似度[%3]").arg(src).arg(compare).arg(res); return res; } // 对计算后的余弦相似度进行处理，找出最大的余弦相似度 void reduce(double &result, double calc_result) { if (result < calc_result) { result = calc_result; } } int main(int argc, char** argv) { QApplication app(argc, argv); // 查找files目录下的所有txt文件，并返回文件路径列表。1.txt (我们中国百姓都喜欢喝牛奶) 2.txt (外国人不喜欢牛奶) QStringList files = find_files("./files/", QStringList() << "*.txt"); double result = QtConcurrent::mappedReduced(files, cos_ab_proxy, reduce); qDebug() << "最高相似度为：" << result; }

输出结果：

并行计算结果

使用QtConcurrent编写的程序可以根据可用的处理器内核数自动调整线程数来加快计算速度，那么当部署到核数更多的机器上时，计算速度将自动提高。

QtConcurrent::mappedReduced函数，第一个参数是一个序列，它会将序列中的每一个元素分别传递给cos_ab_proxy函数作为参数，然后将cos_ab_proxy的结果传递给reduce，作为reduce的入参。reduce的结果将是整个函数的返回值。

你可以尝试增加文本和文件数量，当数量越来越多时，就会体现出并行计算的优势。

此处小豆君计算文本之间的相似度，是很初级的。因为中国是汉字，这里只计算的汉字之间的相似度，实际应计算词语相似度，过滤掉特殊符号，标点符号等。还需要处理同一种词语或词义的不同形式。这个留给后面我们进行探索。

最后留一个问题，本代码中，并没有返回是哪篇文章相似度最高，大家可以思考下应该怎么做。

喜欢本文的大家就点个赞吧，同时也欢迎关注

知乎号：小豆君编程分享

小豆君编程分享（关注后，可加入小豆君交流群进行学习交流，也可第一时间看到最新文章）