Levenshtein 编辑距离与多字符单位的分隔符

Question

我搜索了 R 函数 adist、agrep、match 和 stringdist，但没有找到使用分隔符计算编辑距离的方法。

现有编辑距离：

“that” & ”fat” = 2  i.e., adist("that","fat")

所需函数将使用分隔符来表示多字符单元：

“th.a.t” & ”f.a.t” = 1

Answer 1

Levenshtein距离很容易实现，直接计算即可。这是 Wagner-Fischer 算法的快速无保证版本（参见维基百科）

vecLeven <- function(s, t) {
  d <- matrix(0, nrow = length(s) + 1, ncol=length(t) + 1)
  d[, 1] <- (1:nrow(d)) - 1
  d[1,] <- (1:ncol(d))-1
  for (i in 1:length(s))  {
    for (j in 1:length(t)) {
      d[i+1, j+1] <- min(
        d[i, j+1] + 1, # deletion
        d[i+1, j] + 1, # insertion
        d[i, j] + if (s[i] == t[j]) 0 else 1 # substitution
      )
    }
  }

    d[nrow(d), ncol(d)]
}

sepLeven <- function(s, t, sep=".") {
  mapply(vecLeven, 
         strsplit(s, sep, fixed=TRUE), 
         strsplit(t, sep, fixed=TRUE))
}

sepLeven(c("th.a.t", "t.e.s.t"), c("f.a.t", "f.e.t"), sep=".")
# output: [1] 1 2

Levenshtein 编辑距离与多字符单位的分隔符

Levenshtein edit distance with separator for multi-character units

r

levenshtein-distance