做后台开发和算法落地的同学十有八九都遇到过这种需求给一段文本找出最像的另一段或者从一个库里筛出重复内容。这个能力背后的根基就是相似度判断。今天聊聊用C实现相似度判断这件事包括算法选择、代码实现和工程落地尽量把踩过的坑都摊开讲。适合正在写检索、推荐、去重模块的开发者也适合想系统了解相似度计算原理和C写法的初学者。1. 相似度判断到底在判断什么1.1 相似度的定义与生活化类比相似度判断本质上是把两个对象映射到一个可比较的度量空间然后用一个数值描述它们之间的接近程度。这个数值通常落在0到1之间1表示完全一致0表示毫无关系但具体范围取决于你选的算法。举个生活化的例子有两道菜都放了番茄和鸡蛋只是咸淡不同我们说它们相似度高一道番茄炒蛋和一道红烧肉几乎没交集相似度就低。工程里的对象不是菜而是文本、图片、用户行为序列、音频片段这些数据。数据必须被转换成计算机能算的形式最常见的就是向量。向量可以理解为高维空间里的一个点相似度就是点与点之间的距离远近。为什么需要这个东西因为很多业务用精确匹配根本做不了。两个网页内容可能只改了几个字你不能拿字符串等值比较去判断它们是重复的两个用户看过不同的商品但偏好方向一致你需要从行为向量里找出那种“味觉上很像”的感觉。所以相似度判断解决的从来不是“是不是同一个”的问题而是“有多像”的问题。这个细微的差别决定了算法选型和技术实现的走向。1.2 哪些场景需要相似度判断相似度判断的覆盖面比很多人想象中广我随便列几个高频场景你就知道它多常见。文本去重内容社区、新闻聚合、爬虫系统都会碰到大量重复或高度相似的稿件。直接用哈希做指纹只能对付完全相同的文本稍微改动就失效所以要用相似度来计算内容重合率。我之前在某个项目里处理过一批技术博客很多文章被人改了个标题和首段就发出来靠相似度判断能轻松揪出来。推荐系统用户画像会表示成高维向量商品也会表示成向量相似度用于计算“看了这个还喜欢那个”。这里常用的不是文本相似度而是用户行为向量的余弦相似度或协同过滤里的相似度计算。日志异常检测系统日志可以按时间段转换成模式向量对比当前时间片和历史正常时间片的相似度一旦相似度跌破阈值就告警。这个场景要求算法快因为日志量非常大。代码查重学生作业、开源代码重复度检测本质是对代码片段做特征提取后计算相似度。这比文本去重难点在于需要处理语法结构但底层仍然离不开相似度度量。图片查重指纹提取后的感知哈希向量之间的汉明距离或者深度网络特征向量的余弦距离都是相似度判断。这些场景有一个共同特点原始数据不能直接计算必须先经过特征化特征选得好不好直接决定相似度有没有意义。这也是后面所有内容的大前提。2. 常见相似度算法的选择逻辑2.1 余弦相似度向量空间的黄金标准余弦相似度是实战中出场率最高的算法没有之一。它的核心是计算两个向量之间的夹角余弦值公式是[ sim(a,b) \frac{a \cdot b}{||a|| \cdot ||b||} ]也就是向量的点积除以两个向量的模长乘积。它衡量的是方向一致性不看向量的绝对长度。这个特性非常契合很多业务场景文本向量里一篇文章的长短只会影响向量模长但主题方向往往由词项比例决定所以余弦相似度对文本特别友好。举个例子向量A是[1, 2, 3]向量B是[2, 4, 6]这俩是纯倍数关系欧氏距离会很大但余弦相似度是1.0因为方向完全一致。在实际文本检索里一篇短文和一篇长文讨论同一个话题它们词的分布比例相似余弦值就高这符合直觉。实现上也非常简单只需要一次循环累加点积和模长没有复杂分支。我建议所有刚接触相似度的人先把余弦相似度写熟它是最容易调试也最不容易出幺蛾子的算法。2.2 欧氏距离与曼哈顿距离几何视角的相似欧氏距离就是通常说的“直线距离”公式是[ d(a,b) \sqrt{\sum_{i1}^{n}(a_i - b_i)^2} ]曼哈顿距离则是两个点在各个维度上的绝对差之和城市街区的走法[ d(a,b) \sum_{i1}^{n}|a_i - b_i| ]这两种算法跟余弦相似度最大的差别是它们考虑数值的绝对差异。使用场景很典型如果你在比较坐标、图像像素值、传感器读数数值本身的大小有意义那欧氏距离就是合适的选择。比如判断两条用电曲线是否相似幅度差异本身就可能代表异常不能只比较趋势方向。但要注意欧氏距离和余弦相似度不是完全对立的。把向量归一化到单位长度后欧氏距离和余弦相似度在排序意义上是等价的所以有些系统会先把向量L2归一化再统一用余弦目的就是让两种度量保持一致。实际工程中我常用一个简单经验文本、推荐用余弦数值、坐标、时序信号优先看距离。2.3 杰卡德相似系数、汉明距离与编辑距离除了向量有些数据天然不是向量形态。集合类数据适合用杰卡德相似系数公式是交集大小除以并集大小[ J(A,B) \frac{|A \cap B|}{|A \cup B|} ]比如两个用户都有哪些标签两边共同标签占比越高相似度越高。杰卡德对稀疏集合表现得很好因为它无视了双方都不存在的元素。汉明距离一般用在等长编码序列上计算两个序列对应位置不同的个数。经典场景是图片感知哈希后得到的64位二进制指纹比较两张图就是统计指纹比特位不同的数量。这个算法极其快硬件层面可以并行比较位运算所以在大规模图片去重里非常实用。编辑距离Levenshtein距离解决的是字符串相似问题通过增删改操作把一个字符串变成另一个字符串的最小次数。它对拼写错误、OCR识别结果比对很有效但计算复杂度较高O(m*n)长文本慎用。如果只是想快速判断两个短字符串是否“差不多”编辑距离是个直观的选择。2.4 怎么选数据形态和业务目标说了算我总结了一张选型速查表自己平时也用数据类型推荐算法适合场景主要缺点高维稀疏向量余弦相似度文本、用户向量、推荐对共现结构不敏感连续数值向量欧氏距离坐标、图像像素、传感器量纲需要归一化集合杰卡德系数标签、权限、关键词集合忽略元素权重等长编码汉明距离图片指纹、二进制特征无法处理长度变化短字符串编辑距离拼写纠错、名称匹配长文本计算慢业务目标也很关键。你要的是排名还是绝对阈值推荐系统只看Top K排序余弦相似度够用去重系统需要设一个绝对相似度阈值切断那就要考虑算法对数值的实际分布是否稳定。有的算法对数据分布敏感比如欧氏距离在高维空间里区分度很差这时候余弦往往表现更好。我的建议是先想清楚你的数据长什么样、业务对距离的语义期待是什么再决定算法不要一上来就套余弦。3. C实现的代码级拆解3.1 从零写一个余弦相似度计算器先来一个最直接的实现输入是两个等长的vector 返回余弦相似度#include vector #include cmath #include stdexcept double cosineSimilarity(const std::vectordouble a, const std::vectordouble b) { if (a.size() ! b.size()) { throw std::invalid_argument(向量长度必须一致); } double dot 0.0; double normA 0.0; double normB 0.0; for (size_t i 0; i a.size(); i) { dot a[i] * b[i]; normA a[i] * a[i]; normB b[i] * b[i]; } if (normA 0.0 || normB 0.0) { return 0.0; } return dot / (std::sqrt(normA) * std::sqrt(normB)); }这个函数有几个细节值得说。一是先检查长度避免后面越界二是用 normA 和 normB 同时累加一遍循环就做完不额外开数组三是零向量直接返回0。零向量没有方向余弦公式里分母为零但工程里不能抛异常否则线上会炸。具体返回什么值看语义有的场景想当作完全不相同处理返回0最合理。如果向量是float或者你对精度要求不高也可以把double换成float速度会快一些尤其是批量计算时。但代价是数值稳定性稍差超大向量点积可能溢出可以考虑用long double做累加再转回double。3.2 文本特征表示从字符串到向量算法再好输入是字符串也没法直接算。最常见的做法是把文本转换成词频向量。下面是一个极其简化的英文分词版本#include unordered_map #include string #include sstream std::unordered_mapstd::string, size_t tokenize(const std::string text) { std::unordered_mapstd::string, size_t freq; std::istringstream stream(text); std::string word; while (stream word) { freq[word]; } return freq; }这只是按空白切分真实场景里要做更多清洗去掉标点、转小写、过滤停用词、甚至做词干化。中文就复杂一些需要分词组件但分词后得到的词频map是一样的。拿到map之后怎么转成向量通常有两种思路第一种是固定一个全局词表所有文档都用这个词表的下标做维度词表大小就是向量长度这是稠密向量第二种是只保留非零维度用稀疏结构存储比如vectorpairsize_t, double或者unordered_map这是稀疏向量。对于文本场景词表动辄几万维但每篇文章只含有几百个词用稠密向量存99.9%的零维度非常浪费所以工程上基本都用稀疏表示。稀疏结构的余弦计算不需要遍历全部维度只要对两个向量共同存在的维度做运算即可速度可以提升几个数量级。3.3 工程化封装、边界处理与性能优化写一个单独函数很容易但放到模块里就要考虑封装。我习惯把相似度计算放到一个独立的类里避免业务代码到处复制公式class SimilarityCalculator { public: enum class Metric { COSINE, EUCLIDEAN, JACCARD }; double calculate(const std::vectordouble a, const std::vectordouble b, Metric metric) const { switch (metric) { case Metric::COSINE: return cosineSimilarity(a, b); case Metric::EUCLIDEAN: return 1.0 / (1.0 euclideanDistance(a, b)); // 其他指标按需扩展 default: return 0.0; } } };这里我把欧氏距离转成了相似度用1/(1d)做映射将距离压到0到1区间。这么做是为了上层统一接口但不能滥用因为映射会改变原始距离的分布如果要严格排序不如直接返回距离让调用方自己比较。边界处理是工程里的重灾区。输入向量的维度不一致要抛异常空字符串、全零词频、只包含停用词的文本都会产生零向量计算前要识别。另一个容易踩的坑是浮点数相等比较别写if (normA 0.0)因为浮点数可能因为累计误差产生极小值比如1e-300它不等于0但接近0这时计算出来的相似度可能是一个病态值。更稳妥的做法是判断绝对值小于某个极小阈值比如normA 1e-12。性能优化方面几个方向值得优先考虑。第一用稀疏向量表示文本不存储零值。第二相似度计算循环里避免函数调用和动态内存分配提前用reserve预留容量。第三批量比较时可以用多线程并行比如按文档ID分片最后归并排序。第四如果机器支持SIMD可以用向量化指令同时计算多个维度的乘加不过那是进阶玩法大部分场景把算法复杂度降下来收益更高。4. 实操记录做一个文本相似度判断工具4.1 需求定义与接口设计这里我记录一个真实做过的简化版工具模拟项目叫“文章相似度检索X”。需求很简单给一批文档输入一个query返回最相似的Top N篇。数据量大概十万篇每篇几百字要求单次查询在100毫秒内完成。接口我设计成三个方法一个建索引一个查询一个辅助清空。class SimilarityEngine { public: void buildIndex(const std::vectorstd::string documents); std::vectorsize_t findTop(const std::string query, size_t topN) const; private: std::vectorstd::vectorstd::pairsize_t, double sparseVectors_; std::vectorstd::string rawDocs_; std::unordered_mapstd::string, size_t globalDict_; };这里用sparseVectors_保存每篇文档的非零词索引和权重globalDict_负责词到维度ID的映射。为什么不用稠密向量因为十万篇文档词表可能二十万稠密矩阵就是十万乘二十万内存直接爆炸。稀疏向量只需要内存保存每个文档里真实出现的词平均下来每篇几百项内存能省九成以上。4.2 核心流程与代码实现整个查询流程分为四步query预处理、转向量、逐个计算相似度、保留TopN。预处理和建索引阶段一致才能保证词表ID对齐。把query转换成稀疏向量的代码std::vectorstd::pairsize_t, double SimilarityEngine::queryToSparse(const std::string query) const { std::vectorstd::pairsize_t, double result; auto freq tokenize(query); for (const auto [word, count] : freq) { auto it globalDict_.find(word); if (it ! globalDict_.end()) { result.emplace_back(it-second, static_castdouble(count)); } } return result; }这里注意query中出现的词如果不在全局词典中就只能忽略这也是常见问题之一。如果新词太多说明离线建词典时语料覆盖不够后续要考虑增量更新词典或者采用hash trick直接给词哈希成ID。TopN我用了一个小根堆也就是priority_queue只保留相似度最大的N个候选避免全文排序。实现如下std::vectorsize_t SimilarityEngine::findTop(const std::string query, size_t topN) const { auto qVec queryToSparse(query); using Item std::pairdouble, size_t; std::priority_queueItem, std::vectorItem, std::greaterItem pq; for (size_t i 0; i sparseVectors_.size(); i) { double sim cosineSparse(qVec, sparseVectors_[i]); if (pq.size() topN) { pq.emplace(sim, i); } else if (sim pq.top().first) { pq.pop(); pq.emplace(sim, i); } } std::vectorsize_t result; while (!pq.empty()) { result.push_back(pq.top().second); pq.pop(); } std::reverse(result.begin(), result.end()); return result; }cosineSparse跟稠密版本写法不同它只遍历两个稀疏向量中重叠的ID。常见做法是遍历维度较短的向量并在另一个向量里二分查找更快的做法是两个有序向量线性归并前提是向量按ID排序。我在构建索引时保证每个向量的pair按ID升序查询时也排序这样归并一遍就能算完。4.3 效果测试与结果分析做完之后我用三句中文测试过效果为了绕过开源分词组件直接按字符做了简化切分。假设库里有这么几句话编号内容0我喜欢喝咖啡1咖啡是我每天早上的必需品2今天天气很好适合户外跑步用“我喜欢咖啡”查询得到的相似度大概如下文档相似度00.8110.5220.0第0篇明显最高第1篇有一半词重叠所以中等第2篇没有交集所以为0。这个结果符合直觉。不过我也碰到了典型问题第1篇和第0篇语义上都在讲咖啡但分词方式导致共同词项有限相似度被拉低了。改进方向是用词向量或句子向量代替简单的词频向量但那是更重的模型不是本篇重点。建索引阶段我的做法是离线把十万篇文档全部转为稀疏向量写入内存。查询时只扫一遍稀疏向量数组每次计算只涉及非零维度十万次点积大概几十毫秒满足需求。如果进一步优化可以给每个词建倒排索引先筛出有共同词的文档再计算相似度但当前线性扫描已经够用就保持简单。5. 常见问题与排查技巧5.1 零向量和稀疏向量怎么办零向量是最容易踩的坑。一篇文档分词之后所有词都不在词典里它就会得到一个空的稀疏向量计算时分母为0程序直接崩。应对方法就是在所有入口做空向量检查返回相似度为0并且考虑要不要在构建索引时直接过滤掉空文档。稀疏向量的存储也值得多聊两句。你可能会想用unordered_mapsize_t, double来存每个文档的向量这样查询时可以在哈希表里快速查找维度但哈希表节点分散缓存命中率低遍历慢。通常更好的做法是使用vectorpairsize_t, double按ID严格升序两个向量用归并方式找交集。归并过程中每个元素只访问一次对缓存友好性能比哈希表好不少。我实测过同样数据量有序vector比unordered_map快接近4倍。5.2 性能瓶颈在哪里文本相似度检索的性能瓶颈一般有两个一个是建索引阶段的词频统计和词典构建这是离线任务慢一点问题不大另一个是查询阶段的相似度计算这是核心关注点。如果文档总量很大线性扫描无法满足延迟要求就要用倒排索引。简单说每个词项维护一个文档ID链表query包含哪些词就只去这几个词的链表里找候选文档显著减少需要计算相似度的文档数量。但倒排索引也有代价维护索引结构复杂更新文档要同步改链表。另外如果query里包含“的”“是”这类高频词候选集会非常大所以要做停用词过滤或按文档频率加权。另一个容易忽视的性能问题是向量维度的排序。如果每个向量构建时没排序查询归并就退化成在vector里做线性查找那还不如直接扫稠密数组。我在实现里专门加了一个排序步骤确保每个稀疏向量按ID升序。5.3 精度与速度的取舍不同项目对相似度的精度要求差异很大。推荐系统要的是相对排序差不多的精度也能忍受去重系统要的是绝对阈值判断误差可能导致误杀或漏杀。一种常见的优化方法是把double改成float内存减半速度接近翻倍。float的精度大约7位有效数字对相似度0到1之间的数值已经够用。如果连float都嫌重可以把向量权重量化成整数用int存词频大小虽然会丢失精度但配合倒排索引做粗排效果也不错。还有一个思路是使用局部敏感哈希做近似检索。提前对向量做哈希把相似的item以高概率映射到同一个桶查询时只在桶内计算精确相似度。这能大幅减少计算量但会牺牲召回率。碰到海量数据场景这是个很好的取舍方案小数据量则没必要引入额外复杂度。调试时我习惯先跑几个小用例打印中间向量的稀疏结构和相似度数值而不是直接看最终TopN。这样能快速发现是特征提取的问题还是相似度计算的问题。6. 一点个人体会代码写得久了我越来越觉得相似度判断的难点不在数学公式而在特征表示。同一个向量空间下余弦相似度只是简单的点积除法真正决定结果的是你用什么维度去描述对象。词频和词向量的区分度天差地别坐标特征和归一化特征也会改变距离含义。所以每次接相似度需求我会先花最多的时间确认数据的特征方案再写代码不然算法再标准也只是在错误的表示里打转。还有一个小技巧所有相似度计算模块一定要在接口层做日志埋点记录query和结果分数的分布。线上出问题时通过日志分布可以快速判断阈值是否合理、特征是否退化。我吃过一次亏某个去重模块上线后误杀率很高查了半天才发现是词典更新任务没跑所有新词都映射不到维度相似度被系统性拉低。从那以后我每次都会在构建索引后做一轮抽样验证拿几个已知相似和已知不相似的样本跑一遍确认结果符合预期再发布。相似度判断看起来简单实际上越往深处越有意思。先从余弦相似度搭起一个最小闭环再根据数据规模逐步加倒排索引、稀疏优化甚至近似检索这条路走通之后你会发现自己对“怎么度量事务之间的关系”有了更深的敏感度。