Java 技能关键词纠错——计算两字符串最长公共子序列（动态规划）

前言

最近在做一项功能，需要自动从招聘文本中提取技能需求关键词。然而问题来了，请看下面这句招聘需求：

2、 熟练掌握 SpringMVC、Srping、Mybetis 或者 hibernate，熟悉 Jquery，EasyUI 或者 AngularJS；

稍微仔细点看，比较熟悉 Java 的兄 dei 可能已经发现了，WTF？Spring、MyBatis 哭晕在厕所……

是哪家公司的我就不说了哈，影响不好，可能就是单纯手误吧。

然而，我就需要多做一项工作——纠错。从招聘文本中提取的关键词，不能直接作为结果，还需要使用对可能的手误打错、粘贴漏字这些问题进行处理，对可能为错误的关键词进行纠正。

整体的思路是这样的：

• 1.我写了一个提取器，可以按照特定的规则从招聘文本中提取可能的关键词
• 2.我建立了一个小型的 java 关键词库。但不属于这个词库的、可能的关键词，也能被 1 中的提取器识别出来。
• 3.对于所有提取的技能关键词，尝试和词库进行匹配（匹配时关键词和词库统一转成小写，避免大小写不一致产生的问题），如果匹配上了，说明这个词大概率没有拼写问题，跳过。
• 4.如果在 3 中没有匹配上，且这个词里面含有中文，也认为它没有拼写问题，跳过。
• 5.如果在 3 中没有匹配上，且这个词是英文词，我们将它与词库进行 模糊匹配，匹配上了，则认为它的拼写有问题，进行纠正；没匹配上，认为它是被模型发现的新技能关键词，是正确的。

那么，问题的关键就是，怎么做模糊匹配。

想了一下，拼写错误或者粘贴漏字也不可能太离谱吧？对于有一定长度的关键词（比如长度 >=5），当它和词库里的一个关键词只有不超过一定个数（比如 2 个）的字符有差异，其他完全相同的话，是不是就有较大概率认为它们是同一个词？

再仔细一想，这不就是最长公共子序列吗？！卧槽？！

没想到不打比赛这么久之后，我竟然有看到了这个词……讲道理这还是第一次在工作中用到 ACM 里面学到的算法知识？数据结构就不算了，经常用。

好吧，那就开始做题吧。回忆了一会儿，开始写动态规划……一堆废话的前言结束了。

用 Python3 实现最长公共子序列

动态规划是什么，我就不多说了，大家可以参考 wiki。

简单来说，就是把一个复杂的问题拆解成一步步的小问题，由简单的状态开始，逐步递推，直到计算出最终状态，即我们需要的结果。

一般来说，写动态规划都是从寻找递推公式开始的。

对于当前这个问题，我们假设有字符串 s1 和 s2，它们的长度分别为 n 和 m，用数组 dp 记录最长公共子序列的长度（dp[i][j]表示的是 s1[:i]和 s2[:j]的最长公共子序列的长度。ps:刚刚那个写法是切片，点进我的博客的应该多多少少都了解些 python，这种基础语法我就不解释了= =）。

那么 dp[i][j]的数值是由谁决定的呢（这里 i 和 j 是从 1 开始的，dp[i][j]=0）？

我们可以想一下，假如 s1[i-1]和 s2[j-1]是相等的（参考上面一句，这里下标从 0 开始，所以要-1），那么它们就可以作为公共子序列的一部分，接入到 s1[:i]和 s2[:j]的最长公共子序列中去。而按照递推来看,dp[i-1][j-1]是我们已经算出来的，所以 dp[i][j]=dp[i-1][j-1]+1。

如果 s1[i-1]和 s2[j-1]不相等呢？如果不相等，那我们就不用考虑 dp[i-1][j-1]了，因为不论是 dp[i][j-1]还是 dp[i-1][j]都一定大于等于它。在 s1[i-1]!=s2[j-1]的情况下，dp[i][j]只能从 dp[i-1][j]和 dp[i][j-1]中选择，我们要的是最长子序列，选择最大的即可。

那么，递推公式可以这么表示：

solo 上面的 markdown 对 LaTeX 的解析好像有点问题，所以我直接放截图了。

动态规划麻烦就麻烦在递推公式推导方面，推出来之后就好办了，编码而已嘛。

def check_similarity(word1, word2, diff_size=2):
    """
    给定两个字符串，判断两个字符串是否相差不超过diff个字符

    Args:
        word1: 待判定字符串1
        word2: 待判定字符串2
        diff_size: 允许的最大相差字符数

    Returns:
        bool: 字符串word1和word2是否满足相似度要求
    """
    # 先计算字符串长度，后面会频繁使用
    length1 = len(word1)
    length2 = len(word2)
    # 如果两个字符串的长度相差大于diff_size，肯定不满足我们的要求，
    # 直接返回False
    if abs(length1 - length2) > diff_size:
        return False
    # 如果有任何一个字符串长度小于5，就不进行比较了，
    # 当长度较短时最长公共子序列的说服力不足，直接返回False
    if min(length1, length2) < 5:
        return False
    # 初始化dp数组，尺寸为(length1+1)*(length2+1)，初始值全为0
    dp = [[0 for _ in range(length2 + 1)] for _ in range(length1 + 1)]
    # 开始递推
    for i in range(1, length1 + 1):
        for j in range(1, length2 + 1):
            # 参考递推公式，没什么好说的
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # 最长公共子序列的长度和比较短的字符串的长度差距 + 给定两个字符串之间的长度差距，不能查过diff_size，
    # 否则认为两个字符串差距过大，不是同一技能关键词
    if abs(dp[length1][length2] - min(length1, length2)) + abs(length1 - length2) > diff_size:
        return False
    else:
        return True

上面的代码夹杂了部分业务代码，如果需要的话，我们可以把计算最长公共子序列长度的代码单独提取出来：

def longest_common_dp(word1, word2):
    """
    给定两个字符串，计算两者之间的最长公共子序列长度

    Args:
        word1[str]: 给定字符串1
        word2[str]: 给定字符串2

    Returns:
        int: 两字符串最长公共子序列长度
    """
    # 先计算字符串长度，后面会频繁使用
    length1 = len(word1)
    length2 = len(word2)
    # 如果两个字符串中有任何一个为空串，两字符串的最长公共子序列肯定为空串
    if not word1 or not word2:
        return 0
    # 初始化dp数组，尺寸为(length1+1)*(length2+1)，初始值全为0
    dp = [[0 for _ in range(length2 + 1)] for _ in range(length1 + 1)]
    # 开始递推
    for i in range(1, length1 + 1):
        for j in range(1, length2 + 1):
            # 参考递推公式，没什么好说的
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    # 按照递推公式的假设，dp[length1][length2]是最终状态，返回即可
    return dp[length1][length2]

结尾

打完收工！当然啦，在业务实现中没这么简单，还有很多琐碎的细节（比如比较的时候统一转小写啦、小写关键词-> 标准关键词的映射啦什么的，挺麻烦的），都没有在这里给出，没必要，也没什么意思。

测试了一下，效果还行，先凑合着用？

纠错(或者标准化写法)的流程大概如下：

最后，除 CSDN 的个人博客外，我使用 solo 自建了独立的 个人站点（ https://www.aaronjny.com/ ）。
感谢开源项目 solo！！！

另外，请大佬们眼熟我，多谢 ～