This topic created in 1582 days ago, the information mentioned may be changed or developed.
有三个集合，集合里是一些可以度量相似度的东西，比如一个数，可以用绝对值来衡量相似情况，又比如一个向量，大概就是这个意思，数学上应该有比较正式的定义。。。
有没有一种比较好的方案，可以找出三个集合中，有哪些二元组或者三元组，对应是比较相似的。
比如以整数集合为例
A (1,2,3) B (1,100) C (10,4,3)
假设以绝对值来衡量，相似的阈值设为 2
那么就有
(A0 B0 C2) (A1 B0 C2) (A1 C1) (A2 C1)
等等
 |
1
ipwx Jan 9, 2022
最好的算法不清楚。
使用 Ball-tree 配合应该能有复杂度 O(N log N) 的算法， 但是常数较大。具体方法就是对 ABC 三个集合建 Ball-tree ，然后 ABC 分别枚举每一个元素，在另外两个 Ball-tree 找 distance < threshold 的点，最后用 hashtable 对三元组去重。 目测最优算法也是 O(N log N) 的，但是常数比这个小。 |
|
2
ipwx Jan 9, 2022
哦一维情况下可以对三个集合先排序，然后用二分查找代替建树。
|
|
3
ipwx Jan 9, 2022
|
Select Language