Расчет расстояния levenshtein в списке Python

Question

У меня есть список строк, и я хочу отфильтровать строки, которые слишком похожи на основе расстояния levenstein. Поэтому, если lev(list[0], list[10]) < 50; затем del list[10]. Есть ли способ, которым я могу рассчитать такое расстояние между каждой парой строк в списке, более эффективно? Благодаря!!

data2= [] 
for i in data: 
    for index, j in enumerate(data): 
     s = levenshtein(i, j) 
     if s < 50: 
      del data[index] 
    data2.append(i) 

Довольно немого выше код занимает слишком много времени, чтобы вычислить ...

Answer 1

Что делать, если мы держали только индексы хит-строк и просто пропустил их позже? Я игнорирую, сколько весит enumerate() and del() и процент процентных показов (т. Е. Сколько строк должно быть удалено из вашего набора данных).

THRESHOLD = 50 
data = ["hel", "how", "are", "you"] # replace with your dataset 

tbr = {} # holds the index of the strings to be removed 
idx = 0 
for i in data: 
    for j in xrange(len(data)): 
     if j != idx and levenshtein(i, data[j]) < THRESHOLD: 
      tbr[j] = True 
    idx += 1 

# print tbr 
data2 = [] 
idx = -1 
for d in data: 
    idx += 1 
    if idx in tbr: 
     continue # skip this string 
    data2.append(d) 
# print data2