水母的Damerau-Levenshtein距離計算車？

Question

我正在嘗試使用Jellyfish來處理模糊字符串。我注意到Damerau–Levenshtein distance算法的一些奇怪行爲。例如：

import jellyfish as jf 
In [0]: jf.damerau_levenshtein_distance('ZX', 'XYZ') 
Out[0]: 3 
In [1]: jf.damerau_levenshtein_distance('BADC', 'ABCD') 
Out[1]: 3 

依我看兩者都應該得分2.

在第一示例：

1. ZX→XZ（轉置相鄰的字符）
2. XZ→XYZ（插入Y）

在第二個範例：

1. BACD→ABDC（轉置相鄰BA字符）
2. ABDC→ABCD（轉置相鄰DC字符）

這是有點毛病算法，還是我誤解了措施？任何指導將不勝感激。

編輯

只是爲了讓事情更奇怪的，我還注意以下事項：

In [3]: jf.damerau_levenshtein_distance('jellyifhs', 'jellyfish') 
Out[3]: 2 
In [4]: jf.damerau_levenshtein_distance('ifhs', 'fish') 
Out[4]L 3 

這是特別奇怪，因爲編輯的數量不應僅僅是兩個在這兩個例子，但它們是完全相同的編輯次數：

在第三示例：

1. jellyifhs→jellyfihs（轉置相鄰的字符if）
2. jellyfihs→jellyfish（轉置相鄰的字符hs）

在第四示例：

1. ifhs→fihs（轉置相鄰字符if ）
2. fihs→fish（轉置相鄰的字符hs）

Answer 1

從

wikipedia

在信息理論和計算機科學，Damerau-Levenshtein距離（弗雷德裏克·J·達梅勞和Vladimir I.得名Levenshtein）[引用需要]是兩個字符串之間的「距離」（字符串度量），即有限的符號序列，通過計算將一個字符串轉換爲另一個字符串所需的最小操作次數給出，其中操作被定義爲插入，刪除或替換單個字符，或轉換兩個相鄰字符。

但是，如果你繼續讀下去，

就拿CA和ABC之間的編輯距離。因爲CA→AC→ABC，所以Damerau-Levenshtein距離LD（CA，ABC）= 2，但是因爲如果使用操作CA→AC，所以不是最佳的字符串對準距離OSA（CA，ABC）= 3可能使用AC - > ABC，因爲這會要求子字符串被多次編輯，這在OSA中是不允許的，因此最短的操作順序是CA-> A-> AB-> ABC。請注意，對於最佳字符串對齊距離，三角形不等式不成立：OSA（CA，AC）+ OSA（AC，ABC）< OSA（CA，ABC），因此它不是一個真正的度量標準。

編輯：

在source服用後一看，很明顯，該函數計算OSA，而不是Damerau–Levenshtein distance。