Longest-common-subsequence-and-minimum-edit-distance/main.md at master

fly6516s_Education.test/Longest-common-subsequence-and-minimum-edit-distance

Fork 0

fly6516 dadf36d046 full file

2024-12-08 23:11:33 +08:00

4.1 KiB

Raw Permalink Blame History

以下是针对实验内容的详细指导和实现建议：

一、实验目的

最长公共子序列问题（LCS）
理解如何通过动态规划求解两个序列的最长公共子序列，熟悉其算法原理及应用场景。
最小编辑距离（Levenshtein Distance）
掌握最小编辑距离的定义及动态规划实现，理解其在字符串相似度计算中的实际应用。
动态规划思想
学习将复杂问题分解为子问题并通过递推关系逐步求解。

二、实验环境

操作系统：Windows 或 Linux
编程语言：Python 3.x
开发工具：推荐使用 PyCharm、Jupyter Notebook 或 Sublime Text。

三、实验内容

1. 最长公共子序列问题（LCS）

基本原理：
给定两个字符串 X 和 ( Y )，找到它们的最长公共子序列。动态规划的核心是构建一个二维表 ( dp )，其中 dp[i][j] 表示 X[0:i] 和 Y[0:j] 的最长公共子序列长度。

算法步骤：

初始化二维表 ( dp )。
遍历 X 和 ( Y )，按以下规则更新 ( dp[i][j] )：
- 若 ( X[i-1] == Y[j-1] )：( dp[i][j] = dp[i-1][j-1] + 1 )。
- 否则 ( dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) )。
最后，dp[m][n] 为结果，其中 m, n 分别为 X 和 Y 的长度。

2. 最小编辑距离

基本原理：
计算将字符串 A 转换为 B 的最小操作次数。允许的操作包括插入、删除和替换。

算法步骤：

构建一个二维表 ( dp )，dp[i][j] 表示将 A[0:i] 转换为 B[0:j] 的最小操作数。
初始化边界条件：
- ( dp[i][0] = i )（全删）。
- ( dp[0][j] = j )（全插）。
遍历 A 和 ( B )，按以下规则更新 ( dp[i][j] )：
- 若 ( A[i-1] == B[j-1] )：( dp[i][j] = dp[i-1][j-1] )。
- 否则 ( dp[i][j] = 1 + \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) )。
dp[m][n] 即为结果，其中 m, n 分别为 A 和 B 的长度。

四、实验报告要求

基本思想说明
详细描述 LCS 和最小编辑距离的动态规划思想，包括状态定义和状态转移方程。
源码
提供清晰、注释详尽的 Python 实现。
算法分析
- 时间复杂度：分析循环嵌套次数。
- 空间复杂度：分析二维表的空间占用及优化可能。
实验结果截图
展示控制台输出结果及二维表状态。

五、文件提交说明

文件夹格式：
学号+姓名（如 "2024123456张三"）。
文件内容：
- 实验报告（Word 或 PDF 格式，命名为 实验报告_学号_姓名）。
- 可运行的 Python 源代码文件（如 lcs_and_edit_distance.py）。
上传路径：
上电云盘 -> 课程目录 -> 20241202 文件夹。

以下为代码示例：

最长公共子序列

def longest_common_subsequence(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
    
    return dp[m][n]

# Example
X = "ABCBDAB"
Y = "BDCAB"
print("LCS Length:", longest_common_subsequence(X, Y))

最小编辑距离

def min_edit_distance(A, B):
    m, n = len(A), len(B)
    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 A[i - 1] == B[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
    
    return dp[m][n]

# Example
A = "kitten"
B = "sitting"
print("Minimum Edit Distance:", min_edit_distance(A, B))

祝你实验顺利完成！如果有疑问，可以随时联系我。

4.1 KiB Raw Permalink Blame History Unescape Escape