Найти наиболее похожий диапазон в массиве

Я нахожу 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);
}

0

Решение

это займет O ((N ^ M) * (N ^ 2)).

Похоже, что Big-O подобия находки — N ^ 2. При попарном сравнении каждого элемента.

Так это выглядит как

Попарное сравнение — M * (M-1). Каждый список должен быть проверен на соответствие друг другу или на предмет M ^ 2.

Это проблема, которая была решена для кластеризации, и существуют структуры данных (например, Метрическое дерево), которые позволяют хранить расстояния между похожими объектами в дереве.

При поиске N ближайших соседей поиск этого дерева ограничивает количество необходимых попарных сравнений и приводит к форме O (ln (M))

Недостатком этого конкретного дерева является то, что мера подобия должна быть метрической. Где расстояние между A и B и расстояние между B и C позволяют сделать выводы о диапазоне расстояний A и C.

Если ваша мера сходства не является метрической, то это невозможно сделать.

Жаккардовое расстояние метрика расстояния, которая позволяет поместить его в дерево метрик.

0

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]