使用Levenshtein距離匹配的匹配的百分比等級

我想使用Levenshtein距離算法將匹配單個搜索項與可能匹配的字典進行匹配。算法返回一個距離，表示爲將搜索字符串轉換爲匹配字符串所需的操作次數。我想將結果呈現在排名最高的「N」（比如說10）匹配的百分比列表中。使用Levenshtein距離匹配的匹配的百分比等級

由於搜索字符串可能比單個字典字符串更長或更短，因此將以百分比形式表示距離的適當邏輯將定性反映「查詢結果」對查詢的每個結果的接近程度字符串，100％表示完全匹配。

我考慮以下選項：

Q = query string 
M = matched string 
PM = Percentage Match 
Option 1. PMi = (1 - Lev_distance(Q, Mi)/Strlen(Q)) * 100 
Option 2. PMi = (1 - Lev_distance(Q, Mi)/max(Strlen(Q), strlen(Mi))) * 100

選項1具有負百分比的可能性的情況下的距離比搜索字符串長度，其中匹配字符串是長越大。例如，與「ABC Corp.」匹配的查詢「ABC」會導致負面的比賽百分比。

選項2似乎沒有給出一組Mi的一致百分比，因爲每個計算可能會使用不同的分母，因此得到的百分比值將不會被標準化。

我只能想到的其他方式是將lev_distance與字符串長度進行比較，而是將頂部「N」個匹配的比較距離顯示爲逆百分位數（100百分位數）。

有什麼想法？有更好的方法嗎？因爲Levenshtein距離可能是模糊匹配最常用的算法，所以我一定會錯過一些東西，這肯定是一個非常普遍的問題。

來源

2012-05-01 user1368587

結果是否定的，然後簡單地返回0？ PS：我已經發布的問題也在這裏http://math.stackexchange.com/questions/1776860/convert-levenshtein-distance-to-percents –

我不明白什麼是與Option2的問題，因爲我已經實現了完全你描述它的相同的邏輯，似乎正常工作。你能解釋一下嗎？ – Roberto14

(1 - (levNum/Math.max(s.length,t.length))) *100

應該是正確的

來源

2013-01-09 14:51:50

最初的問題已經有了這個解決方案作爲「選項2」。他正在尋找解決問題的方法。 –

這基本上是我的問題提到的選項2。不過，讓我來演示一下這種方法的問題。

Q = "ABC Corp" (len = 8) 
M1 = "ABC" 
M2 = "ABC Corporati" 
M3 = "ABC Corp"

我已經選擇M1和M2以使得它們的列夫距離相同（5次）。使用選項2，本場比賽的百分比是

M1 = (1 - 5/8)*100 = 37.5% 
M2 = (1 - 5/13)*100 = 61.5% 
M3 = 100%

正如你可以看到，如果我的順序呈現比賽，有M1和M2之間的巨大級差，即使他們有相同的列弗距離。你看到問題了嗎？

來源

2013-01-11 01:01:45

經過一段時間我猜這是正確的做法。假設你有很短的字符串，其LevDisstance是5.假設你有很長的字符串，其LevDist也是5.然後說最短的字符串不像是長的字符串是正確的。 –

Tbh，我沒有在那裏看到任何問題，因爲@Wakan Tanka說，距離較長的字符串意味着更多的字符在它們之間匹配。因此，沒有問題，Option2是一個有效的選項。 – Roberto14

我對這個問題的解決方法是計算最大允許的操作，這就是Levenshtein距離。我使用的公式是：

percent = 0.75; // at least 75% of string must match 
maxOperationsFirst = s1.length() - s1.length() * percent; 
maxOperationsSecond = s2.length() - s2.length() * percent; 
maxOperations = round(min(maxOperationsFirst, maxOperationsSecond));

它計算每個字符串的最大操作數，我相信這個計算很容易理解。我使用這兩個結果的最小值並將其舍入到最接近的整數。你可以跳過這部分，只使用兩個字符串中的最大操作值，這取決於你的數據。

獲得最大操作次數後，可以將其與levenshtein結果進行比較，並確定該字符串是否可接受。通過這種方式，您可以使用任何擴展的levenshtein方法，例如Damerau–Levenshtein distance，其計算拼寫錯誤，例如測試 - > tset，只能作爲1次操作，這在檢查用戶輸入時經常發生拼寫錯誤是非常有用的。

我希望這可以幫助你瞭解如何解決這個問題。

來源

2013-08-14 23:11:45

對我來說似乎很好。 – tonix

我有類似的問題，這個線程幫我找出解決方案。希望它也能幫助別人。

int levDis = Lev_distance(Q, Mi) 
int bigger = max(strlen(Q), strlen(Mi)) 
double pct = (bigger - levDis)/bigger

它應該返回100％，如果兩個字符串完全相同，0％，如果他們是完全以不同。

（抱歉，如果我的英語不太好）

來源

2014-02-11 14:49:52

這是不正確的，因爲它給出了不同的結果'（「ABC公司」，「ABC」）和'（「ABC Corp」，「ABC Corporati」）' –

這是錯誤的答案。 –

這個怎麼樣：

100 - (((2*Lev_distance(Q, Mi))/(Q.length + Mi.length)) * 100)

它詳細介紹了(Q, M1)和那你的第一個選項，但在相同的距離(Q,M2)

來源

2016-05-08 09:06:52

使用Levenshtein距離匹配的匹配的百分比等級

回答

相關問題