Найти элементы, которые появляются в более чем k множествах в Python

Question

Я внедряю базовую систему исправления орфографии и построил инвертированный индекс для языка моего домена, где каждый биграмм символов отображается в список слов, содержащих этот биграмм.

Теперь я хочу найти все слова, которые имеют более 3 символов биграммы с данным словом w.Итак, основная проблема: при наличии набора списков, как можно эффективно найти элементы, которые встречаются в 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

Дополнительно к @Ralf.Вы можете использовать дикты для построения гистограммы

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

Answer 2

Вы можете попробовать использовать 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']