编辑距离算法全解析:优化文本处理的关键技术

本文涉及的产品
全局流量管理 GTM,标准版 1个月
云解析DNS,个人版 1个月
云解析 DNS,旗舰版 1个月
简介: 编辑距离算法全解析:优化文本处理的关键技术

作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。

会一些的技术:数据分析、算法、SQL、大数据相关、python

欢迎加入社区:码上找工作

作者专栏每日更新:

LeetCode解锁1000题: 打怪升级之旅

python数据分析可视化:企业实战案例

python源码解读

备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级

这是力扣72题:编辑距离

题目描述

给定两个单词 word1word2,计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作:

  1. 插入一个字符
  2. 删除一个字符
  3. 替换一个字符
输入格式
  • word1:一个字符串。
  • word2:一个字符串。
输出格式
  • 返回将 word1 转换成 word2 的最小操作数。

示例

示例 1
输入: word1 = "horse", word2 = "ros"
输出: 3
解释: 
horse -> rorse (将 'h' 替换为 'r')
rorse -> rose (删除 'r')
rose -> ros (删除 'e')
示例 2
输入: word1 = "intention", word2 = "execution"
输出: 5
解释: 
intention -> inention (删除 't')
inention -> enention (将 'i' 替换为 'e')
enention -> exention (将 'n' 替换为 'x')
exention -> exection (将 'n' 替换为 'c')
exection -> execution (插入 'u')

方法一:动态规划

解题步骤
  1. 定义状态数组dp[i][j] 表示 word1 的前 i 个字母转换成 word2 的前 j 个字母所使用的最少操作。
  2. 初始化边界:初始化 dp 数组的第一行和第一列,分别表示空字符串到任意长度字符串的转换。
  3. 状态转移方程
  • 如果 word1[i-1] == word2[j-1],则 dp[i][j] = dp[i-1][j-1]
  • 否则,取插入、删除、替换操作的最小值加一,即 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
  1. 计算最终结果:返回 dp[m][n]
完整的规范代码
def minDistance(word1, word2):
    """
    使用动态规划解决编辑距离问题
    :param word1: str, 第一个单词
    :param word2: str, 第二个单词
    :return: int, 最少操作数
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        dp[i][0] = i
    for j in range(1, n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
    return dp[m][n]
# 示例调用
print(minDistance("horse", "ros"))  # 输出: 3
print(minDistance("intention", "execution"))  # 输出: 5
算法分析
  • 时间复杂度:(O(m * n)),其中 mn 分别是两个字符串的长度。
  • 空间复杂度:(O(m * n)),用于存储 dp 表。

方法二:空间优化的动态规划

解题步骤
  1. 使用滚动数组:使用两行(当前行和前一行)或一行(滚动更新)来减少空间复杂度。
  2. 状态转移:更新 dp 数组时,只依赖于当前行的前一个元素和上一行的元素,因此可以用一维数组滚动更新。
完整的规范代码
def minDistance(word1, word2):
    """
    使用空间优化的动态规划解决编辑距离问题
    :param word1: str, 第一个单词
    :param word2: str, 第二个单词
    :return: int, 最少操作数
    """
    if len(word1) < len(word2):
        word1, word2 = word2, word1
    m, n = len(word1), len(word2)
    previous, current = list(range(n + 1)), [0] * (n + 1)
    for i in range(1, m + 1):
        current[0] = i
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                current[j] = previous[j - 1]
            else:
                current[j] = min(previous[j - 1], previous[j], current[j - 1]) + 1
        previous, current = current, previous
    return previous[n]
# 示例调用
print(minDistance("horse", "ros"))  # 输出: 3
print(minDistance("intention", "execution"))  # 输出: 5
算法分析
  • 时间复杂度:(O(m * n)),与完整的动态规划相同。
  • 空间复杂度:(O(min(m, n))),只使用两个长度为 n + 1 的数组。

方法三:递归加记忆化

解题步骤
  1. 定义递归函数:定义一个递归函数来计算 word1[0...i]word2[0...j] 的编辑距离。
  2. 记忆化存储:使用一个二维数组来存储已计算的结果,避免重复计算。
  3. 递归计算:基于给定的操作计算最小编辑距离。
完整的规范代码
def minDistance(word1, word2):
    """
    使用递归加记忆化解决编辑距离问题
    :param word1: str, 第一个单词
    :param word2: str, 第二个单词
    :return: int, 最少操作数
    """
    memo = {}
    def dp(i, j):
        if (i, j) in memo:
            return memo[(i, j)]
        if i == 0: return j
        if j == 0: return i
        if word1[i - 1] == word2[j - 1]:
            ans = dp(i - 1, j - 1)
        else:
            ans = min(dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1)) + 1
        memo[(i, j)] = ans
        return ans
    return dp(len(word1), len(word2))
# 示例调用
print(minDistance("horse", "ros"))  # 输出: 3
print(minDistance("intention", "execution"))  # 输出: 5
算法分析
  • 时间复杂度:(O(m * n)),递归处理每对索引一次。
  • 空间复杂度:(O(m * n)),用于存储递归调用栈和记忆化结果。

方法四:迭代加记忆化

解题步骤
  1. 初始化:建立一个二维数组用于记忆化存储。
  2. 基本情况填充:填充数组的基本情况(一个字符串为空的情况)。
  3. 迭代计算:使用之前填充的结果迭代计算整个 dp 表。
完整的规范代码
def minDistance(word1, word2):
    """
    使用迭代加记忆化解决编辑距离问题
    :param word1: str, 第一个单词
    :param word2: str, 第二个单词
    :return: int, 最少操作数
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
    return dp[m][n]
