文档相识度

文档相似度计算在信息检索、数据挖掘、机器翻译、文档复制检测等领域有着广泛的应用。站在数学角度去量化其相似性，进而对其进行抽象分解。

例子比如舆论控制，我们假设你开发了一个微博网站，并且已经把世界上骂人的句子都已经收录进了数据库，那么当一个用户发微博时会先跟骂人句子的数据库进行比较，如果符合里面的句子就不让用户发出。

通常情况下，很多工程师就会想到用like或者where的sql语法去查找。可是当情况更为复杂呢？数据库存放了“你是个坏人”，用户要发“小明是个坏人”，这时应该怎么办呢？最简单的办法就是通过判断文本的相似程度来决定用户发的内容是否是骂人的。

相关算法余弦相似性TF-IDF，余弦相似度，向量空间模型这几个知识点在信息检索中是最基本的，入门级的参考资料可以看看吴军老师在《数学之美》中第11章“如何确定网页和查询的相关性”和第14章“余弦定理和新闻的分类”中的通俗介绍或者阮一峰老师写的两篇科普文章“TF-IDF与余弦相似性的应用（一）：自动提取关键词**”和“TF-IDF与余弦相似性的应用（二）：找出相似文章”。

专业一点的参考资料推荐王斌老师在中科院所授的研究生课程“现代信息检索(Modern Information Retrieval)”的课件，其中“第六讲向量模型及权重计算”和该主题相关。或者更详细的可参考王斌老师翻译的经典的《信息检索导论》第6章或者其它相关的信息检索书籍。

子序列与子字符串这个系列问题包含这么几种：最大子序列、最长递增子序列、最长公共子串、最长公共子序列。 几个子问题都可以用动态规划的思路来求解。对于长度为i、j的两个字符串 ，使用矩阵来存放中间结果。

字符串编辑距离精确计算两个字符串的编辑距离，可以使用经典的动态规划思路。这里来看下如何判断字符串A与B的编辑是否>N？这样我们就可以比较两个字符串的相似度了。 可以构建一个编辑距离自动机（超酷算法：Levenshtein自动机），把测试字符集合输入自动机进行判断。可用于拼写检查，模糊匹配等场景。

向量相似度使用TF-IDF计算出文本中词的词频集合，把该集合作一个向量，比较不同集合向量在线性空间中的相似度。如：余弦距离、欧氏距离、概率分布距离（K-L距离）等1。

SimHashsimhash算法的主要思想是降维，将高维的特征向量映射成一个f-bit的指纹(fingerprint)，通过比较两篇文章的f-bit指纹的Hamming Distance来确定文章是否重复或者高度近似。

主要分以下几步：

1、抽取文本中的关键词及其权重。

2、对关键词取传统hash，并与权重叠加，算出文本的fingerprint值。

3、计算出两个文本之间fingerprint值的海明距离。

本词条内容贡献者为:

王慧维 - 副研究员 - 西南大学