请教一个算法/方案？

2022-01-09 13:20:22 +08:00
 zxCoder

有三个集合，集合里是一些可以度量相似度的东西，比如一个数，可以用绝对值来衡量相似情况，又比如一个向量，大概就是这个意思，数学上应该有比较正式的定义。。。

有没有一种比较好的方案，可以找出三个集合中，有哪些二元组或者三元组，对应是比较相似的。

比如以整数集合为例

A (1,2,3) B (1,100) C (10,4,3)

假设以绝对值来衡量，相似的阈值设为 2

那么就有

(A0 B0 C2) (A1 B0 C2) (A1 C1) (A2 C1)

等等

820 次点击
所在节点    问与答
3 条回复
ipwx
2022-01-09 14:16:40 +08:00
最好的算法不清楚。

使用 Ball-tree 配合应该能有复杂度 O(N log N) 的算法， 但是常数较大。具体方法就是对 ABC 三个集合建 Ball-tree ，然后 ABC 分别枚举每一个元素，在另外两个 Ball-tree 找 distance < threshold 的点，最后用 hashtable 对三元组去重。

目测最优算法也是 O(N log N) 的，但是常数比这个小。
ipwx
2022-01-09 14:17:41 +08:00
哦一维情况下可以对三个集合先排序，然后用二分查找代替建树。
ipwx
2022-01-09 14:18:17 +08:00
Ball-tree implementation： https://scikit-learn.org/stable/modules/generated/sklearn.neighbors.BallTree.html#sklearn.neighbors.BallTree.query_radius

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://tanronggui.xyz/t/827111

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX