0

我有一个包含数千个名称的长列表，这些名称都是唯一的字符串，但我想过滤它们以生成一个较短的列表，以便如果有相似的名称，则只保留一个。例如，原始列表可能包含：

米老鼠

米老鼠

米奇米老鼠

新列表将只包含其中一个 - 此时此刻哪个并不重要。可以使用下面的代码获得相似度分数（其中a和b是要比较的文本），所以如果我选择了一个合适的比率，我就有办法做出包含/排除决定。

difflib.SequenceMatcher(None, a, b).ratio()

我正在努力解决的是如何从第一个列表中填充第二个列表。我确信这是一件微不足道的事情，但它让我的新手大脑感到困惑。

我原以为这样的事情会奏效，但最终在第二个列表中没有填充任何内容。

for p in ppl1:
    for pp in ppl2:
       if difflib.SequenceMater(None, p, pp).ratio() <=0.9:
           ppl2.append(p)

事实上，即使它确实填充了列表，它仍然是错误的。我想它需要将第一个列表中的名称与第二个列表中的所有名称进行比较，跟踪得分最高的比率，然后仅在最高比率低于截止标准时才添加它。

任何指导都感激不尽！

4

2 回答 2

1

我将冒着永远不会被接受的风险，因为这对你来说可能太先进了，但这是最佳解决方案。

您正在尝试做的是凝聚聚类的一种变体。可以使用联合查找算法来有效地解决这个问题。从所有不同的字符串对a和b，可以使用生成

def pairs(l):
    for i, a in enumerate(l):
        for j in range(i + 1, len(l)):
            yield (a, l[j])

您过滤具有相似率的对<= .9：

similar = ((a, b) for a, b in pairs
                  if difflib.SequenceMatcher(None, p, pp).ratio() <= .9)

然后将不相交的森林中的那些联合起来。之后，您循环遍历集合以获取它们的代表。

于 2013-05-20T11:15:24.657 回答
0

首先，您不应该在迭代列表时修改它。

一种策略是遍历所有名称对，如果某一对彼此太相似，则只保留一个，然后迭代直到没有两对太相似。当然，结果现在将取决于列表的初始顺序，但如果您的数据足够集群并且您的相似度得分指标足够好，它应该会产生您正在寻找的内容。

于 2013-05-20T10:57:37.837 回答