问题: 一些 R 包具有用于计算两个字符串相似度的 Levenshtein 距离实现,例如http://finzi.psych.upenn.edu/R/library/RecordLinkage/html/strcmp.html。计算的距离可以很容易地针对字符串长度进行归一化,例如通过将 Levenshtein 距离除以所涉及的最长字符串的长度或将其除以两个字符串的长度的平均值。然而,对于语言学中的某些应用(例如方言学和接受性多语言研究),建议将原始 Levenshtein 距离标准化为最长最小成本对齐的长度(Heeringa,2004:130-132)。从感知语言的角度来看,这往往会产生更有意义的距离度量。
示例: 德语字符串“tsYklUs”(Zyklus = cycle)可以在 7 槽对齐中转换成它的瑞典同源词“sYkEl”(cyckel = (bi)cycle),其中两个插入 (I) 和两个替换 (S)总转换成本为 4。归一化 Levenshtein 距离:4/7
(一个)
t--s--Y--k--l--U--s
---s--Y--k--E--l---
===================
I-----------S--S--I = 4
也可以将字符串转换为具有 3 个插入 (I) 和 1 个删除 (D) 的 8 槽对齐方式,总对齐成本也为 4。归一化 Levenshtein 距离:4/8
(乙)
t--s--Y--k-----l--U--S
---s--Y--k--E--l------
======================
I-----------D-----I--I = 4
后一种对齐在语言上更有意义,因为它将 [l] 音素彼此对齐,而不是与 [E] 和 [U] 元音对齐。
问题: 有谁知道任何 R 函数可以让我标准化 Levenshtein 距离以获得最长的最低成本对齐,而不是正确的字符串长度?感谢您的输入!
参考: WJ Heeringa (2004),使用 Levenshtein 距离测量方言发音差异。博士论文,格罗宁根大学。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