- 主题:如何快速找出相似度最高的数据
需求是这样：
数据库中有数千万条数据，每条数据有4个特征值，外部任意输入4个特征值，如何快速找到匹配度最高的那一条。
如：
数据库中有
a1 b1 c1 d1
a2 b2 c1 d2
输入：a1 b2 c1 d2
得出：与第一条数据只有2个相同(a1 c1)，与第二个有3条相同(b2 c1 d2)。第二条数据为匹配度最高的结果。
--
FROM 113.200.76.*
相似哈希
--
FROM 101.24.90.*
“相似”的定义这么明确， 那就是一个排序了吧？
【 在 BAIYUXIONG 的大作中提到: 】
: 需求是这样：
: 数据库中有数千万条数据，每条数据有4个特征值，外部任意输入4个特征值，如何快速找到匹配度最高的那一条。
: 如：
: ...................
--
FROM 86.131.76.*
特征值量化为向量，转换为求向量点积问题
【 在 BAIYUXIONG 的大作中提到: 】
: 需求是这样：
: 数据库中有数千万条数据，每条数据有4个特征值，外部任意输入4个特征值，如何快速找到匹配度最高的那一条。
: 如：
: ....................
- 来自「最水木 for iPhone13,2」
--
FROM 124.160.220.*
有专门针对这类问题的相似检索数据库，比如 faiss
【 在 StephenLee 的大作中提到: 】
: 特征值量化为向量，转换为求向量点积问题
: 【 在 BAIYUXIONG 的大作中提到: 】
: : 需求是这样：
: ....................
- 来自「最水木 for iPhone13,2」
--
FROM 124.160.220.*
假设1000万条数据，每条数据4个特征值，每个特征值1 byte,共40 MB数据，可以全加载到内存里。
方法1:
按照4，3，2，1个特征值匹配依此排好序，依次从排好序的列表里二分法查询。 比如假设4个特征值都匹配， 排序结果：
AA AA AA AA : id list
AA AA AA AB : id list
AA AA AA AC : id list
…
假设只有三个特征值匹配，
AA AA AA None : id list
AA AA AB None : id list
AA AA AC None : id list
…
AA AA None AA : id list
AA AA None AB : id list
AA AA None AC : id list
…
类似的可以建立2个、1个匹配的排序列表。
方法2:
同上，但用哈希表，不用排序
方法3:
每个特征值单独排序，用二分查找法找出每个目标特征值最靠近的点。 四个点就连成了一个最佳匹配线，但线上可能没有完美匹配的数据。 在每个匹配点上下动一格，寻找次优解，不行就再动一格。
方法4:
机器学习， 训练一个神经网络模型预测。
方法 5:
算出每行数据与原点（0, 0, 0, 0) 的距离差， 目标与到原点的距离 约等于 最优解到原点的距离。 以此为依据缩小搜索范围。
方法6:
分布式计算，用一万台机器，每台机器比对一千条数据。
不论选择何种算法，都可以加一层cache， 遇到最近查过的数据，直接从cache里返回结果，不用读数据库。
【 在 BAIYUXIONG 的大作中提到: 】
: 需求是这样：
: 数据库中有数千万条数据，每条数据有4个特征值，外部任意输入4个特征值，如何快速找到匹配度最高的那一条。
: 如：
: ....................
- 来自「最水木 for iPhone 11 Pro Max」
※ 修改:·galaxy123 于 Dec 4 10:36:00 2021 修改本文·[FROM: 173.63.213.*]
※ 来源:·最水木 客户端·[FROM: 173.63.213.*]
修改:galaxy123 FROM 173.63.213.*
FROM 173.63.213.*
匹配4个、3个、2个、1个，依次检索一遍
匹配中了就终止
总共也没检索几次
【 在 BAIYUXIONG 的大作中提到: 】
: 需求是这样：
: 数据库中有数千万条数据，每条数据有4个特征值，外部任意输入4个特征值，如何快速找到匹配度最高的那一条。
: 如：
: ...................
--
FROM 123.119.122.*
不带距离权重的直接用 Levenshtein 距离
如果python的话直接用fuzzywuzzy库
--
FROM 117.89.132.*
这不可行。排列组合，一共有十几种情况了。万一将来特征值变成5个，6个，那查询次数更多了。
【 在 zjzf 的大作中提到: 】
: 匹配4个、3个、2个、1个，依次检索一遍
: 匹配中了就终止
: 总共也没检索几次
--
FROM 113.200.76.*
这个方案有误差的。
比如数据库有这样的值
aaa bb cc dd
abb ba cc dd
如果输入一个
bbb bb cc dd
按需求，第1个是正确值，但是按编辑距离的话，第二个才是合理值。
【 在 pyl720 的大作中提到: 】
: 不带距离权重的直接用 Levenshtein 距离
: 如果python的话直接用fuzzywuzzy库
--
FROM 222.91.149.*