字符串相似性计算方法
参考文档: https://blog.csdn.net/shijing_0214/article/details/53100992
余弦相似性（cosine similarity）
它是定义在向量空间模型（VSM）中的。它的定义如下：
$$ similarity = cos(\theta) = \frac {A \cdot B} {||A||||B||} = \frac {\displaystyle \sum^{n}{i}A_i \times B_i } {\sqrt { \displaystyle \sum^{n}{i=1} (A_i)^2 } \times \sqrt { \displaystyle \sum^{n}_{i=1} (B_i)^2 } } $$
其中，A,B为向量中间中的两个向量。 在使用它来做字符串相似性度量的时候，需要先将字符串向量化，通常使用词袋模型（BOW）来向量化。举个例子如下：
String1 = “apple”
String2 = “app”
则词包为｛’a’,’e’,’l’,’p’｝，若使用0,1判断元素是否在词包中，字符串1、2可以转化为：
StringA = [1111]
StringB = [1001]
那么，根据余弦公式，可以计算字符串相似性为：0.707。
欧氏距离（Euclidean distance）
定义在向量空间模型中，计算使用欧氏距离公式：
$$ d(p,q) = d(q,p) = \sqrt {(q_1 - p_1)^2+(q_2-p_2)^2+…+(q_n-p_n)^2} = \sqrt {\displaystyle \sum^n_{i=1}(q_i-p_i)^2} $$
编辑距离（edit distance）
编辑距离，有的地方也会称为Levenshtein距离，表示从一个字符串转化为另一个字符串所需要的最少编辑次数，这里的编辑是指将字符串中的一个字符替换成另一个字符，或者插入删除字符。例如上例String1通过删除’l’与’e’转化为String2，所以其最小编辑次数为2。
编辑距离的核心就是如何计算出一对字符串间的最小编辑次数，考虑到问题的特点，我们可以使用动态规划的思想来计算其最小编辑次数，根据维基百科：两个字符串
$a = a_1a_2…a_n$
$b = b_1b_2…b_m$
的编辑距离递归计算公式如下：
$$ d_{i0} = \displaystyle \sum^i_{k=1}w_{del}(b_k), for 1 \leq i \leq m $$
$$ d_{0j} = \displaystyle \sum^j_{k=1}w_{ins}(a_k), for 1 \leq j \leq m $$
$$ d_{ij} = \left{ { {d_{i-1,j} , for a_j=b_i} \atop { min \left{ {d_{i-1,j}+w_{del}(b_i) \atop d_{i,j-1}+w_{ins}(a_j) } \atop d_{i-1,j-1} +w_{sub}(a_j,b_i) for a_i \neq b_i \right} for 1 \leq i \leq m, i \leq j \leq n } } \right} $$
其中，w表示增删改三种操作的权重，一般定义为：
$$ w = \left{ 1, 若有操作 \atop 0， 无操作 \right} $$
海明距离（hamming distance）
Dice 距离
Jaccard distance
J-W距离（Jaro–Winkler distance)
简单共有词
通过计算两篇文档共有的词的总字符数除以最长文档字符数来评估他们的相似度。
假设有A、B两句话，先取出这两句话的共同都有的词的字数然后看哪句话更长就除以哪句话的字数。
同样是A、B两句话，共有词的字符长度为4，最长句子长度为6，那么4/6，≈0.667。
SimHash + 汉明距离
将一个文档转换成64位的字节，然后我们可以通过判断两个字节的汉明距离就知道是否相似了。
Jaccard相似性系数
Jaccard 系数，又叫Jaccard相似性系数，用来比较样本集中的相似性和分散性的一个概率。Jaccard系数等于样本集交集与样本集合集的比值，即
$$ J= |A \cap B| \div | A \cup B | $$
就是交集除以并集，两个文档的共同都有的词除以两个文档所有的词。
曼哈顿距离
曼哈顿距离（Manhattan Distance）是由十九世纪的赫尔曼·闵可夫斯基所创词汇，是种使用在几何度量空间的几何学用语，用以标明两个点上在标准坐标系上的绝对轴距总和。
跟欧几里德距离有点像，简单来说就是:
$$ d(i,j) = |x_i - x_2…| + |y_i-y_i…| $$
同理xn和yn分别代表两个文档所有的词（不重复）在A和B的词频。
然后可以通过: $ 1 \div (1+曼哈顿距离)$ 得到相似度。