在数组中查找最相似的范围
Finding most similar Range in an Array
我发现 A[i..j]
与 B 最相似。
这里 calcSimilarity
是两个数组 returns 相似度的函数。
相似度计算为
不是暴力搜索,我想知道什么样的数据结构和算法在范围搜索中是有效的
样本input/output
input: A: [(10,1), (20,1), (-200,2), (33,1), (42,1), (58,1)] B:[(20,1), (30,1), (1000,2)]
output: most similar Range is [1, 3]
match [20, 33] => [20, 30]
这是暴力搜索代码。
struct object{
int type, value;
}A[10000],B[100];
int N, M;
int calcSimilarity(object X[], n, object Y[], m){
if(n > m) return calcSimilarity(Y, m, X, n);
for(all possible match){//match is (i, link[i])
int minDif = 0x7ffff;
int count = 0;
for( i = 0; i< n; i++){
int j = link[i];
int similar = similar(X[i], Y[j]);
minDif = min(similar, minDif);
}
}
if(count == 0) return 0x7fffff;
return minDif/pow(count,3);
}
find_most_similar_range(){
int minSimilar = 0x7fffff, minI, minJ;
for( i = 0; i < N; i ++){
for(j = i+1; j < N; j ++){
int similarity = calcSimilarity(A + i, j-i, B, M);
if (similarity < minSimilar)
{
minSimilar = similarity;
minI= i;
minJ = j;
}
}
}
printf("most similar Range is [%d, %d]", minI, minJ);
}
it will take O((N^M) * (N^2)).
看起来相似度的Big-O是N^2。与每个元素的两两比较。
所以看起来更像
成对比较是M*(M-1)。每个列表都必须针对其他列表或大约 M^2 进行测试。
这是一个已经解决的聚类问题,并且有数据结构(例如Metric Tree),它允许将相似对象之间的距离存储在树中。
当寻找 N 个最近的邻居时,这棵树的搜索限制了所需的成对比较的数量并导致 O( ln(M) ) 形式
这棵树的缺点是相似性度量需要度量。其中A和B的距离,B和C的距离可以推断出A和C的距离范围
如果您的相似性度量不是公制的,那么这将无法完成。
Jaccard distance 是距离的度量,可以将其放置在度量树中。
我发现 A[i..j]
与 B 最相似。
这里 calcSimilarity
是两个数组 returns 相似度的函数。
相似度计算为
不是暴力搜索,我想知道什么样的数据结构和算法在范围搜索中是有效的
样本input/output
input: A: [(10,1), (20,1), (-200,2), (33,1), (42,1), (58,1)] B:[(20,1), (30,1), (1000,2)]
output: most similar Range is [1, 3]
match [20, 33] => [20, 30]
这是暴力搜索代码。
struct object{
int type, value;
}A[10000],B[100];
int N, M;
int calcSimilarity(object X[], n, object Y[], m){
if(n > m) return calcSimilarity(Y, m, X, n);
for(all possible match){//match is (i, link[i])
int minDif = 0x7ffff;
int count = 0;
for( i = 0; i< n; i++){
int j = link[i];
int similar = similar(X[i], Y[j]);
minDif = min(similar, minDif);
}
}
if(count == 0) return 0x7fffff;
return minDif/pow(count,3);
}
find_most_similar_range(){
int minSimilar = 0x7fffff, minI, minJ;
for( i = 0; i < N; i ++){
for(j = i+1; j < N; j ++){
int similarity = calcSimilarity(A + i, j-i, B, M);
if (similarity < minSimilar)
{
minSimilar = similarity;
minI= i;
minJ = j;
}
}
}
printf("most similar Range is [%d, %d]", minI, minJ);
}
it will take O((N^M) * (N^2)).
看起来相似度的Big-O是N^2。与每个元素的两两比较。
所以看起来更像
成对比较是M*(M-1)。每个列表都必须针对其他列表或大约 M^2 进行测试。
这是一个已经解决的聚类问题,并且有数据结构(例如Metric Tree),它允许将相似对象之间的距离存储在树中。
当寻找 N 个最近的邻居时,这棵树的搜索限制了所需的成对比较的数量并导致 O( ln(M) ) 形式
这棵树的缺点是相似性度量需要度量。其中A和B的距离,B和C的距离可以推断出A和C的距离范围
如果您的相似性度量不是公制的,那么这将无法完成。
Jaccard distance 是距离的度量,可以将其放置在度量树中。