知识卡片
倒排算相似
内容
文档两两相似度直接计算是 O(n²)。倒排索引把视角转为“同一词贡献哪些文档对”，只累加共享词的贡献，利用文本向量稀疏性省掉大量零乘法。
参考来源
- 位置：《大数据日知录：架构与算法》第16章《机器学习：分布式算法》"16.4 自然语言处理：文档相似性计算"一节（源文件：_epub-src/OEBPS/text00021.html）
- 结论依据：原文明确"如果t在任意一个文档中没有出现，则其对两者相似性贡献为0，也即只有两个文档同时包含单词t，那么单词t才对这两者相似性有影响……记录包含单词t的文档集合其实就是搜索引擎的倒排索引……通过累计每个单词对任意两个文档之间的相似性的贡献来最终求得整体相似性"，避免了对不共享词的文档对做无效计算。
- 原始内容：如果t在任意一个文档中没有出现，则其对两者相似性贡献为0，也即只有两个文档同时包含单词t，那么单词t才对这两者相似性有影响……记录包含单词t的文档集合其实就是搜索引擎的倒排索引……上述计算流程的基本思路是通过累计每个单词对任意两个文档之间的相似性的贡献来最终求得整体相似性。