1

我发现A[i..j]它与 B 最相似。这calcSimilarity是返回两个数组相似度的函数。相似度计算为 Not than brute force search，我想知道什么样的数据结构和算法在范围搜索中是有效的。
在此处输入图像描述

样品输入/输出

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);
}
4

1 回答 1

0

它需要 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 距离是一种距离度量，可以将其放置在度量树中。

于 2017-10-04T07:10:49.757 回答