如何合并列表中的类似项目

一尘不染

如何合并列表中的类似项目

algorithm

我还没有在Google上找到任何相关信息，因此希望在这里找到帮助：)

我有如下的Python列表：

[['hoose', 200], ["Bananphone", 10], ['House', 200], ["Bonerphone", 10], ['UniqueValue', 777] ...]

我有一个函数可以返回2个字符串之间的Levenshtein距离，对于House而言，它会返回2，依此类推。

现在，我要合并levenshtein得分为fe <5的列表元素，而（！）将其得分相加，因此对于结果列表，我需要以下内容：

[['hoose', 400], ["Bananaphone", 20], ['UniqueValue', 777], ...]

要么

[['House', 400], ["Bonerphone", 20], ['UniqueValue', 777], ...]

等等

只要添加它们的值就没有关系。

列表中将只有2个项目非常相似，因此，与任何其他项目类似的任何项目的连锁效应都不会完全被消耗掉。

阅读 380

2020-07-28

共1个答案

一尘不染

与其他评论一样，我不确定这样做是否有意义，但是我认为这是一种可以满足您需求的解决方案。它的效率非常低-O（n 2），其中n是您列表中的单词数-
但我不确定有更好的方法：

data = [['hoose', 200],
        ["Bananphone", 10],
        ['House', 200],
        ["Bonerphone", 10],
        ['UniqueValue', 777]]

already_merged = []

for word, score in data:
    added_to_existing = False
    for merged in already_merged:
        for potentially_similar in merged[0]:
            if levenshtein(word, potentially_similar) < 5:
                merged[0].add(word)
                merged[1] += score
                added_to_existing = True
                break
        if added_to_existing:
            break
    if not added_to_existing:
        already_merged.append([set([word]),score])

print already_merged

输出为：

[[set(['House', 'hoose']), 400], [set(['Bonerphone', 'Bananphone']), 20], [set(['UniqueValue']), 777]]

这种方法的明显问题之一是，您正在考虑的单词可能已经与您已经考虑过的许多不同单词集足够接近，但是此代码会将其汇总到找到的第一个单词中。

2020-07-28