python - 字符串的近似周期 - 将 Python 代码移植到 F#

Question

给定两个字符串 u 和 v，我们可以使用流行的 Levenshtein 算法计算编辑距离。使用 Sim 等人在 [1] 中介绍的方法。我能够使用以下代码计算 Python 中字符串的 k 近似周期

def wagnerFischerTable(a, b):
    D = [[0]]
    [D.append([i]) for i, s in enumerate(a, 1)]
    [D[0].append(j) for j, t in enumerate(b, 1)]

    for j, s in enumerate(b, 1):
        for i, t in enumerate(a, 1):
            if s == t:
                D[i].append(D[i-1][j-1])
            else:
                D[i].append(
                    min(
                        D[i-1][j] + 1,
                        D[i][j-1] + 1,
                        D[i-1][j-1] +1
                    )
                )
    return D

def simEtAlTables(s, p):
    D = []
    for i in xrange(len(s)):
        D.append(wagnerFischerTable(p, s[i:]))
    return D

def approx(s, p):
    D = simEtAlTables(s, p)
    t = [0]
    for i in xrange(1, len(s)+1):
        cmin = 9000
        for h in xrange(0, i):
            cmin = min(
                cmin,
                max(t[h], D[h][-1][i-h])
            )
        t.append(cmin)
    return t[len(s)]

我想将其移植到 F#，但尚未成功，我期待得到一些可能出现问题的反馈。

let inline min3 x y z = 
    min (min x y) z

let wagnerFischerTable (u: string) (v: string) =
    let m = u.Length
    let n = v.Length
    let d = Array2D.create (m + 1) (n + 1) 0

    for i = 0 to m do d.[i, 0] <- i
    for j = 0 to n do d.[0, j] <- j    

    for j = 1 to n do
        for i = 1 to m do
            if u.[i-1] = v.[j-1] then
                d.[i, j] <- d.[i-1, j-1]
            else
                d.[i, j] <-
                    min3
                        (d.[i-1, j  ] + 1) // a deletion
                        (d.[i  , j-1] + 1) // an insertion
                        (d.[i-1, j-1] + 1) // a substitution
    d

let simEtAlTables (u: string) (v: string) =
    let rec tabulate n lst =
        if n <> u.Length then
            tabulate (n+1) (lst @ [wagnerFischerTable (u.Substring(n)) v])
        else
            lst
    tabulate 0 []

let approx (u: string) (v: string) =
    let tables = simEtAlTables u v
    let rec kApprox i (ks: int list) =
        if i = u.Length + 1 then
            ks
        else
            let mutable curMin = 9000
            for h = 0 to i-1 do
                curMin <- min curMin (max (ks.Item h) ((tables.Item h).[i-h, v.Length - 1]))
            kApprox (i+1) (ks @ [curMin])
    List.head (List.rev (kApprox 1 [0]))

它“不起作用”的原因只是我得到了错误的值。 Python 代码通过了所有测试用例，而 F# 代码则未能通过所有测试。我认为函数 simEtAlTables 和/或 approx 中有错误。可能与索引有关，尤其是访问大约中的三维表列表。

所以这里是三个测试用例，它们应该涵盖不同的结果:

Test 1: approx "abcdabcabb" "abc" -> 1
Test 2: approx "abababababab" "ab" -> 0
Test 3: approx "abcdefghijklmn" "xyz" -> 3

[1] http://www.lirmm.fr/~rivals/ALGOSEQ/DOC/SimApprPeriodsTCS262.pdf

Answer 1

这根本不起作用(你的 Python 解决方案也不起作用)，但这里有一个更直接的 F# 转换。也许您可以使用它作为起点，并从那里使其更加实用(尽管我大胆猜测它不会提高性能)。

let wagnerFischerTable (a: string) (b: string) =
  let d = ResizeArray([ResizeArray([0])])
  for i = 1 to a.Length do d.Add(ResizeArray([i]))
  for j = 1 to b.Length do d.[0].Add(j)
  for j = 1 to b.Length do
    for i = 1 to a.Length do
      let s, t = b.[j-1], a.[i-1]
      if s = t then
        d.[i].Add(d.[i-1].[j-1])
      else
        d.[i].Add(
          Seq.min [
            d.[i-1].[j] + 1
            d.[i].[j-1] + 1
            d.[i-1].[j-1] + 1
          ])
  d

let simEtAlTables (s: string) (p: string) =
  let d = ResizeArray()
  for i = 0 to s.Length - 1 do
    d.Add(wagnerFischerTable p s.[i..])
  d

let approx (s: string) (p: string) =
  let d = simEtAlTables s p
  let t = ResizeArray([0])
  for i = 1 to s.Length do
    let mutable cmin = 9000
    for h = 0 to i - 1 do
      let dh = d.[h]
      cmin <- min cmin (max t.[h] dh.[dh.Count-1].[i-h])
    t.Add(cmin)
  t.[s.Length]