1

我有一个字符串列表，我想根据列文斯坦距离过滤掉过于相似的字符串。所以如果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)

上面相当愚蠢的代码计算时间太长了......

4

1 回答 1

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
于 2015-04-04T17:34:21.987 回答