在Python中編輯距離

我正在用Python編寫一個拼寫檢查程序。我有一個有效單詞列表（字典），我需要輸出一個單詞列表，這個單詞列表中的單詞與給定的無效單詞的編輯距離爲2。在Python中編輯距離

我知道我需要首先生成一個與無效單詞的編輯距離爲1的列表（然後在所有生成的單詞上再次運行該列表）。我有三種方法，插入（...），刪除（...）和更改（...），它們應該輸出編輯距離爲1的單詞列表，其中inserts輸出所有有效單詞的多個字母給定的單詞刪除將輸出所有有效的單詞少一個字母，並更改輸出所有有效的單詞一個不同的字母。

我檢查了一堆地方，但我似乎無法找到描述此過程的算法。我提出的所有想法都涉及多次循環遍歷字典列表，這將非常耗時。如果有人能夠提供一些見解，我會非常感激。

來源

2010-03-17 Mel

您可能需要查看Peter Norvig的拼寫檢查程序（http://norvig.com/spell-correct.html）並對其進行修改以適合您的需求。 – 2010-03-17 06:08:57

您描述的特定算法稱爲Levenshtein距離。谷歌快速拋出了幾個Python庫和食譜來計算它。

來源

2010-03-17 07:57:41

#this calculates edit distance not levenstein edit distance 
word1="rice" 

word2="ice" 

len_1=len(word1) 

len_2=len(word2) 

x =[[0]*(len_2+1) for _ in range(len_1+1)]#the matrix whose last element ->edit distance 

for i in range(0,len_1+1): #initialization of base case values 

    x[i][0]=i 
for j in range(0,len_2+1): 

    x[0][j]=j 
for i in range (1,len_1+1): 

    for j in range(1,len_2+1): 

     if word1[i-1]==word2[j-1]: 
      x[i][j] = x[i-1][j-1] 

     else : 
      x[i][j]= min(x[i][j-1],x[i-1][j],x[i-1][j-1])+1 

print x[i][j]

來源

2013-11-12 12:16:49

這裏是我的版本Levenshtein距離

 
def edit_distance(s1, s2): 
    m=len(s1)+1 
    n=len(s2)+1 

    tbl = {} 
    for i in range(m): tbl[i,0]=i 
    for j in range(n): tbl[0,j]=j 
    for i in range(1, m): 
     for j in range(1, n): 
      cost = 0 if s1[i-1] == s2[j-1] else 1 
      tbl[i,j] = min(tbl[i, j-1]+1, tbl[i-1, j]+1, tbl[i-1, j-1]+cost) 

    return tbl[i,j] 

print(edit_distance("Helloworld", "HalloWorld"))

來源

2014-06-11 20:56:01 Santosh

你能解釋你的代碼嗎？這似乎是一個很好的解決方案，但很難理解 – python 2015-10-23 04:53:58

它是在Python中，自我解釋。它正在實施一個動態程序。 – Santosh 2015-10-25 03:11:39

簡單直觀，易於理解。我喜歡它！ – 2018-01-06 21:22:09

你正在尋找被稱爲編輯距離，這裏的東西是nice explanation on wiki。如何定義兩個單詞之間的距離以及所需的稱爲Levenshtein距離的方法有很多，這裏是python中的DP實現。

def levenshteinDistance(s1, s2): 
    if len(s1) > len(s2): 
     s1, s2 = s2, s1 

    distances = range(len(s1) + 1) 
    for i2, c2 in enumerate(s2): 
     distances_ = [i2+1] 
     for i1, c1 in enumerate(s1): 
      if c1 == c2: 
       distances_.append(distances[i1]) 
      else: 
       distances_.append(1 + min((distances[i1], distances[i1 + 1], distances_[-1]))) 
     distances = distances_ 
    return distances[-1]

and a couple of more implementations are here。

來源

2015-09-14 06:52:27

DP代表動態編程。 – 2017-10-19 06:20:38

而是用Levenshtein距離算法中使用BK樹或TRIE去，因爲這些算法有更低的複雜性，然後編輯距離。一個很好的瀏覽這些話題將給予詳細的描述。

這個link會幫助你更多地瞭解拼寫檢查。

來源

2017-04-01 12:54:18 jt26

在Python中編輯距離

回答

相關問題