如何根据编辑距离对字符串列表进行有效排序？

Question

我正在尝试使用levenshtein距离通过编辑距离对列表进行排序

def suggest(dic, word, distance, maxSugestions=5):
   list = []
   for i in range(1, 200):
       for word1 in sorted(dic):
           if distance(word1, word) == i:
               list.append(word1)
               if len(list) == maxSugestions:
                   return list

这是我当前的函数，它接收一个字符串列表（这个列表大约有43000个字符串），一个我想要比较的字，一个返回两个字符串之间的编辑距离和列表应该具有的maxSugestions整数的函数

这是当前距离函数：

def levDistance(str1, str2):
   matrix = [[0 for x in range(len(str2) + 1)] for x in range(len(str1) + 1)]

   for i in range(len(str1) + 1):
       for j in range(len(str2) + 1):
           if i == 0:
               matrix[i][j] = j
           elif j == 0:
               matrix[i][j] = i
           elif str1[i-1] == str2[j-1]:
               matrix[i][j] = matrix[i-1][j-1]
           else:
               matrix[i][j] = 1 + min(matrix[i][j-1], matrix[i-1][j], matrix[i-1][j-1])    

   return matrix[len(str1)][len(str2)]

当前的suggest（）函数可以工作，但是我需要对它进行优化，因为它花费的时间太长了，我不知道该怎么做。任何帮助都是感激的。多谢各位

Answer 1

我试过这个方法，希望对你有用

def edit_distance(word, string_to_take_distance_with = "someString"):
    '''
    Description:
        give you the edit distance between 2 words
        word                            : String 1 (dynamic) 
        string_to_take_distance_with    : String 2 (static)
        
    '''
    
    
    length_of_string  = len(word)+1
    length_of_string2 = len(string_to_take_distance_with)+1

    tbl = {}
    for i in range(length_of_string): tbl[i,0]=i
    for j in range(length_of_string2): tbl[0,j]=j
    for i in range(1, length_of_string):
        for j in range(1, length_of_string2):
            cost = 0 if word[i-1] == string_to_take_distance_with[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]




sorted(["hello","helo","aen"], key=edit_distance)