# 示例调用
print(minDistance("horse", "ros"))  # 输出: 3
print(minDistance("intention", "execution"))  # 输出: 5

方法五:基于编辑操作的动态规划

解题步骤
  1. 分析编辑操作:将编辑操作细分为插入、删除、替换,并为每种操作定义独立的逻辑。
  2. 逐步构建解决方案:基于以上操作,构建一个解决方案,逐步填充 dp 表。
完整的规范代码
def minDistance(word1, word2):
    """
    基于编辑操作的动态规划解决编辑距离问题
    :param word1: str, 第一个单词
    :param word2: str, 第二个单词
    :return: int, 最少操作数
    """
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                insert_op = dp[i][j - 1]
                delete_op = dp[i - 1][j]
                replace_op = dp[i - 1][j - 1]
                dp[i][j] = min(insert_op, delete_op, replace_op) + 1
    return dp[m][n]
# 示例调用
print(minDistance("horse", "ros"))  # 输出: 3
print(minDistance("intention", "execution"))  # 输出: 5

不同算法的优劣势对比

特征 方法一:动态规划 方法二:空间优化DP 方法三:递归加记忆化 方法四:迭代加记忆化 方法五:基于编辑操作DP
时间复杂度 (O(m * n)) (O(m * n)) (O(m * n)) (O(m * n)) (O(m * n))
空间复杂度 (O(m * n)) (O(min(m, n))) (O(m * n)) (O(m * n)) (O(m * n))
优势 易于理解和实现 空间复杂度较低 避免重复计算,提高效率 适合大规模数据处理 直观反映不同编辑操作
劣势 空间占用大 代码稍复杂 空间占用大 空间占用大 实现较为复杂

应用示例

自然语言处理:在自然语言处理领域,编辑距离用来衡量两个词语之间的相似度,常用于拼写检查、语音识别系统等领域。

数据库记录匹配:在数据清洗过程中,编辑距离可以帮助识别和合并重复的记录,例如在客户数据库中识别重复的客户名称。

生物信息学:在生物信息学中,编辑距离用于比较基因序列的相似性,对于基因编辑和比较具有重要的应用价值。

欢迎关注微信公众号 数据分析螺丝钉

