匹配具有最大相似性的 2 个哈希的有效方法

Question

[
  {"id"=>11486, "opt_ids"=> [3545, 3546, 3548, 3550] },
  {"id"=>12624, "opt_ids"=> [3545, 3396, 3548, 3550] }, 
  {"id"=>14588, "opt_ids"=> [3394, 3396, 3397, 3399] }, 
  {"id"=>14589, "opt_ids"=> [3394, 3545, 3398, 3548] }, 
  {"id"=>14590, "opt_ids"=> [3394, 3396, 3397, 3399, 3545, 3547, 3548, 3551, 3653, 3655, 3657, 3660, 3772, 3775, 3777, 3778]},
  .....
  .....
  ...
  ...

]

Is there an efficient way of finding 2 id's which would have the maximum number of similar option_ids?

上面例子的答案是

[[11486, 12624], [14588, 14590]]

我已经尝试过的是-

获取每个散列并将其 opt_ids 与数组中其他剩余散列的 opt_ids 进行比较。
当前哈希的 opt_ids 最匹配的哈希，我将这 2 个 ID 配对。
所以我实际上是在遍历每个散列的次数与数组中散列的数量一样多 - O(n^2)

Answer 1

您可以检查数组中的差异。因此，如果它 returns 空数组或元素数量较少，则表示它们相等或几乎相等。

例如：

a = [1,2,3,4,5]
b = [1,3,2,5,4]
c = [2,4,3,5,9]
d = [2,7,8,8,9]

a-b = []            // similar
a-c = [1]           // almost similar
a-d = [1,3,4,5]     // least similar

Answer 2

假设给定一个非负整数max_diff，如果

，两个整数n1和n2被认为是“相似的”

|n1 - n2| <= max_diff

进一步假设我们得到以下哈希数组：

arr = [
  { "id"=>11486, "opt_ids"=> [3545, 3546, 3548, 3550] },
  { "id"=>12624, "opt_ids"=> [3545, 3396, 3548, 3550] }, 
  { "id"=>14588, "opt_ids"=> [3394, 3396, 3397, 3399] }, 
  { "id"=>14589, "opt_ids"=> [3394, 3545, 3398, 3548] }, 
  { "id"=>14590, "opt_ids"=> [3394, 3396, 3397, 3399] },
  { "id"=>14591, "opt_ids"=> [3545, 3547, 3548, 3551] },
  { "id"=>14592, "opt_ids"=> [3653, 3655, 3657, 3660] },
  { "id"=>14593, "opt_ids"=> [3772, 3775, 3777, 3778] }
]

并指定：

max_diff = 3

我假设我们要根据“相似”的元素对 [h1["opt_ids"][i], h2["opt_ids"][j]] 的数量对这些散列对（以及相关的 "id" 值对）进行排序“根据我上面的定义。这可能与您的想法不一致，但它可能是一个有用的起点。我简要说明 max_diff 始终为零的情况。

考虑 "opt_ids" 的哈希值 arr[0] 和 arr[3]:

a0 = arr[0]["opt_ids"]
  #=> [3545, 3546, 3548, 3550]
a3 = arr[3]["opt_ids"]
  #=> [3394, 3545, 3398, 3548]

如下面的table所示，a0中的3545类似于a3、3545和3548中的两个元素.类似地，a0中的3546、3548和3550类似于[=32]中的2、2和1元素=]，分别意味着散列 arr[0] 和 arr[3] 可以被认为具有 7.

的相似性分数

  a0      a3      #
____________________
3545: 3545, 3548 (2)
3546: 3545, 3548 (2)
3548: 3545, 3548 (2)
3550: 3548       (1)

我们可以使用以下辅助方法来实现此计数。

def count_similar(a1, a2, max_diff)
  a1.product(a2).count { |n1,n2| (n1-n2).abs <= max_diff }
end

例如，

count_similar(a0, a3, max_diff)
  #=> 7

如果我误解了这个问题并且 max_diff 始终为零，并且如果所有数组 arr[i]["opt_ids"] 都包含唯一元素（就像他们在问题示例中所做的那样），那么可以写

def count_similar(a1, a2)
  (a1 & a2).size
end

并删除 max_diff 参数。

我们现在可以按如下方式计算 ID 对的相似性度量：

def similarities(arr, max_diff)
  arr.combination(2)
     .map do |h1,h2|
       [[h1["id"], h2["id"]],
        count_similar(h1["opt_ids"], h2["opt_ids"], max_diff)]
      end.to_h
end

similarities(arr, max_diff)
  #=> {[11486, 12624]=> 9, [11486, 14588]=>0, [11486, 14589]=> 7, [11486, 14590]=>0,
  #    [11486, 14591]=>13, [11486, 14592]=>0, [11486, 14593]=> 0, [12624, 14588]=>4,
  #    [12624, 14589]=> 7, [12624, 14590]=>4, [12624, 14591]=>10, [12624, 14592]=>0,
  #    [12624, 14593]=> 0, [14588, 14589]=>6, [14588, 14590]=>14, [14588, 14591]=>0,
  #    [14588, 14592]=> 0, [14588, 14593]=>0, [14589, 14590]=> 6, [14589, 14591]=>7,
  #    [14589, 14592]=> 0, [14589, 14593]=>0, [14590, 14591]=> 0, [14590, 14592]=>0,
  #    [14590, 14593]=> 0, [14591, 14592]=>0, [14591, 14593]=> 0, [14592, 14593]=>0}

然后我们可能会计算度量，以确定具有最高相似性分数的五对：

similarities(arr, max_diff).max_by(5, &:last)
  #=> [[[14588, 14590], 14], [[11486, 14591], 13], [[12624, 14591], 10],
  #    [[11486, 12624],  9], [[12624, 14589],  7]]

这表明 14588 和 14590 这对 id（来自 arr[2] 和 arr[4]）具有最高的相似度得分，14 .

Answer 3

sqlfiddle I have put the table here with the same data as above. I have created a view from many different tables.

在SQL做，这就是它擅长的

使用自连接获取每对的重叠数。

select
  a.emp_id emp_id1,
  b.emp_id emp_id2,
  count(a.option_id) as overlap
from data a
join data b on
  -- Ensure we count each pair only once
  a.emp_id < b.emp_id and
  a.option_id = b.option_id
group by a.emp_id, b.emp_id

然后将其用作 select 重叠最多的对的 CTE。

with overlaps as (
  select
    a.emp_id emp_id1,
    b.emp_id emp_id2,
    count(a.option_id) as overlap
  from data a
  join data b on
    a.emp_id < b.emp_id and
    a.option_id = b.option_id
  group by a.emp_id, b.emp_id
)
select *
from overlaps
where overlap = (
  select max(overlap)
  from overlaps
)

只要您被编入索引，这应该比将所有数据拉出到 Ruby 中执行得更好。

create index idx_option_emp_ids on data(option_id, emp_id);

即使没有索引，它的性能也应该比将其全部拉出到 Ruby 中要好得多。

匹配具有最大相似性的 2 个哈希的有效方法

Efficient way of matching 2 hashes having maximum similarity

ruby

algorithm

ruby-on-rails

hashmap

ruby-hash