ChatGPT 算法训练营 — 编辑距离

简介: 编辑距离是一种用来度量两个字符串之间相似程度的算法。它通常用于搜索错别字的纠正,或者模糊搜索。例如,如果我们搜索 gogle 时,它可以正确搜索到 google 的结果。

ChatGPT 写代码还是可以的,不过在一步一步推导过程中就会错误频出了。


编辑距离是一种用来度量两个字符串之间相似程度的算法。它通常用于搜索错别字的纠正,或者模糊搜索。例如,如果我们搜索 gogle 时,它可以正确搜索到 google 的结果。

算法原理


编辑距离通过将一个字符串转换成另一个字符串所需的最少操作数来衡量两个字符串的相似度。这些操作可以是插入一个字符、删除一个字符或替换一个字符。


编辑距离的实现是通过动态规划来做的,那就让我们来看看如何用动态规划来拆分子问题。


具体来说,我们可以把两个字符串看成是由它们的子串组成的,那么问题就变成了如何计算这些子串之间的编辑距离。我们可以先计算最小的子串之间的编辑距离,然后再逐渐扩大子串的范围,直到计算出整个字符串的编辑距离。这样,我们就把大问题拆分成了很多个小问题。


我们假设两个字符串分别为 AB, 当我们需要计算A 的前 i 个字符到 B 的前 j 个字符的编辑距离dp[i][j]时,我们需要考虑以下三种情况:

  1. 如果 A[i] == B[i], 则其编辑距离就等于 dp[i-1][j-1]
  2. 如果 A[i] != B[i],则要分三种情况,然后取三种情况的最小值就是编辑距离:
  • 如果将 A 的第 i 个字符替换为 B 的第 j 个字符,那么编辑距离就是 dp[i-1][j-1] + 1
  • 如果将 A 的第 i 个字符删除,那么编辑距离就是 dp[i-1][j] + 1
  • 如果将 B 的第 j 个字符插入到 A 的第 i 个字符之后,那么编辑距离就是 dp[i][j-1] + 1

举个例子


假设 AabcdBabedf。我们来一步一步看它的编辑距离是怎么计算的。

首先,我们创建一个表格:

a b e d f
0 1 2 3 4 5
a 1 x
b 2
c 3
d 4

表格中的值 dp[i][j]A 的前 i 的字符到 B 的前 j 个字符的编辑距离。我们首先填充第一行和第一列,因为从空字符串转换到一个字符串的编辑距离就是进行该字符串长度的插入。这个就简单了。


例如这个时候我们要计算 x 位置的编辑距离, 我们就可以带入上面的那几种情况:


因为 ABx 位置的都为 a,所以其编辑距离就等于 d[i-1][j-1], 也就是 0, 我们将其更新到表格中

a b e d f
0 1 2 3 4 5
a 1 0 x
b 2
c 3
d 4

接下来我们就可以计算新的 x 位置的编辑距离了,由于此时 A[i] != B[j] 了, 我们就要按前文说的分三种情况分别计算了:

  1. 替换: dp[i-1][j-1] + 1 = 1 + 1 = 2
  2. 删除: dp[i-1][j] + 1 = 2 + 1 = 3
  3. 插入: dp[i][j-1] + 1 = 0 + 1 = 1

所以我们可以取得最小值为 1,然后写入表格

a b e d f
0 1 2 3 4 5
a 1 0 1 x
b 2
c 3
d 4

重复上面的步骤,我们就可以得到最终的结果

a b e d f
0 1 2 3 4 5
a 1 0 1 2 3 4
b 2 1 0 1 2 3
c 3 2 1 1 2 3
d 4 3 2 2 1 2

因此我们就可以得到最终的编辑距离为 2 了。

如果理解了上述过程,写代码就是个翻译过程了。

代码实现


koltin


fun editDistance(s: String, t: String): Int {
    val m = s.length
    val n = t.length
    val dp = Array(m+1) { IntArray(n+1) }
    for (i in 0..m) {
        dp[i][0] = i
    }
    for (j in 0..n) {
        dp[0][j] = j
    }
    for (i in 1..m) {
        for (j in 1..n) {
            if (s[i-1] == t[j-1]) {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = minOf(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1
            }
        }
    }
    return dp[m][n]
}

rn dp[m][n]}

Rust 实现


fn edit_distance(s: &str, t: &str) -> usize {
    let m = s.chars().count();
    let n = t.chars().count();
    let mut dp = vec![vec![0; n+1]; m+1];
    for i in 0..=m {
        dp[i][0] = i;
    }
    for j in 0..=n {
        dp[0][j] = j;
    }
    for i in 1..=m {
        for j in 1..=n {
            if s.chars().nth(i-1) == t.chars().nth(j-1) {
                dp[i][j] = dp[i-1][j-1];
            } else {
                dp[i][j] = dp[i-1][j-1].min(dp[i][j-1]).min(dp[i-1][j]) + 1;
            }
        }
    }
    dp[m][n]
}

