Поиск наиболее похожего диапазона в массиве

Я нахожу A[i..j], который больше всего похож на B. Здесь calcSimilarity — это функция, которая возвращает сходство двух массивов. Сходство рассчитывается как
введите здесь описание изображения
Не чем поиск грубой силы, я хочу знать, какая структура данных и алгоритм< /strong> эффективен при поиске по диапазону.

SAMPLE вход/выход

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

c++ arrays algorithm data-structures pattern-finding
person artgb    schedule 04.10.2017    source источник

Ответы (1)


arrow_upward
0
arrow_downward

это займет 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.

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

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

person mksteve    schedule 04.10.2017
comment
Спасибо за ваш ответ, и это имеет смысл. Но мне нужно установить для всего диапазона A[i..j] метрическое дерево? Я думаю, что это будет неэффективно (память и время). Общее количество A[i..j] займет 10^8. Я нахожу конкретный алгоритм для массива. как people.cs.uct.ac.za/~ksmith/articles / - person artgb; 04.10.2017