c# - 过滤一组包含其他短语的所有短语的算法

Question

给定一组短语，我想过滤包含任何其他短语的所有短语的集合。此处包含意味着如果一个短语包含另一个短语的所有单词，则应将其过滤掉。短语中单词的顺序无关紧要。

我目前的情况是这样的:

1. 按每个短语中的字数对集合进行排序。
2. 对于集合中的每个短语 X:
   1. 对于集合其余部分中的每个短语 Y:
      1. 如果 X 中的所有词都在 Y 中，则 X 包含在 Y 中，丢弃 Y。

考虑到大约 10k 短语的列表，这很慢。还有更好的选择吗？

Answer 1

这是寻找一组集合的最小值的问题。朴素的算法和问题定义如下所示:

set(s for s in sets if not any(other < s for other in sets))

有次二次算法可以做到这一点(例如 this )，但鉴于 N 为 10000，实现效率可能更重要。最佳方法在很大程度上取决于输入数据的分布。鉴于输入集是大部分不同的自然语言短语，redtuna 建议的方法应该很有效。这是该算法的 python 实现。

from collections import defaultdict

def find_minimal_phrases(phrases):
    # Make the phrases hashable
    phrases = map(frozenset, phrases)

    # Create a map to find all phrases containing a word
    phrases_containing = defaultdict(set)
    for phrase in phrases:
        for word in phrase:
            phrases_containing[word].add(phrase)

    minimal_phrases = []
    found_superphrases = set()
    # in sorted by length order to find minimal sets first thanks to the
    # fact that a.superset(b) implies len(a) > len(b)
    for phrase in sorted(phrases, key=len):
        if phrase not in found_superphrases:
            connected_phrases = [phrases_containing[word] for word in phrase]
            connected_phrases.sort(key=len)
            superphrases = reduce(set.intersection, connected_phrases)
            found_superphrases.update(superphrases)
            minimal_phrases.append(phrase)
    return minimal_phrases

这仍然是二次方的，但在我的机器上，它在 350 毫秒内运行了一组 10k 短语，其中包含 50% 的最小值以及来自指数分布的单词。