05月23日
Edit Distance 问题在两种编程范式下的求解

本文由 Coding 用户 jadetang 投稿并授权。

前言

Edit Distance,中文叫做编辑距离。编辑距离在文本处理等领域是一个重要的问题,以下是摘自于 百度百科 的定义:

编辑距离(Edit Distance),又称 Levenshtein 距离,是指两个字串之间由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。

如果分别用R(replace),I(insert),D(delete),M(Match)代表替换、插入、删除、匹配操作,那么 vintnerwriters 的转换过程,可以如图所示

编辑距离

从图中可以看出,*vintner*到*writeres*的最短编辑距离为5。编辑距离问题即求解两个字符串之间的最小距离,定义函数如下:

int minDistance(String word1, String word2) {

指令式编程范式下使用动态递归求解

状态定义

这一类问题,可以通过动态递归的方式来解决。

定义 对于两个字符串 S1 和 S2,D( i, j ) 表示两个字符子串 S1[1..i] 和 S2[1..j] 之间的最短编辑距离。

对于两个字符串,长度分别为 n 和 m ,那么 D( n,m ) 就是他们的之间的最短编辑距离,为了计算 D( n,m )需要计算所有的 D( i,j ),其中 0<=i<=M, 0<=j<=N。对于基本情况,可以得到 D(i, 0)=0, D(0, j)=0

状态转移方程及其证明

动态递归问题中,确定了初始状态以后,就需要推导出问题的状态转移方程,编辑距离问题的状态转移方程是:
D(i,j)= min[D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+t(i,j)]

其中

t(i,j) = S1.charAt(i) == S2.charAt(j) ? 0 : 1

以下是证明:

命题1 : D( i, j )的取值,只可能为 D( i-1, j ) + 1, D( i, j - 1 )+1, D( i - 1, j - 1 ) + t ( i, j ) 这三者中的一个。

考虑把 S1[1..i] 转换到 S2[1..j] 这个过程,对于最后一步编辑,这一步的动作只可能是R,I,D,M中的一种。现假设最后一步编辑的动作是 Insert ,即表示把 S2[j] 插入到正在转化的 S1 的末尾。那么对于这个动作之前的连续的编辑动作,表示的是把 S1[1..i] 转换到 S2[1..j-1] 这个过程,这个过程的最短编辑距离根据之前的定义表示为 D(i,j-1) ,那么由此可以得出 $D( i, j ) = D( i, j - 1 ) + 1$ 。同理,对于最后一步动作是D的情况,$ D( i, j ) = D( i - 1 , j ) + 1$。而对于最后一步东西是M或者R的情况,$D( i, j ) = D( i - 1 , j - 1 ) + t ( i , j )$。结合命题1和 D( i , j )的定义,状态转移方程的正确性得正。

LeetCode上,就有一道这样的题目,以下是用上述动态规划的思路的解法,已经AC:

public int minDistance(String word1, String word2) {
        int w1length = word1.length();
        int w2length = word2.length();
        int[][] dp = new int[w1length+1][w2length+1];
        for(int l = 0; l<= w2length; l++ ){
            dp[0][l] = l;
        }
        for(int l = 0; l<= w1length; l++ ){
            dp[l][0] = l;
        }
        for(int i = 1; i<=w1length; i++){
            for(int j=1; j<=w2length;j++){
                if(word1.charAt(i-1) == word2.charAt(j-1)){
                    dp[i][j] = Math.min(dp[i-1][j-1],Math.min(dp[i-1][j]+1,dp[i][j-1]+1));
                }else{
                   dp[i][j] = Math.min(dp[i-1][j-1]+1,Math.min(dp[i-1][j]+1,dp[i][j-1]+1));

                }
            }
        }
        return dp[w1length][w2length];
    }

函数式编程范式下的求解

之前说到的动态递归的算法,都在指令式编程即 imperative programming 范式下讨论的,但是在程序开发中,还有一种范式称为函数式编程即 functional programming。Scala 作为一种在 JVM 上运行的语句,既有函数式又有面对对象的特点,下面我们用函数式的方式,用 Scala 来求解最小编辑距离问题。

对问题建立模型

这里的模型,指的是如何将这个问题 model 成程序中的类型,这里的类型包括 Scala 中内置的数据类型,也包括自定义的类型,以下是我根据几种编辑步骤定义的类型:

trait Edit
case class Replace(val from: Char, val to: Char) extends Edit
case class Match(val c: Char) extends Edit
case class Delete(val c: Char) extends Edit
case class Insert(val c: Char) extends Edit

每个 case class 对应一种编辑动作,所有的 case class 都继承自 。为了求解两个字符串之间的最小编辑距离,先求解一个字符串到另外一个字符串需要经过多少步的编辑步骤,函数的定义如下:

def transform(s1: List[Char], s2: List[Char]): List[Edit]

注:在Scala中,String 可以很方便的转化成 List[Char] 。

问题求解

对于 base case, 当 s2 为空字符串的时候,s1 只需要把每个字符给删掉,就能转换成 s2;当 s1 为空字符串的时候,只需要把 s2 中所有的字符按次序插入 s1,就能转化成 s1 。把这段话语直白的翻译成代码,可以得到函数的部分实现:

def transform(s1: List[Char], s2: List[Char]): List[Edit] = {
  (s1, s2) match {
    case (s1, Nil) => s1 map (x => Delete(x))
    case (Nil, s2) => s2 map (x => Insert(x))
  }
}

处理了 base case,需要处理更加一般的情况。当 s1 和 s2 的第一个字符相等的时候,则生成一个 Match 动作,接着处理剩下的字符子串。如果 s1 和 s2 的第一个字符串不相等的时候,则有三种情况:
1. 删掉 s1 的第一个字符,将剩下字符子串 s1[2..n] 转化成 s2。
2. 插入 s2 的第一个字符,将 s1 转化成 s2 剩下的字符子串 s2[2..n]。
3. 将 s1 的第一个字符替换成 s2 的第一个字符,将字符子串 s1[2..n] 转化成 s2[2..n]。

综上,我们可以得到 tranform 函数的完整实现

def transform(s1: List[Char], s2: List[Char]): List[Edit] = {
  (s1, s2) match {
    case (s1, Nil) => s1 map (x => Delete(x))
    case (Nil, s2) => s2 map (x => Insert(x))
    case (x :: xs, y :: ys) => if (x == y) {
      Match(y) :: transform(xs, ys) //s1和s2的第一个字符相等的时候,则生成一个Match动作
    }
    else {
      best(List(Delete(x) :: transform(xs, s2), Insert(y) :: transform(s1, ys), Replace(x, y) :: transform(xs, ys)))
    }
  }
}

其中best函数求解多个 List[Edit] 中的最优值,函数的实现为:

def best(edits: List[List[Edit]]): List[Edit] = edits match {
  case (x :: Nil) => x
  case (x :: xs) => {
    val b = best(xs)
    if (cost(x) <= cost(b)) x else b
  }
}

cost 函数求解一个 List[Edit] 中所需要的编辑步骤,因为 Match 步骤其实是不需要做任何动作的,那么计算 cost 的时候,只需要把 Match 步骤给过滤掉就行,在 Scala中可以用一行函数来实现:

def cost(edits: List[Edit]): Int = edits.filterNot(x => x.isInstanceOf[Match]).length

我们可以测试一下:

val s1 = "vintner"
val s2 = "writers"
val edits = transform(s1.toList, s2.toList)
val result = s"edit distance between $s1 and $s2 is" + cost(edits)
//result
edits: List[Edit] = List(Insert(w), Replace(v,r), Match(i), Delete(n), Match(t), Delete(n), Match(e), Match(r), Insert(s))
result: String = edit distance between vintner and writers is 5

总结

至此,这道问题用scala就解决了,其实所做的无非就是把建立模型和解决问题的思考过程非常直白的翻译成代码,因为函数式语言描述的更多是数学,和人类的思考过程更加相近,而过程式编程描述的更多的是机器语言,对于一些问题的求解没有那么的直观。

参考书籍

  1. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology
  2. Haskell: The Craft of Functional Programming

此问题的Haskell解法,来自于*Haskell: The Craft of Functional Programming*一书,原书代码如下:

data Edit = Change Char|
            Copy|
            Delete|
            Insert Char|
            Kill
            deriving(Eq,Show)

transform :: String->String->[Edit]
transform [] [] = []
transform xs [] = [Kill]
transfrom [] ys = map Insert ys
transform (x:xs)(y:ys)
    | x == y = Copy: : transform xs ys
    | otherwise = best [Delete : transform xs (y:ys), Insert y : transform (x:xs) ys, Change y : transform xs ys]
best :: [[Edit]] ->[Edit]
best [x] = x
best (x:xs)
    | cost x <= cost b = x
    | otherwise = b
        where 
        b = best xs
cost :: [Edit] -> Int
cost = length . filter(/=Copy)

5条评论

@skyli 动规,扎心了

CharlieJiang1 个月前回复

3楼吗?我只是来水一下的。

xiaoyu971 个月前回复

沙发

coding-44421 个月前回复

OIer表示做过此题。

skyli1 个月前回复

沙发吗,不敢信了

imocco1 个月前回复