similarity - 如何标准化编辑距离以获得最大对齐长度而不是字符串长度？

Question

问题:一些 R 包具有 Levenshtein 距离实现，用于计算两个字符串的相似度，例如http://finzi.psych.upenn.edu/R/library/RecordLinkage/html/strcmp.html 。计算出的距离可以很容易地针对字符串长度进行标准化，例如将编辑距离除以所涉及的最长字符串的长度，或者将其除以两个字符串长度的平均值。然而，对于语言学中的某些应用(例如方言测量法和接受性多语言研究)，建议将原始 Levenshtein 距离归一化为最长最低成本对齐的长度(Heeringa，2004:130-132)。这往往会产生从感知语言学角度来看更有意义的距离测量。

示例:德语字符串“tsYklUs”(Zyklus = 循环)可以转换为其瑞典语同源词“sYkEl”(cyckel = (bi)cycle)，采用 7 槽对齐方式，总共有两次插入 (I) 和两次替换 (S)改造成本4.归一化编辑距离:4/7

(一)

t--s--Y--k--l--U--s
---s--Y--k--E--l---
===================
I-----------S--S--I = 4

还可以将字符串转换为 8 槽对齐方式，其中 3 次插入 (I) 和 1 次删除 (D)，总对齐成本也为 4。归一化编辑距离:4/8

(B)

t--s--Y--k-----l--U--S
---s--Y--k--E--l------
======================
I-----------D-----I--I = 4

后一种对齐在语言上更有意义，因为它将 [l] 音素彼此对齐，而不是与 [E] 和 [U] 元音对齐。

问题:有谁知道任何 R 函数可以让我标准化 Levenshtein 距离以获得最长的最低成本对齐，而不是正确的字符串长度？感谢您的投入!

引用:W.J. Heeeringa (2004)，使用编辑距离测量方言发音差异。博士论文，格罗宁根大学。 http://www.let.rug.nl/~heeringa/dialectology/thesis/

编辑 - 解决方案:我想我找到了一个解决方案。 adist 函数可以返回对齐方式，并且似乎默认为最长的低成本对齐方式。继续上面的例子，下面是从 sykel 到 tsyklus 的对齐方式:

> attr(adist("sykel", "tsyklus", counts = TRUE), "trafos")
     [,1]      
[1,] "IMMMDMII"

为了按照 Heeeringa (2004) 的建议计算长度归一化距离，我们可以编写一个适度的函数:

normLev.fnc <- function(a, b) {
  drop(adist(a, b) / nchar(attr(adist(a, b, counts = TRUE), "trafos")))
}

对于上面的示例，这将返回

> normLev.fnc("sykel", "tsyklus")
[1] 0.5

此函数还返回 Heeeringa (2004: 131) 示例的正确归一化距离:

> normLev.fnc("bine", "bEi")
[1] 0.6
> normLev.fnc("kaninçen", "konEin")
[1] 0.5555556
> normLev.fnc("kenEeri", "kenArje")
[1] 0.5

比较多对字符串:

> L1 <- c("bine", "kaninçen", "kenEeri")
> L2 <- c("bEi",  "konEin", "kenArje")
> diag(normLev.fnc(L1, L2))
[1] 0.6000000 0.5555556 0.5000000

Answer 1

如果任何语言学家偶然发现这篇文章，我想指出 RecordLinkage 包提供的算法不一定是比较非 ASCII 字符串的最佳算法，例如:

> levenshteinSim("väg", "way")
[1] -0.3333333
> levenshteinDist("väg", "way")
[1] 4
> levenshteinDist("väg", "wäy")
[1] 2
> levenshteinDist("väg", "wüy")
[1] 3