请求协助用递归实现F#版Levenshtein距离

当然可以！我来帮你用F#实现递归版本的Levenshtein距离，完全贴合你提到的数学定义来写。

首先先明确递归的核心逻辑，和你给出的数学定义完全一致：

• 如果其中一个字符串是空串，距离就是另一个字符串的长度（需要插入所有字符）
• 如果两个字符串的最后一个字符相同，距离等于去掉最后一个字符后的子串距离
• 如果最后一个字符不同，距离就是替换、删除、插入这三种操作的最小值加1，其中替换的代价是1（当字符不同时），否则为0

基础递归实现 #

这个版本非常直观，直接用F#的模式匹配来处理边界情况和递归分支：

let rec levenshtein (a: string) (b: string) =
    match a.Length, b.Length with
    // 边界情况：其中一个字符串为空
    | 0, len -> len
    | len, 0 -> len
    | lenA, lenB ->
        // 获取两个字符串的最后一个字符
        let lastCharA = a.[lenA - 1]
        let lastCharB = b.[lenB - 1]
        // 计算替换操作的代价：字符相同则代价为0，否则为1
        let replaceCost = if lastCharA = lastCharB then 0 else 1
        // 计算三种可能操作的距离
        let replace = levenshtein (a.Substring(0, lenA - 1)) (b.Substring(0, lenB - 1)) + replaceCost
        let delete = levenshtein (a.Substring(0, lenA - 1)) b + 1
        let insert = levenshtein a (b.Substring(0, lenB - 1)) + 1
        // 返回三种操作中的最小值
        min replace (min delete insert)

测试示例 #

你可以用这些例子验证代码是否正确：

printfn "%d" (levenshtein "kitten" "sitting") // 输出3，符合预期
printfn "%d" (levenshtein "hello" "world")   // 输出4
printfn "%d" (levenshtein "" "test")         // 输出4
printfn "%d" (levenshtein "same" "same")     // 输出0

优化版：带备忘录的递归 #

基础递归版本虽然清晰，但对于较长的字符串会有大量重复计算（比如多次计算相同子串的距离）。我们可以用**备忘录（Memoization）**来缓存已经计算过的结果，大幅提升效率：

open System.Collections.Generic

let memoizedLevenshtein =
    // 用字典缓存已经计算过的字符串对的距离
    let cache = Dictionary<string * string, int>()
    
    let rec calculate a b =
        // 先检查缓存中是否已有结果
        match cache.TryGetValue((a, b)) with
        | true, value -> value
        | false, _ ->
            let result =
                match a.Length, b.Length with
                | 0, len -> len
                | len, 0 -> len
                | lenA, lenB ->
                    let lastCharA = a.[lenA - 1]
                    let lastCharB = b.[lenB - 1]
                    let replaceCost = if lastCharA = lastCharB then 0 else 1
                    let replace = calculate (a.Substring(0, lenA - 1)) (b.Substring(0, lenB - 1)) + replaceCost
                    let delete = calculate (a.Substring(0, lenA - 1)) b + 1
                    let insert = calculate a (b.Substring(0, lenB - 1)) + 1
                    min replace (min delete insert)
            // 将结果存入缓存
            cache.Add((a, b), result)
            result
    // 返回缓存版的计算函数
    calculate

使用缓存版的示例 #

printfn "%d" (memoizedLevenshtein "abcdefghij" "jihgfedcba") // 输出8，比基础版快很多

内容的提问来源于stack exchange，提问作者Saager