相关文章
|
6天前
|
物联网 大数据 定位技术
基于RFID、室内定位技术的图书馆定位系统功能解析
维小帮图书馆定位导航系统解决了复杂布局与找书难题,采用RFID、室内定位技术,结合大数据与云计算,提供电子地图、VR云览、AR导航及图书位置指引。通过集成座位预约,优化资源分配,提升读者体验,促进图书馆与城市的智慧化建设。
42 3
基于RFID、室内定位技术的图书馆定位系统功能解析
|
1天前
|
算法 搜索推荐 开发者
别再让复杂度拖你后腿!Python 算法设计与分析实战,教你如何精准评估与优化!
【7月更文挑战第23天】在Python编程中,掌握算法复杂度—时间与空间消耗,是提升程序效能的关键。算法如冒泡排序($O(n^2)$时间/$O(1)$空间),或使用Python内置函数找最大值($O(n)$时间),需精确诊断与优化。数据结构如哈希表可将查找从$O(n)$降至$O(1)$。运用`timeit`模块评估性能,深入理解数据结构和算法,使Python代码更高效。持续实践与学习,精通复杂度管理。
16 9
|
1天前
|
机器学习/深度学习 缓存 并行计算
操作系统调度算法的演变与优化
【7月更文挑战第23天】本文深入探讨了操作系统中调度算法的发展历程,从简单的先来先服务到复杂的多级反馈队列调度算法。通过分析不同算法的特点和性能表现,文章揭示了调度算法在提升系统响应速度、公平性以及资源利用率方面的重要性。同时,文章也讨论了现代操作系统如何通过优化调度算法来适应多核处理器架构,以及未来可能的研究方向。
|
2天前
|
缓存 算法 编译器
python算法优化
【7月更文挑战第21天】
11 3
|
3天前
|
传感器 机器学习/深度学习 算法
基于GA遗传算法的WSN网络节点覆盖优化matlab仿真
本研究应用遗传优化算法于无线传感器网络(WSN),优化节点布局与数量,以最小化节点使用而最大化网络覆盖率。MATLAB2022a环境下,算法通过选择、交叉与变异操作,逐步改进节点配置,最终输出收敛曲线展现覆盖率、节点数及适应度值变化。无线传感器网络覆盖优化问题通过数学建模,结合遗传算法,实现目标区域有效覆盖与网络寿命延长。算法设计中,采用二进制编码表示节点状态,适应度函数考量覆盖率与连通性,通过选择、交叉和变异策略迭代优化,直至满足终止条件。
|
6天前
|
域名解析 缓存 网络协议
深入理解Linux下的DNS技术
Linux DNS详解:连接用户与网络资源的关键,涉及基本原理、DNS服务器软件如BIND、PowerDNS、Dnsmasq、解析过程、缓存及系统配置。理解这些有助于优化网络性能和安全。配置文件 `/etc/resolv.conf` 用于指定DNS服务器,而DNS缓存提升响应速度。学习DNS技术,提升系统效率与可靠性。
35 7
|
3天前
|
机器学习/深度学习 自然语言处理
深入解析深度学习中的正则化技术
【7月更文挑战第21天】深度学习模型在追求高精度的同时,也面临着过拟合的风险。本文将探讨如何通过正则化技术来平衡模型复杂度与泛化能力,包括L1与L2正则化、Dropout、数据增强和早停等策略。我们将分析这些方法的工作原理及其在实际问题中的应用效果,并讨论如何选择合适的正则化技术以优化深度学习模型的性能。
|
4天前
|
JavaScript 前端开发 搜索推荐
服务器端渲染技术SSR与ISR:深入解析与应用
【7月更文挑战第20天】服务器端渲染(SSR)和增量静态再生(ISR)作为现代Web开发中的两种重要渲染技术,各有其独特的优势和适用场景。在实际应用中,开发者应根据具体需求和条件选择合适的渲染模式。无论是追求极致的页面加载速度和SEO优化,还是实现内容的实时更新,SSR和ISR都能提供有效的解决方案。通过深入理解这些技术的工作原理和应用场景,开发者可以构建出更加高效、可靠和用户体验优异的Web应用。
|
4天前
|
监控 负载均衡 安全
微服务架构下的服务发现与注册:技术深度解析
【7月更文挑战第20天】服务发现与注册是微服务架构中不可或缺的一部分,它确保了服务间的动态发现和通信。通过选择合适的实现工具和遵循最佳实践,可以构建出高效、可靠、可扩展的微服务系统。随着技术的不断进步,未来我们还将看到更多创新的服务发现与注册解决方案的出现。
|
4天前
|
存储 JSON 安全
OAuth2与JWT在API安全中的角色:技术深度解析
【7月更文挑战第20天】OAuth2和JWT作为两种重要的安全协议,在API安全中发挥着不可或缺的作用。OAuth2通过提供灵活的授权框架,实现了对资源的细粒度访问控制;而JWT则通过其紧凑性和自包含性,确保了身份验证和信息传输的安全性。在实际应用中,将OAuth2和JWT结合使用,可以构建出既强大又安全的API服务,为用户提供更加安全、可靠和便捷的数字体验。

推荐镜像

更多