通過Python中的Levenshtein對字符串列表進行分組

Question

我創建了一個腳本來計算兩個字符串的Levenshtein距離。現在我想根據Levenshtein距離對字符串列表進行分組。 （如果字符串的距離低於閾值，它們將處於同一個羣組中）：

目前，我已經做了一些事情，但似乎沒有工作。下面是一個僞代碼：

for every string in list: 
    create a new cluster with this string 
    remove the string from the list 
    for every string in the remaining list: 
     if distance(string1,string2) < threshold: 
      add string2 to the cluster 
      remove string2 from the list 

這裏是因爲一些用戶問它真正的代碼：

cid = 0 
clusters = {} 

numb = range(len(mylist)) 
for i in numb: 
     cls = [mylist[i]] 
     numb.remove(i) 
     for j in numb: 
      if distance(mylist[i],mylist[j]) <= threshold: 
       cls.append(mylist[j]) 
       numb.remove(j) 

     clusters[cid] = cls  
     cid+=1 
     cls = [] 

Answer 1

您將要從你遍歷列表項。這將改變索引並導致意外行爲，您應該將需要的值複製到新列表中，而不是修改正在迭代的列表。

Answer 2

下面是一些清理代碼：

clusters = defaultdict(list) 

numb = range(len(mylist)) 
for i in numb: 
     for j in range(i+1, len(numb)): 
      if distance(mylist[i],mylist[j]) <= threshold: 
       clusters[i].append(mylist[j]) 
       clusters[j].append(mylist[i])