大家好，欢迎来到IT知识分享网。

最近需要做一个文章标题相似度检测提醒，所以了解一下相关的算法，整理如下。

Hamming Distance 汉明距离

汉明距离是一个概念，它表示两个（相同长度）字符串对应位置的不同字符的数量，我们以d（x,y）表示两个字x,y之间的汉明距离。对两个字符串进行异或运算，并统计结果为1的个数，那么这个数就是汉明距离。
1011101 与 1001001 之间的汉明距离是 2。
2143896 与 2233796 之间的汉明距离是 3。
“toned” 与 “roses” 之间的汉明距离是 3。

function hamingString(str1: string, str2: string) {
  if (str1.indexOf(str2) >= 0)
    return str1.length - str2.length
  
  if (str2.indexOf(str1) >= 0)
    return str2.length - str1.length
  
  let diffCount = 0
  let minLen = 0
  if (str2.length < str1.length) {
    diffCount = str1.length - str2.length
    minLen = str2.length
  }
  else {
    diffCount = str2.length - str1.length
    minLen = str1.length
  }
  
  for (let i = 0; i < minLen; i++) {
    if (str1[i] != str2[i])
      diffCount++
  }
  return diffCount
}

算法介绍
比较两个字符串中最短的那个，从左开始循环比较，循环长度是最短的字符的长度。
汉明距离就是差异个数加上两个字符串的长度差
汉明距离算法有个很大的缺点，
字符A：我今天吃的很饱
字符B：我今天吃的很饱呢
A和B的汉明距离是1

字符A：我今天吃的很饱
字符B：看我今天吃的很饱
A和B的汉明距离是8，会认为两个完全不同。

simhash算法

simhash算法介绍
simhash针对文本的话，k值敏感，一般选取3。认为汉明距离小于3的文本是相似的。
缺点：完全无关的文本正好对应成了相同的simhash，精确度并不是很高，而且simhash更适用于较长的文本，但是在大规模语料进行去重时，simhash的计算速度优势还是很不错的。

google的排重就是使用simhash算法实现的。
simhash算法适用于较长文本，大量文本，由于我们现在需求是判断文章标题雷同，所以暂时不深入研究。

最长公共子序列 LCS

最长公共子序列，英文缩写为LCS（Longest Common Subsequence）。其定义是，一个序列 S ，如果分别是两个或多个已知序列的子序列，且是所有符合此条件序列中最长的，则 S 称为已知序列的最长公共子序列。

应用

最长公共子序列是一个十分实用的问题，它可以描述两段文字之间的“相似度”，即它们的雷同程度，从而能够用来辨别抄袭。对一段文字进行修改之后，计算改动前后文字的最长公共子序列，将除此子序列外的部分提取出来，这种方法判断修改的部分，往往十分准确。

def checkSimilarTitle(ret, englishName, name):
    '''
    判断标题相似
    '''
    calcList = {}
    for i in range(0, len(ret['data']['items'])):
        title = ret['data']['items'][i]['title']
        if ('username' in ret['data']['items'][i]['user']) == False:
            continue
        userName = ret['data']['items'][i]['user']['username']
        md5 = getMd5(title)
        for j in range(0, len(ret['data']['items'])):
            title2 = ret['data']['items'][j]['title']
            point = longestCommonSubsequence(title, title2)
            if (len(title) + len(title2)) / 2 == 0:
                continue
            # 最长公共子序列的长度除以平均长度
            point = point / ((len(title) + len(title2)) / 2)
            # print(title, title2, point)
            # 这里的限定值需要测算，目前看情况0.7比较合适，大于等于0.7认为是重复
            if point >= 0.7:
                if md5 in calcList:
                    calcList[md5] = {"point": calcList[md5]['point'] +
                                     1, "title": title, "userName": userName}
                else:
                    calcList[md5] = {"point": 1,
                                     "title": title, "userName": userName}
    text = ''
    for key in calcList:
        if calcList[key]['point'] >= 3:
            text += f"标题：{calcList[key]['title']} 相似数量:{calcList[key]['point']} 发贴人:{calcList[key]['userName']}  \n"

def longestCommonSubsequence(text1, text2):
    '''
    最长公共子序列查找
    '''
    s1, s2 = len(text1), len(text2)

    dp = [[0] * (s2 + 1) for _ in range(s1 + 1)]

    for i in range(1, s1 + 1):
        for j in range(1, s2 + 1):
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            if text1[i - 1] == text2[j - 1]:
                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1)

    return dp[-1][-1]

测试示例

    text1 = '你好啊'
    text2 = '你好啊啊'
    val = longestCommonSubsequence(text1, text2)
    print(val)

输出
3

    text1 = '今天天气真不错，适合外出玩'
    text2 = '今天玩了一下午，只吃了一个汉堡包'
    val = longestCommonSubsequence(text1, text2)
    print(val)

输出
3

上面两个例子，最长公共子序列长度都是3，但是很明显第一个才是我们认为重复的文本，第二个明显不是。
所以判断的依据应该是最长公共子序列长度除以比较文本的平均长度，暂时命名叫：重复比，就是重复的文本长度占原标题文本长度的多少
比如占到70%以上，即认为是两个文本重复。

    text1 = '你好啊'
    text2 = '你好啊啊'
    val = longestCommonSubsequence(text1, text2)
    point = val / ((len(text1) + len(text2)) / 2)
    print(val, point)

输出
3 0.8571428571428571

    text1 = '今天天气真不错，适合外出玩'
    text2 = '今天玩了一下午，只吃了一个汉堡包'
    val = longestCommonSubsequence(text1, text2)
    point = val / ((len(text1) + len(text2)) / 2)
    print(val, point)

输出
3 0.20689655172413793

很明显，根据第一个重复比，0.85就可以判定文本重复。