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

╰+哭是因爲堅強的太久メ 2023-08-17 15:27 6阅读 0赞

## 前言 ##

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

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

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

![wtf.jpeg][]

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

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

![image.png][]

整体的思路是这样的：

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

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

![image.png][image.png 1]

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

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

![image.png][image.png 2]

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

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

![image.png][image.png 3]

## 用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\]中选择，我们要的是最长子序列，选择最大的即可。

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

![image.png][image.png 4]

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

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

![image.png][image.png 5]

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]

## 结尾 ##

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

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

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

<table> 
 <thead> 
  <tr> 
   <th>职位描述中提取的关键词</th> 
   <th>转小写的职位描述关键词</th> 
   <th>匹配到词典中的小写关键词</th> 
   <th>标准化技能关键词</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>SpringMVC</td> 
   <td>springmvc</td> 
   <td>spring mvc</td> 
   <td>Spring MVC</td> 
  </tr> 
  <tr> 
   <td>Srping</td> 
   <td>srping</td> 
   <td>spring</td> 
   <td>Spring</td> 
  </tr> 
  <tr> 
   <td>Mybetis</td> 
   <td>mybetis</td> 
   <td>mybatis</td> 
   <td>Mybatis</td> 
  </tr> 
  <tr> 
   <td>hibernate</td> 
   <td>hibernate</td> 
   <td>hibernate</td> 
   <td>Hibernate</td> 
  </tr> 
 </tbody> 
</table>

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

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

[wtf.jpeg]: /images/20230810/44e67dbf895b4aeda301ae1a6b427839.png
[image.png]: /images/20230810/e7b89f917c37409db66b928be1e41f7f.png
[image.png 1]: /images/20230810/6fa2b5a3423a4a5cbf9b463fa7d50cdd.png
[image.png 2]: /images/20230810/31910aada66e4e61bc91e9325be30d92.png
[image.png 3]: /images/20230810/d7d4ef9afd1e48cb8ca7a637d21ed841.png
[wiki]: https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
[image.png 4]: /images/20230810/01ba277af1c54129ad4d3695d22af180.png
[image.png 5]: /images/20230810/7069fc34a0184433ba5694760bed062f.png
[Link 1]: https://www.aaronjny.com/
[solo]: https://github.com/b3log/solo