Levenshtein編輯距離Python

這段代碼返回2項的Levenshtein編輯距離。我如何做到這一點，以便插入和刪除只花費0.5而不是1？替換仍然需要花費1.Levenshtein編輯距離Python

def substCost(x,y): 
    if x == y: 
     return 0 
    else: 
     return 1 

def levenshtein(target, source): 
    i = len(target); j = len(source) 
    if i == 0: 
     return j 
    elif j == 0: 
     return i 

    return(min(levenshtein(target[:i-1],source)+1, 
      levenshtein(target, source[:j-1])+1, 
      levenshtein(target[:i-1], source[:j-1])+substCost(source[j-1],target[i-1])))

來源

2016-09-19 Brutalized

請修復您問題的縮進，目前無法讀取。即使如此，把所有東西放在一條線上也不是慣用的python，這使得很難回答。 – roganjosh

你到目前爲止嘗試過什麼？在請求某人爲你解決這個問題之前，你應該發佈一個嘗試 –

用另一個元音代替元音是否也花費0.5，或者它只是插入和刪除比正常便宜？用元音替換非元音怎麼辦？反之亦然？ – Blckknght

有兩個地方需要考慮降低添加或刪除元音的成本。它們是函數的基本情況下的return j和return i行，以及在前兩次遞歸調用後的min調用中的+1。

我們需要將其中的每一個改爲使用「三元」表達式：0.5 if ch in 'aeiou' else 1來代替假設每個角色添加或刪除的成本爲1。

對於鹼的情況下，我們可以在發電機表達式包括所述三元表達sum調用替換的返回值：

if i == 0: 
    return sum(0.5 if ch in 'aeiou' else 1 for ch in source) 
elif j == 0: 
    return sum(0.5 if ch in 'aeiou' else 1 for ch in target)

對於後面的情況下，我們可以用三元表達式本身更換+1（與索引，而不是ch迭代變量）：

return min(levenshtein(target[:i-1],source) + (0.5 if target[-1] in 'aeiou' else 1), 
      levenshtein(target, source[:j-1]) + (0.5 if source[-1] in 'aeiou' else 1), 
      levenshtein(target[:i-1], source[:j-1])+substCost(source[j-1],target[i-1]))

如果要概括這一點，你可以從移動三元表達到其自身的功能，命名爲舒美特像addCost，並從levenshtein函數中的代碼調用它。

來源

2016-09-19 21:23:00 Blckknght

Levenshtein編輯距離Python

回答

相關問題