我有 N 个对象，以及这些对象的 M 组。集合是非空的、不同的，并且可能相交。通常 M 和 N 具有相同的数量级，通常为 M> N。
从历史上看，我的集合是按原样编码的，每个集合只包含其对象的表(数组)，但我想创建一个更优化的编码。通常，大多数集合中都存在一些对象，我想利用这一点。
我的想法是将集合表示为堆栈(即单向链表)，而它们的底部可以在不同的集合之间共享。它也可以定义为树，而每个节点/叶都有一个指向其父节点的指针，但没有指向子节点的指针。 这样的数据结构将允许使用最常见的对象子集作为根，所有适当的集合都可以"继承"。
最有效的编码由以下算法计算。我将它编写为递归伪代码。
BuildAllChains()
{
BuildSubChains(allSets, NULL);
}
BuildSubChains(sets, pParent)
{
if (sets is empty)
return;
trgObj = the most frequent object from sets;
pNode = new Node;
pNode->Object = trgObj;
pNode->pParent = pParent;
newSets = empty;
for (each set in sets that contains the trgObj)
{
remove trgObj from set;
remove set from sets;
if (set is empty)
set->pHead = pNode;
else
newSets.Insert(set);
}
BuildSubChains(sets, pParent);
BuildSubChains(newSets, pNode);
}
注意：伪代码是以递归方式编写的，但技术上不应该使用朴素的递归，因为在每个点上拆分都不平衡，并且在退化的情况下(这很可能，因为源数据不是随机的)，递归深度将是 O(N)。 实际上，我使用循环+递归的组合，而递归总是在较小的部分调用。
因此，这个想法是每次选择最常见的对象，创建一个继承其父子集的"子集"，并且包含它的所有集合，以及到目前为止选择的所有前置对象 - 都应该基于这个子集。
现在，我正在尝试找出一种有效的方法来从集合中选择最常用的对象。最初我的想法是计算所有对象的直方图，并对其进行一次排序。然后，在递归期间，每当我们删除一个对象并仅选择包含/不包含它的集合时 - 推断其余集合的排序直方图。但后来我意识到这不是微不足道的，因为我们删除了许多集合，每个集合都包含许多对象。
当然，我们每次都可以直接选择最频繁的对象，即O(N*M)。但它看起来也很差，在退化的情况下，一个对象几乎存在于所有集合中，或者几乎不存在集合中，我们可能需要重复这个 O(N) 次。OTOH 对于这些特定情况，对排序的直方图进行就地调整可能是首选方法。
到目前为止，我无法想出足够好的解决方案。任何想法将不胜感激。提前谢谢。
更新：
@Ivan：首先非常感谢您的回答和详细分析。 我确实将元素列表存储在直方图中，而不仅仅是计数。实际上，我使用非常复杂的数据结构(与STL无关)和侵入性容器，corss链接指针等。我从一开始就计划好了，因为在我看来，删除元素后的直方图调整是微不足道的。
我认为你的建议的要点是，在每一步中，直方图应该只包含家族中仍然存在的元素，即它们不能包含零。我认为在拆分非常不均匀的情况下，为较小的部分创建新的直方图太昂贵了。但是将其限制为仅现有元素是一个非常好的主意。
因此，我们删除了较小家族的集合，调整了"大"直方图并构建了"小"直方图。现在，我需要澄清一下如何保持大直方图的排序。
我首先想到的一个想法是在每次删除单个元素后立即修复直方图。 即，对于我们删除的每个集合，对于集合中的每个对象，将其从直方图中删除，如果排序被破坏 - 将直方图元素与其邻居交换，直到恢复排序。
如果我们删除少量对象，这看起来很好，我们不需要遍历整个直方图，我们做一个"微气泡"排序。 但是，当删除大量对象时，最好只删除所有对象，然后通过快速排序对数组重新排序。
那么，你对此有更好的想法吗？
更新2：
我考虑了以下内容：直方图应该是一个数据结构，它是一个二叉搜索树(当然是自动平衡的)，而树的每个元素都包含适当的对象ID和它所属的集合列表(到目前为止)。比较标准是此列表的大小。
每个集合都应该包含它现在包含的对象列表，而"对象"具有指向元素直方图的直接指针。此外，每个集合应包含到目前为止匹配的对象数，在开头设置为 0。
从技术上讲，我们需要一个交链列表节点，即同时存在于 2 个链表中的结构：在直方图元素列表中和在集合列表中。此节点还应包含指向直方图项和集合的指针。我称之为"交联"。
选择最常见的对象只是在树中找到最大值。 调整这样的直方图是 O(M log(N))，而 M 是当前受影响的元素数，如果只有少量元素受到影响，则小于 N。
我还将使用您的想法来构建较小的直方图并调整较大的直方图。
听起来对吧？
我用 T 表示集合的总大小。我提出的解决方案在时间O(T log T log N)内工作。
为了清楚起见，我用集合表示初始集合，用家庭表示这些集合的集合。
实际上，让我们存储一个直方图。BuildSubChains函数中，我们维护当前集合中呈现的所有元素的直方图，按频率排序。它可能类似于std::set对(frequency, value)，也许带有交叉引用，因此您可以按值找到元素。现在，获取最常用的元素很简单：它是直方图中的第一个元素。但是，维护它更棘手。
您将集合族拆分为两个子系列，一个包含最常用的元素，另一个不包含。设总大小为 T' 和 T''。选取总大小最小的族，并从直方图中删除其集合中的所有元素，使新的直方图正在运行。现在您有两个族的直方图，它是在时间O(min(T'， T'') log n)中构建的，其中log n来自对std::set的操作。
乍一看，它似乎在二次时间内起作用。但是，它更快。看看任何单个元素。每次我们从直方图中显式删除此元素时，其族的大小至少减半，因此每个元素将直接参与不超过log T的删除。因此，总共会有直方图的O(T log T)操作。
如果我知道集合的总大小，可能会有更好的解决方案。然而，没有一个解决方案可以比O(T)更快，这只是对数慢。
可能还有一个改进：如果你在直方图中不仅存储元素和频率，还存储包含元素的集合(只是每个元素的另一个std::set)，你将能够有效地选择包含最频繁元素的所有集合。