algorithm - 对相关特征的数据结构的建议

Question

我们有一组 Documents ，每个都有一组 Features。给定特征 A，我们需要知道在同一文档中具有特征 B 的概率是多少。

我想建立一个概率矩阵 st: M(i,j) = Probability of having feature B in a document ，假设特征 A 存在。

但是，我们还有一个额外的要求：给定特征 A 在文档中，有哪些特征在同一文档中的概率 > P。

同时，我所能想到的只是概率矩阵的稀疏矩阵，在计算之后，对于每个特征在所有列上运行，按 P 对其进行排序，并将其保存在某个链接列表中。（所以现在，对于每个特征，我们都有一个对应特征的列表

这个空间复杂度相当大（最坏的情况：N^2，而且N很大！），每次搜索的时间复杂度是O(N)。

有更好的主意吗？

Answer 1

如果特征的数量与文档的数量相当，或者更多，考虑保存一个倒排索引：对于每个特征保存（例如一个排序的列表）它所在的文档。然后，您可以通过对特征 A 和 B 的排序列表运行合并来计算 B 给定 A 的概率。

对于“给定 A 的预期共同特征”问题，我想不出比预先计算每个 A 的答案并希望得到的特征列表不会太长更好的办法。