前言 最近在做一项功能,需要自动从招聘文本中提取技能需求关键词。然而问题来了,请看下面这句招聘需求: 2、 熟练掌握 SpringMVC、Srping、Mybetis 或者 hibernate,熟悉 jQuery,EasyUI 或者 AngularJS; 稍微仔细点看,比较熟悉 Java 的兄 dei 可能已经发现了, ..

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

前言

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

2、 熟练掌握 SpringMVC、Srping、Mybetis 或者 hibernate,熟悉 jQuery,EasyUI 或者 AngularJS;

稍微仔细点看,比较熟悉 Java 的兄 dei 可能已经发现了,WTF?SpringMyBatis 哭晕在厕所……

wtf.jpeg

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

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

image.png

整体的思路是这样的:

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

image.png

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

再仔细一想,这不就是最长公共子序列吗?!卧槽?!

image.png

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

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

image.png

用 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

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

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

image.png

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]

结尾

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

测试了一下,效果还行,先凑合着用?

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

职位描述中提取的关键词 转小写的职位描述关键词 匹配到词典中的小写关键词 标准化技能关键词
SpringMVC springmvc Spring mvc Spring MVC
Srping srping Spring Spring
Mybetis mybetis MyBatis MyBatis
hibernate hibernate hibernate Hibernate

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

另外,请大佬们眼熟我,多谢 ~

  • Python

    Python 是一种面向对象、直译式电脑编程语言,具有近二十年的发展历史,成熟且稳定。它包含了一组完善而且容易理解的标准库,能够轻松完成很多常见的任务。它的语法简捷和清晰,尽量使用无异义的英语单词,与其它大多数程序设计语言使用大括号不一样,它使用缩进来定义语句块。

    381 引用 • 546 回帖 • 570 关注
  • 动态规划
    5 引用 • 1 回帖
回帖
请输入回帖内容...