Re: [问题]海量小型数据文件找出所有包含关系

我觉得这个理由有一些奇怪，不知道你们想如何使用trie树处理这个问题。 但是单词最大的分支是26个字母，难道一个数最大的分支不是0~9这10个数吗？（把数字当做字符串考虑的话） 如果因为数比较长而爆了空间，那么单词也会爆啊。 （咦，似乎我想说的是在这种情况下，如果是单词也是不能用trie树的？ 【 在 ReLive 的大作中提到: 】 : 我面试时提出过用trie树，面试官直接否了。它跟单词最大的不同是字母就26个，而数是没有范围的，trie树最差情况下的空间复杂度无法接受。 :

寻找所有偏序，可以构造一些偏序的必要条件帮助判断，比如文件中数的个数，比如文件中所有的数的hash的和（可以多弄几个),复合条件,其他。最后复杂度就是O(N*N*k1*k2),k1是预处理缩减判断对的比例，k2是每个判断所需复杂度。 k1:k1比如用个数就是0.5。上面每个必要条件代表一个全序，多个全序的并形成一个偏序的必要条件。可以看作映射到多维的坐标，偏序当且仅当每一维都小于等于成立。像个数维度上只有20个值，可以认为把一个高维的映射到低维的hash空间(比如20*100)，然后对hash空间每个可行的(A',B')对中的(A,B)判断，缩减比例依赖于可行(A',B')中(A,B)的量，即必要条件的强度，越强,k1越逼近T/N^2, T是实际的(A,B)可行数。 k2:单单对比任意2个排序后的复杂度也并不会太大，用概率算,最坏的k1，A可能平均走上2个数就跳出了,随着k1变小，k2趋向O(M).可以拿lx的优化一下，即有些并不需要直接对比求出，而是通过传递性O(1)求出。 菜。。路过一写，就是思路，具体还要分析啊..

发现一些关系（不考虑重复文件），仅供参考： 1. 如果文件A包含文件B，B包含C，那么A包含C（无需对比直接比较） 2. 如果文件B包含A并且C不包含A，那么C不可能包含A，无需再做检查。 3. 只有大文件可以包含小文件，小文件不能包含打文件。 4. 如果另个文件的数字范围不符合，则不存在包含关系。