文本相似度的那些算法

子序列与子字符串

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

更详细的算法可以看这篇文档：
http://www.cnblogs.com/zhangchaoyang/articles/2012070.html

字符串编辑距离

精确计算两个字符串的编辑距离，可以使用经典的动态规划思路。

这里来看下如何判断字符串A与B的编辑是否>N？这样我们就可以比较两个字符串的相似度了。
可以构建一个编辑距离自动机（超酷算法：Levenshtein自动机），把测试字符集合输入自动机进行判断。

可用于拼写检查，模糊匹配等场景。

向量相似度

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

更详细的介绍看这篇文档：
http://www.ruanyifeng.com/blog/2013/03/cosine_similarity.html

SimHash

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

主要分以下几步：
1、抽取文本中的关键词及其权重。
2、对关键词取传统hash，并与权重叠加，算出文本的fingerprint值。
3、计算出两个文本之间fingerprint值的海明距离。

更详细的介绍可以看这篇文档：
http://blog.csdn.net/heiyeshuwu/article/details/44117473

最后

以上就是大方火龙果为你收集整理的文本相似度的那些算法的全部内容，希望文章能够帮你解决文本相似度的那些算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。