接下来让我们分析下复杂度:


在上面的实现中,我们使用了一个二维数组 dp 来存储每个子问题的编辑距离。因此,算法的空间复杂度为 O(mn),其中 mn 分别是两个字符串的长度。


在算法的时间复杂度方面,我们需要遍历每个子问题,并对它们进行一些操作(比较两个字符是否相等、取最小值等)。因此,时间复杂度为 O(mn)

算法优化


如果我们看上面流程,我们是一行一行的去计算,而每一行的计算只依赖于几个特定点的值,因而我们可以使用滚动数组技巧将空间复杂度降至 O(n)。

Kotlin 实现


fun editDistance(s: String, t: String): Int {
    val m = s.length
    val n = t.length
    val dp = IntArray(n + 1) { it }
    var pre: Int
    var temp: Int
    for (i in 1..m) {
        pre = dp[0]
        dp[0] = i
        for (j in 1..n) {
            temp = dp[j]
            dp[j] = (pre + (s[i - 1] != t[j - 1]).toInt())
                .coerceAtMost(dp[j - 1] + 1)
                .coerceAtMost(dp[j] + 1)
            pre = temp
        }
    }
    return dp[n]
}

Rust 实现


fn edit_distance(s: &str, t: &str) -> usize {
    let m = s.len();
    let n = t.len();
    let mut dp = vec![0; n + 1];
    for j in 0..=n {
        dp[j] = j;
    }
    for i in 1..=m {
        let mut pre = dp[0];
        dp[0] = i;
        for j in 1..=n {
            let temp = dp[j];
            dp[j] = (pre + (s.as_bytes()[i - 1] != t.as_bytes()[j - 1]) as usize)
                .min((dp[j - 1] + 1).min(dp[j] + 1));
            pre = temp;
        }
    }
    dp[n]
}
目录
相关文章
|
2月前
|
存储 机器学习/深度学习 算法
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
蓝桥杯Python编程练习题的集合,涵盖了从基础到提高的多个算法题目及其解答。
76 3
蓝桥杯练习题(三):Python组之算法训练提高综合五十题
|
1月前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
2月前
|
机器学习/深度学习 人工智能 并行计算
DeepSpeed Chat: 一键式RLHF训练,让你的类ChatGPT千亿大模型提速省钱15倍
DeepSpeed Chat 是一款革命性的平台,专为简化和加速类ChatGPT模型的训练而设计。通过一键式脚本,用户可以轻松完成从预训练模型到生成自定义ChatGPT模型的全过程。该系统复刻了InstructGPT的RLHF训练方法,并集成了一系列优化技术,如DeepSpeed Hybrid Engine,大幅提升了训练效率和经济性。使用DeepSpeed Chat,即使是拥有数千亿参数的大模型,也能在短时间内完成训练,且成本显著降低。无论是单GPU还是多GPU集群环境,DeepSpeed Chat都能提供卓越的性能和易用性,让RLHF训练变得更加普及。
DeepSpeed Chat: 一键式RLHF训练,让你的类ChatGPT千亿大模型提速省钱15倍
|
2月前
|
机器学习/深度学习 算法 决策智能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
【机器学习】揭秘深度学习优化算法:加速训练与提升性能
|
2月前
|
算法 Java C++
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
【贪心算法】算法训练 ALGO-1003 礼物(C/C++)
|
2月前
|
算法 C++
蓝桥 算法训练 共线(C++)
蓝桥 算法训练 共线(C++)
|
4月前
|
机器学习/深度学习 人工智能 自然语言处理
让非算法同学也能了解 ChatGPT 等相关大模型
让非算法同学也能了解 ChatGPT 等相关大模型
让非算法同学也能了解 ChatGPT 等相关大模型
|
4月前
|
人工智能 开发者 芯片
【51单片机】单片机开发者的福音: 让AI看电路图帮你编写程序(使用ChatGPT 中训练好的单片机工程师模型)
使用AI大语言模型编写 单片机程序. 使用的是 OpenAI公司发布的 ChatGPT .在ChatGPT上有别人训练好的 单片机工程师 with Keil uVision 5 - C Code Explainer模型, 可以上传电路图改模型可以通过这个用户所给的电路图进行编程.
308 0
【51单片机】单片机开发者的福音: 让AI看电路图帮你编写程序(使用ChatGPT 中训练好的单片机工程师模型)
|
5月前
knn增强数据训练
【7月更文挑战第28天】
45 2
|
4月前
|
算法 搜索推荐
支付宝商业化广告算法问题之基于pretrain—>finetune范式的知识迁移中,finetune阶段全参数训练与部分参数训练的效果如何比较
支付宝商业化广告算法问题之基于pretrain—>finetune范式的知识迁移中,finetune阶段全参数训练与部分参数训练的效果如何比较