信息检索——两字符串间编辑距离计算

实验目的：通过实验，使学生掌握检索系统中为实现拼写校正，计算两个字符串之间的编辑距离的方法。
实验内容：采用动态规划算法，编程计算两个字符串之间的编辑距离。
实验要求：
输入：两个字符串
输出：两个字符串的距离
编程语言：python

def distance(s1,s2):
    m= [[0]*(len(s2)+1) for i in range(len(s1)+1)]
    for i in range(len(s1)+1):
        m[i][0]=i
    for j in range(len(s2)+1):
        m[0][j]=j
    for i in range(1,len(s1)+1):
        for j in range(1,len(s2)+1):
            if s1[i-1]==s2[j-1]:
                m[i][j]=min(m[i-1][j]+1,m[i][j-1]+1,m[i-1][j-1])
            else:
                m[i][j]=min(m[i-1][j]+1,m[i][j-1]+1,m[i-1][j-1]+1)
    return m[len(s1)][len(s2)]
a="snow"
b="osio"
print("字符串{} 与字符串 {} 的编辑距离是{}".format(a,b,distance(a,b)))

运行结果如下：