在Python中按Levenshtein对字符串列表分组

Question

我写了一个脚本，用来计算两个字符串之间的莱文斯坦距离。现在我想根据这个距离把一组字符串分成不同的组（如果两个字符串的距离小于某个阈值，它们就会被放在同一组里）：

目前，我已经做了一些工作，但似乎没有效果。下面是一个伪代码：

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

这是一些整理过的代码：

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])

Answer 2

你在遍历一个列表的时候，直接从里面删除东西。这会改变列表的索引位置，导致一些意想不到的情况发生。为了避免这个问题，应该把你需要的值复制到一个新的列表里，而不是直接修改你正在遍历的那个列表。