Алгоритм нахождения сумок элементов в последовательности

Скажем, у меня есть последовательность интересующих элементов A, B, C... вкраплениями небезразличных символов x . Я хочу идентифицировать пакеты элементов из предопределенного набора интересных комбинаций, которые происходят в пределах предопределенного расстояния. Между интервалами символов могут быть совпадения. Например, в строке C xx AA xx C алгоритм может дважды обнаружить шаблон AAC если максимальное расстояние равно 5.

Например, говорит, что мой набор интересных комбинаций:

A A C
A B C

что у меня есть последовательность:

B A x x C x x x A A x x x C

и что максимальный промежуток составляет 5.

Мой алгоритм должен выводить:

B A x x C -> A B C

и не сможет определить шаблон AAC поскольку промежуток между интересующими элементами больше 5.

Моя интуиция говорит, что это какое-то динамическое программирование, но, возможно, это всего лишь пример хорошо известного алгоритма, который я не в состоянии заметить.

Любой намек на то, что будет подход / решение?

Всего 2 ответа


  1. Возьмите все свои интересные комбинации и постройте дерево так, чтобы интересные комбинации приводили к листьям, а неинтересные - нет. Сортируйте сначала так, чтобы ребра, соответствующие более ранним символам, были ближе к корню.

  2. Прочитайте первые пять элементов и увеличьте счетчики частоты, соответствующие количеству раз, которое видели каждый.

  3. Проверьте подмножество до пяти значений, пройдясь по дереву в соответствии со счетчиками частоты. Если вы достигнете листа, выбросить текущий матч.

  4. Чтобы сдвинуть окно, уменьшите счетчик, связанный с текущим самым левым интересным символом, и увеличьте счетчики для интересных символов, засосанных после скольжения вправо.

Пример № 1:

AAC, ABC => (-)        [B A x x C] x x x A A x x x C
             |         f[A] = 1, f[B] = 1, f[C] = 1
             A         A->B->C, emit ABC
             |
            (-)        B [A x x C x] x x A A x x x C
            /         f[B]--; A->x; continue
           A   B       
           |   |       B A x x [C x x x A] A x x x C
          (-) (-)      f[A]--; f[A]++; A->x; continue
           |   | 
           C   C       B A x x C x x x [A A x x x] C
           |   |       f[C]--; f[A]++; A->A->x; continue
          (+) (+)

                       B A x x C x x x A [A x x x C]
                       f[A]--; f[C]++; A->x; done

Пример № 2:

AAC => (-)             [C x x A A] x x C
        |              f[A]=2, f[B]=0, f[C]=1
        A              A->A->C, emit AAC; continue
        |
       (-)             C x x [A A x x C]
        |              f[C]--; f[C]++; A->A->C; emit AAC; done
        A
        |
       (-)
        |
        C
        |
       (+)

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


Давайте назначим несколько имен для описания проблемы:

m = длина последовательности массива (14 в вашем примере)
n = общее количество уникальных элементов в последовательности массива (3 в примере)
k = длина каждой области поиска (5 в примере)
g = количество групп, которые вы ищете (2 в примере)

Одним из вариантов будет суммирование ваших данных в каждой поисковой области размера k . В вашем примере вот так:

{B A x x C}
{A x x C x}
...

Мы делаем векторы размером n для каждого из этих разделов, первый элемент представляет появление элемента первого типа, скажем, A

B A x x C --> [1,1,1] (one appearance of each)
A x x C x --> [1,0,1]

и так далее.

Мы можем сделать то же самое для наших групп, которые мы ищем:

{A A C} --> [2,0,1]  
{A B C} --> [1,1,1]

Теперь проблема становится очевидной. Скажем, мы рассматриваем сводку области поиска [3,2,5] и сводку группы, которую мы ищем, [0,1,2], мы можем вычислить количество комбинаций, признав, что у нас было 2 варианта для второго элемента и (5x4) / (1x2) для третьего, то есть всего 20 вариантов.

Таким образом, для сводки по разделам S, [s 1 , s 2 , .., s n ] и отдельной интересующей группы G, [g 1 , g 2 , ... g n ] мы можем вычислить общую сумму способов извлечь G из S (код в стиле c ++, за исключением того, что "!" означает факториал):

int total_options = 1; // total ways to select G from S
for (int i = 0; i < n; ++i)
{
    if(g[i] == 0)
        continue; // this is an element that doesn't appear in G, so it shouldn't effect our count

    if(s[i] < g[i])
        return 0; // not enough elements in S for G

    for (int d = 1, f = s[i]; f > max(g[i], s[i] - g[i]); --f, ++d)
        total_options = total_options / d * f; // f, d are effectively factorials

    // the previous loop is a more efficient version of:
    // total_options *= (s[i]!) /(g[i]! * (s[i] - g[i])!);
}

return  total_options;

Вы должны сделать это для каждого раздела и каждой группы, которую вы ищете.

Временная сложность: O ( g*m*(k + n) ) (мы должны включить k здесь из-за факториального вычисления наихудшего случая)

Сложность пространства: O ( m + g*n ) (каждый раздел мы можем вычислить по ходу, поэтому нет необходимости хранить несколько разделов одновременно)

Затем мы можем улучшить это, осознав, что каждый последующий «раздел» отличается только с учетом уходящего элемента «tail» и входящего элемента «head», поэтому мы должны просто рассчитать, как эти два изменяют «счетчик опций» при выполнении итерации. к следующему разделу. Мы сделали бы это, поддерживая предыдущее вычисление «счетчика опций», и, NF (Number Fails), количество элементов в регионе, которое было слишком низким для группы поиска. Хитрость заключается в том, чтобы поддерживать положительный «счетчик опций», который добавляется к общему итогу, только если NF равен 0. Это даст вам результаты с постоянным временем для каждого G когда вы будете перебирать основной массив размера m .

Временная сложность: O ( g*m + g*n )
Пространство сложность: O ( g*n + m )

Этот алгоритм имеет худшую производительность, когда каждый элемент в основном массиве уникален, и каждый из этих элементов появляется по крайней мере один раз в некоторых поисках (в противном случае мы можем рассматривать любые элементы, которые не появляются ни в одном из поисков, для всех быть таким же, как «х» в вашем примере). Таким образом, сложности наихудшего случая могут быть упрощены до:

Временная сложность: O ( g*m )
Пространственная сложность: O ( g*m )

Я не понимаю, как можно было бы получить лучшую временную сложность, но мне было бы интересно узнать, может ли какой-нибудь умный человек придумать метод с меньшей пространственной сложностью.

Если вы не знаете, о чем я говорю, когда речь идет об итерации в постоянном времени, рассматривая только голову и хвост, дайте мне знать, и я объясню на примере.


Есть идеи?

10000