在 python 中查找出现在超过 k 个集合中的元素

Question

我正在实施一个基本的拼写校正系统，并且为我所在领域的语言建立了一个倒排索引，其中每个字符双字母组都映射到包含该双字母组的单词列表。

现在我想找到与给定单词 w 共享超过 3 个字符的双字母组的所有单词。所以主要问题是：给定一组列表，如何有效地找到出现在其中 3 个或更多列表中的元素？

例如，给定集合：

('a', 'b', 'c', 'd') , ('a', 'e', 'f', 'g'), ('e', 'f', 'g', 'h'), ('b', 'c', 'z', 'y'), ('e', 'k', 'a', 'j')

我喜欢得到输出：

('a', 'e')

因为a和e各出场超过3集

我会很感激你的想法。

Answer 1

您可以尝试使用 collections.Counter:

from collections import Counter

data = [
    ('a', 'b', 'c', 'd'),
    ('a', 'e', 'f', 'g'),
    ('e', 'f', 'g', 'h'),
    ('b', 'c', 'z', 'y'),
    ('e', 'k', 'a', 'j'),
]
c = Counter()
for e in data:
    c.update(e)

# print(c)
# for k, v in c.items():
#     if v >= 3:
#         print(k, v)

你可以使用这个（或类似的东西）得到输出：

>>> [k for k, v in c.items() if v >= 3]
['a', 'e']

Answer 2

除了@Ralf。可以使用dicts构造直方图

someCollection = [('a', 'b', 'c', 'd') , ('a', 'e', 'f', 'g'), ('e', 'f', 'g', 'h'), ('b', 'c', 'z', 'y'), ('e', 'k', 'a', 'j')]
hist = {}
for collection in someCollection:
    for member in collection:
        hist[member] = hist.get(member, 0) + 1

现在历史是：

{'a': 3,
 'b': 2,
 'c': 2,
 'd': 1,
 'e': 3,
 'f': 2,
 'g': 2,
 'h': 1,
 'z': 1,
 'y': 1,
 'k': 1,
 'j': 1}

可以用sorted(hist.items(), key = lambda x[1]) # sort along values排序

在 python 中查找出现在超过 k 个集合中的元素

Find elements that appear in more than k sets in python

python

intersection

set