我遇到了一个有趣的问题，我需要用最少的条目数做一个多对多的哈希。我在python中工作，所以是以字典的形式出现的，但这个问题在任何语言中都同样适用。
数据最初是以一个键对一个条目（代表多对多关系中的一个环节）的形式输入的。
所以像。
A-1, B-1, B-2, B-3, C-2, C-3
一个简单的处理数据的方法就是把数据从一个链接到多个。
A: 1
B: 1,2,3
C: 2,3
但是条目的数量是以后处理的主要计算成本 因为每一个条目都需要生成一个文件并通过互联网发送（这是另一个故事） 在一对多的实现中，很可能会有成千上万的条目。
因此，一个更优化的哈希将是。
[A, B]: 1
[B, C]: 2,3
这个表在使用后就会被丢弃 所以可维护性不是问题 唯一的问题是减少条目的时间复杂性（算法减少条目所需的时间不能超过算法减少基线一对多表的条目所节省的时间）。
现在，我很确定至少有人面对过这个问题，这似乎是我在大学的算法课上直接提出来的问题。然而，我很难找到适用的算法，因为我找不到合适的搜索词。我正准备从头开始做一个算法，但我想问问周围的人，看看人们是否不能确定这是一个通常由修改后的[在此插入知名算法]解决的问题，也不会有什么影响。
我个人认为最好先创建一个一对多的哈希，然后检查每个条目中的值的子集，在解哈希中创建一个条目，用于最大限度地识别共享值集。但我不知道如何保证子集的数量比只用一对多的基线实现要少。
让我们回到你的未优化的字母到数字集的字典。
A: 1
B: 1,2,3
C: 2,3
在这个案例中，你可以做一个两分支的重构步骤树。
A:1 B:1,2,3 C:2,3
/ \
factor using set 2,3 factor using set 1
/ \
A:1 B:1 B,C:2,3 A,B:1 B:2,3 C:2,3
/ \
factor using set 1 factor using set 2,3
/ \
A,B:1 B,C:2,3 A,B:1 B,C:2,3
至少在这种情况下，无论你先做哪种分解，结果都是一样的， 但我不确定是否总是如此。
对树进行详尽的探索听起来很昂贵，所以你可能想避免这样做，但如果我们能选出最优路径，或者至少是一条可能的好路径，那计算成本就会相对较低。 与其随机分支，我的家伙直觉是，如果你试图在树的每一点上尽可能做出最大的集因子变化，会更快，更接近最优。 例如，考虑到上面的两分支树，你会更倾向于在你的树上初始的2,3保理，而不是初始的1保理，因为2,3有更大的集大小二。 更戏剧性的重构表明，在你得到一个稳定的结果之前，重构的次数会更少。
这相当于从最大的集向最小的集迭代（你在同长度集上迭代的顺序并不重要），寻找重构机会。
就像气泡排序一样，在每次重构之后，方法将是 "我做了一个改变，它还不稳定，让我们重复"。 重新开始，从次长集向最短集迭代，边走边检查优化机会。
(我不清楚python的情况，但一般来说，集合比较可能会很贵，你可能想为每个集合维护一个值，这个值是集合中哈希值的XOR-of-hash值--如果有几个集合元素发生变化，更新起来很容易，也很便宜，而且一个琐碎的比较可以告诉你大的集合是不相等的，节省比较时间；不过它不会告诉你集合是否相等：多个集合可能有相同的XOR-of-hash值)。