在列表中计算levenshtein距离Python

我有一个字符串列表，我想根据levenstein距离过滤出过于类似的字符串。所以如果lev(list[0], list[10]) < 50;然后del list[10]。有什么方法可以计算列表中每对字符串之间的距离，更有效率？谢谢！！在列表中计算levenshtein距离Python

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

以上，而哑代码的时间太长计算...

来源

2015-04-04 Blue482

需要更多信息才能回答。 Levenshtein算法据说很慢。另外，data和data1没有定义。你看过，http://www.levenshtein.net？ Exobyte？你用过python的分析器吗？ – xxyzzy 2015-04-04 14:51:45

Levenshtein是对称的。您可能需要相应地构建嵌套的for-loops。请参阅http://stackoverflow.com/questions/9722022/levenshtein-distance-symmetric – xxyzzy 2015-04-04 14:56:21

谢谢。我正在使用[link]（http://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python）的第5个Levenshtein实现。数据是一个包含6000个句子的列表，我只想保留一个非常相似的句子对。 – Blue482 2015-04-04 15:23:27

如果我们只保留命中串的指标，只是跳过他们以后呢？我忽略了多少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-04 17:34:21 Pynchia

谢谢！但是'拥有要删除的字符串的索引'的步骤仍然像是永远... – Blue482 2015-04-04 19:48:07

写在C（带指针）; D – Pynchia 2015-04-04 19:57:16

在列表中计算levenshtein距离Python

回答

相关问题