Я нахожу A[i..j]
это наиболее похоже на B.
Вот calcSimilarity
это функция, которая возвращает сходство двух массивов.
Сходство рассчитывается как
Не чем перебор, Я хочу знать, что это за структура данных и алгоритм эффективен в поиске по дальности.
ОБРАЗЕЦ ввода / вывода
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);
}
это займет O ((N ^ M) * (N ^ 2)).
Похоже, что Big-O подобия находки — N ^ 2. При попарном сравнении каждого элемента.
Так это выглядит как
Попарное сравнение — M * (M-1). Каждый список должен быть проверен на соответствие друг другу или на предмет M ^ 2.
Это проблема, которая была решена для кластеризации, и существуют структуры данных (например, Метрическое дерево), которые позволяют хранить расстояния между похожими объектами в дереве.
При поиске N ближайших соседей поиск этого дерева ограничивает количество необходимых попарных сравнений и приводит к форме O (ln (M))
Недостатком этого конкретного дерева является то, что мера подобия должна быть метрической. Где расстояние между A и B и расстояние между B и C позволяют сделать выводы о диапазоне расстояний A и C.
Если ваша мера сходства не является метрической, то это невозможно сделать.
Жаккардовое расстояние метрика расстояния, которая позволяет поместить его в дерево метрик.
Других решений пока нет …