如何正常化Levenshtein距離以獲得最大對齊長度而不是字符串長度？

問題： 幾個R包的特點Levenshtein距離實現計算兩個字符串的相似性，例如， http://finzi.psych.upenn.edu/R/library/RecordLinkage/html/strcmp.html。計算的距離可以容易地對於字符串長度進行歸一化，例如，將Levenshtein距離除以所涉及的最長弦的長度或將其除以兩個弦的長度的平均值。然而，對於語言學中的一些應用（例如方言測量法和接受性多語言研究），建議將原始Levenshtein距離歸一化爲最長最小成本對準的長度（Heeringa，2004：130-132）。這往往會產生距離度量，從感性語言的角度來看更有意義。如何正常化Levenshtein距離以獲得最大對齊長度而不是字符串長度？

實施例： 德國字符串「tsYklUs」（Zyklus =週期）可被轉化成它的瑞典同源「sYkEl」（cyckel =（BI）循環）在7時隙對準具有兩個插入（I）和兩個取代（S）爲4. 歸Levenshtein距離共改造成本：4/7

（A）

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

另外，也可以將字符串轉換在一個8時隙對準有3個插入（I）和1個刪除（D），總對準成本爲4。歸Levenshtein距離：4/8

（B）

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

後者對準更有意義語言，因爲它對準[1]彼此-phonemes而不是與[E]和元音。

問：有誰知道任何一個R函數，讓我正常化最長的最低成本對齊，而不是字符串的長度適當的萊文斯坦的距離嗎？感謝您的輸入！

參考： W.J. Heeringa（2004），使用Levenshtein距離測量方言發音差異。博士論文，格羅寧根大學。 http://www.let.rug.nl/~heeringa/dialectology/thesis/

編輯 - 解決方案：我想我想出了一個解決方案。 adist函數可以返回對齊，並且似乎默認爲最長的低成本對齊。拿起上面的例子中，在這裏與sykel tsyklus關聯對齊：

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

要計算長度的標準化距離所推薦的Heeringa（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

此功能的LSO返回Heeringa的正確的標準化距離（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

來源

2012-04-13 jvh_ch

我的建議來包裝'DIAG（）''周圍有時normLev.fnc'產生一些stran ge結果。例如，'diag（normLev.fnc（a = c（「kat」，「hond」），b = c（「katze」，「hund」）））'產生'0.4 0.2'（應該是'0.4 0.25' ）。使用'mapply'可以更好地工作：'a = c（「kat」，「hond」）; b = c（「katze」，「hund」）; mapply（normLev.fnc，a = a，b = b）'。 – 2016-06-02 13:10:25

太棒了。你知道一個等價的函數，或者在Python中等同於adist（）嗎？我看到有一個[Python Levenshtein庫]（https://github.com/miohtama/python-Levenshtein），但它似乎並不支持正常化[ – Tadhg 2016-07-28 20:55:05

]有一個基於Python的[應用程序]（http：// www。 let.rug.nl/~kleiweg/L04/）用於包括可能有幫助的Levenshtein函數的方言測量法。 – 2016-08-08 11:15:13

在情況下，任何語言學家偶然發現了這個帖子，我想指出的是，由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

來源

2012-04-17 10:40:47

如何正常化Levenshtein距離以獲得最大對齊長度而不是字符串長度？

回答

相關問題