2

考虑一下：

A组：1 2 3 4
B组：3 4 5 6
C组：4 5 6 7
D组：1

我想将 D 与其余的进行比较，并得到一组最相关的数字。结果应该是这样的顺序：4（因为 D 与 A 有一个公共数字，4 在 A 以及 B 和 C 中），3（因为 D 与 A 有一个公共数字，3 在 A 和 B 中）， 2（因为 D 与 A 有一个公共数字，并且 2 也在 A 中），然后是 5、6、7。

在 PHP/MySQL 中是否有一些算法可以有效地做到这一点？我不想重新发明轮子，而且数据库最终会有大量的集合..

4

2 回答 2

2

一个例子并没有做出完整的规范。例如，如果集合的集合也包括在内，你的答案会有什么不同

set E: 1 2 3
set F: 1   3

这将使 3 成为与 有非空交集的集合中最常出现的值D？所以这是我的假设：

给定一个目标集（D在您的原始示例中）：

  1. “重叠集合”（与目标集合具有非空交集的集合）中的值比那些重叠集合中没有的值更相关。
  2. 在陈述 1 的约束下，相关性由出现的频率决定。

在您的原始示例中，A与 重叠D，因此宇宙 {1, 2, 3, 4, 5, 6, 7} 被划分为重叠 {1, 2, 3, 4} 和不重叠 {5, 6, 7} . 值频率为 {1:2, 2:1, 3:2, 4:3, 5:2, 6:2, 7:1}。结合这些事实给出重叠频率 {1:2, 2:1, 3:2, 4:3} 和非重叠频率 {5:2, 6:2, 7:1}，产生顺序 4, 3, 1、2 后跟 5、6、7。（我注意到您没有为 1 分配相关性。如果故意，这可能是从最终排序中删除目标集值的最后一步。）

在我调整后的示例中，频率变为 {1:4, 2:3, 3:4, 4:3, 5:2, 6:2, 7:1}。这给出了重叠频率 {1:4, 2:3, 3:4, 4:3} 和非重叠频率 {5:2, 6:2, 7:1}，产生顺序 1, 3, 2, 4 之后是 5、6、7。

该算法的伪代码是：

  1. 初始化overlapping和universe为空集并frequency为空散列。

  2. 对于集合集合s中的每个集合（t目标集合除外）：

    2.1。设置universe为和的s并集universe

    2.2. 如果sintersected witht至少有一个元素：

    2.2.1. Set `overlapping` to the union of `overlapping` and `s`

    2.3. e对于中的每个元素s：

    2.3.1. If 'e' is a key in `frequency`

    2.3.1.1. Then increase the value (count) for `e` in `frequency` by 1
    2.3.1.2. Else initialize the value (count) for `e` in `frequency` to 1

  3. 设置nonOverlapping为universe和的差overlapping

  4. 按结果的第一部分中的universe值对元素进行排序。frequency

  5. 将 的元素附加到结果中nonOverlapping，也按它们在 中的值排序frequency。

（如果您确实打算t消除 的元素，我会在 4 中将其作为后处理步骤。）

于 2009-12-09T13:19:01.527 回答
1

在 SQL 中，我假设您有一个名为集合的表，有 2 列，e 代表元素，s 代表集合名称。

select e,count(*) as c from sets where s in
(select s from sets where e in (select e from sets where s='D') group by s)
group by e order by c desc

解释：

(select e from sets where s='D')

选择组 D 的元素。

(select s from sets where e in (select e from sets where s='D') group by s)

选择与先前选择的组有共同成员的所有组。

然后从这些集合中选择所有元素，并按出现次数对它们进行排序（如joel建议的那样）

于 2009-12-09T13:49:38.083 回答