Найти Top N наиболее часто встречающихся последовательностей чисел в списке списков

Question

Допустим, у меня есть следующий список списков:

x = [[1, 2, 3, 4, 5, 6, 7],  # sequence 1
     [6, 5, 10, 11],  # sequence 2
     [9, 8, 2, 3, 4, 5],  # sequence 3
     [12, 12, 6, 5],  # sequence 4
     [5, 8, 3, 4, 2],  # sequence 5
     [1, 5],  # sequence 6
     [2, 8, 8, 3, 5, 9, 1, 4, 12, 5, 6],  # sequence 7
     [7, 1, 7, 3, 4, 1, 2],  # sequence 8
     [9, 4, 12, 12, 6, 5, 1],  # sequence 9
]

По существу, для любого списка, который содержит целевое число 5 (то есть target=5) в любом месте списка, каковы top N=2 наиболее часто наблюдаемые подпоследовательности с длиной M=4?

Итак, условия:

1. , если target не существует в списке, то мы полностью игнорируем этот список
2. , если длина списка меньше чем M, тогда мы полностью игнорируем список
3. , если список точно имеет длину M, но target не находится в позиции Mth, тогда мы игнорируем его (но мы считаем его, если target находится в позиции Mth)
4. , если длина списка L больше M и target в позиции i=M (or i = M + 1 position, or i = M + 2 position, ..., i = L position) then we count the subsequence of length M where target` находится в последней позиции в подпоследовательности

Итак, используя наш пример списка списков, мы посчитали бы следующие подпоследовательности:

subseqs = [[2, 3, 4, 5],  # taken from sequence 1
           [2, 3, 4, 5],  # taken from sequence 3
           [12, 12, 6, 5],  # taken from sequence 4
           [8, 8, 3, 5],  # taken from sequence 7
           [1, 4, 12, 5],  # taken from sequence 7
           [12, 12, 6, 5],  # taken from sequence 9
]

Конечно, нам нужны верхние подпоследовательности N=2 по частоте. Итак, [2, 3, 4, 5] и [12, 12, 6, 5] являются двумя наиболее частыми последовательностями по количеству. Если N=3, то будут возвращены все подпоследовательности (subseqs), поскольку для третьего - ie.

Это очень упрощенно, но на самом деле мой фактический список списков

1. состоит из нескольких миллиардов списков натуральных чисел (от 1 до 10000)
2. каждый список может быть не более 1 элемента или не более 500 элементов
3. N и M может составлять 1 или 100

Мои вопросы:

1. Существует ли эффективная структура данных, которая позволяла бы выполнять быстрые запросы, предполагая, что N и M всегда будут меньше 100?
2. Есть ли эффективные алгоритмы или соответствующая область исследований для проведения такого анализа для различных комбинаций N и M?

Answer 1

Поскольку существует не только N, M и цель, я предполагаю, что есть куски списков со списками. Вот подход в O (N + M) моде временной сложности (где N - количество списков в чанке, а M - общее количество элементов):

def get_seq(x, M, target):
    index_for_length_m = M - 1
    for v in [l for l in x if len(l) >= M]:
        for i in [i for i, v in enumerate(v[index_for_length_m:], start=index_for_length_m) if v == target]:
            # convert to str to be hashable
            yield str(v[i - index_for_length_m : i + 1])

def process_chunk(x, M, N, target):
    return Counter(get_seq(x, M, target)).most_common(N)

на вашем примере:

process_chunk(x, M, 2, target)

вывод:

[('[2, 3, 4, 5]', 2), ('[12, 12, 6, 5]', 2)]

исполнение:

%timeit process_chunk(x, M, 2, target)
# 25 µs ± 713 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Answer 2

Чтобы ответить на ваш первый вопрос: вы можете поместить все списки в массив, зафиксировав длину путем расширения нуля, чтобы массив стал чем-то, с чем вы можете работать. Из ответа здесь

x = [[1, 2, 3, 4, 5, 6, 7],  # sequence 1
     [6, 5, 10, 11],  # sequence 2
     [9, 8, 2, 3, 4, 5],  # sequence 3
     [12, 12, 6, 5],  # sequence 4
     [5, 8, 3, 4, 2],  # sequence 5
     [1, 5],  # sequence 6
     [2, 8, 8, 3, 5, 9, 1, 4, 12, 5, 6],  # sequence 7
     [7, 1, 7, 3, 4, 1, 2],  # sequence 8
     [9, 4, 12, 12, 6, 5, 1],  # sequence 9
]

lens = np.fromiter(map(len, x), np.int)
n1, n2 = len(lens), lens.max()
arr = np.zeros((n1, n2), dtype=np.int)

mask = np.arange(n2) < lens[:,None]
arr[mask] = np.concatenate(x)
arr
>> [[ 1  2  3  4  5  6  7  0  0  0  0]
[ 6  5 10 11  0  0  0  0  0  0  0]
 [ 9  8  2  3  4  5  0  0  0  0  0]
 [12 12  6  5  0  0  0  0  0  0  0]
 [ 5  8  3  4  2  0  0  0  0  0  0]
 [ 1  5  0  0  0  0  0  0  0  0  0]
 [ 2  8  8  3  5  9  1  4 12  5  6]
 [ 7  1  7  3  4  1  2  0  0  0  0]
 [ 9  4 12 12  6  5  1  0  0  0  0]]

Для второго вопроса: используйте np.where, чтобы найти различные позиции, соответствующие вашему состоянию. Затем вы можете транслировать значения строк и столбцов, добавив измерения, включающие 5 s и предыдущие 4 элемента:

M = 4
N = 5
r, c = np.where(arr[:, M-1:]==N)
arr[r[:,None], (c[:,None] + np.arange(M))]
>>array([[ 2,  3,  4,  5],
   [ 2,  3,  4,  5],
   [12, 12,  6,  5],
   [ 8,  8,  3,  5],
   [ 1,  4, 12,  5],
   [12, 12,  6,  5]])

Answer 3

Ваш вопрос состоит из двух частей:

Чтобы сгенерировать нужные вам подпоследовательности, вы можете использовать генератор, чтобы помочь вам:

def gen_m(lst, m, val):
    '''
    lst = sub_list to parse
    m = length required
    val = target value
    '''

    found = 0                                  # starts with 0 index
    for i in range(lst[m-1:].count(val)):      # repeat by the count of val
        found = lst.index(val, found) + 1      # set and find the next index of val
        yield tuple(lst[found-m: found])       # yield the sliced sub_list of m length as a tuple

Затем, используя другой генератор, вы можете создайте Counter из ваших подсписков:

from collections import Counter
target = 5
req_len = 4

# the yielded sub_lists need to be tuples to be hashable for the Counter
counter = Counter(sub_tup for lst in x for sub_tup in gen_m(lst, req_len, target))

Затем создайте генератор для проверки объекта счетчика, чтобы получить необходимое количество N:

req_N = 2

def gen_common(counter, n):
    s = set()
    for i, (item, count) in enumerate(counter.most_common()):
        if i < n or count in s:
            yield item
        else:
            return
        s.add(count)

result = list(gen_common(counter, req_N))

Результаты где N == 2:

[[2, 3, 4, 5], [12, 12, 6, 5]]

Результаты, где N == 3:

[[2, 3, 4, 5], [12, 12, 6, 5], [8, 8, 3, 5], [1, 4, 12, 5]]

При увеличении выборки:

x = [[1, 2, 3, 4, 5, 6, 7],  
     [6, 5, 10, 11],  
     [9, 8, 2, 3, 4, 5],  
     [12, 12, 6, 5],  
     [5, 8, 3, 4, 2],  
     [1, 5],  
     [2, 8, 8, 3, 5, 9, 1, 4, 12, 5, 6],  
     [7, 1, 7, 3, 4, 1, 2],  
     [9, 4, 12, 12, 6, 5, 1],  
     [9, 4, 12, 12, 6, 5, 1],  
     [9, 4, 2, 3, 4, 5, 1],  
     [9, 4, 8, 8, 3, 5, 1],  
     [9, 4, 7, 8, 9, 5, 1],     
     [9, 4, 1, 2, 2, 5, 1],  
     [9, 4, 12, 12, 6, 5, 1],  
     [9, 4, 12, 12, 6, 5, 1],  
     [9, 4, 1, 4, 12, 5],  
     [9, 1, 4, 12, 5, 1]  
]

Где Counter сейчас:

Counter({(12, 12, 6, 5): 5, (2, 3, 4, 5): 3, (1, 4, 12, 5): 3, (8, 8, 3, 5): 2, (7, 8, 9, 5): 1, (1, 2, 2, 5): 1})

Вы можете получить следующие результаты:

for i in range(6):
    # testing req_N from 0 to 5
    list(gen_common(c, i))

# req_N = 0: []
# req_N = 1: [(12, 12, 6, 5)]
# req_N = 2: [(12, 12, 6, 5), (2, 3, 4, 5), (1, 4, 12, 5)]
# req_N = 3: [(12, 12, 6, 5), (2, 3, 4, 5), (1, 4, 12, 5)]
# req_N = 4: [(12, 12, 6, 5), (2, 3, 4, 5), (1, 4, 12, 5), (8, 8, 3, 5)]
# req_N = 5: [(12, 12, 6, 5), (2, 3, 4, 5), (1, 4, 12, 5), (8, 8, 3, 5), (7, 8, 9, 5), (1, 2, 2, 5)]

Answer 4

Вот идея, основанная на структуре обобщенного суффикса . Ваш список списков можно рассматривать как список строк, где алфавит будет состоять из целых чисел (то есть около 10 тысяч символов в алфавите с предоставленной вами информацией).
Построение обобщенного суффиксного дерева выполняется за линейное время по длине строки, так что это не должно быть проблемой, поскольку в любом случае вам придется go, хотя ваши списки в какой-то момент .

Сначала сохраните все свои строки в дереве суффиксов. Это требует 2 небольших модификаций структуры.
Вам необходимо вести счетчик числа вхождений определенного суффикса, поскольку ваша цель в конечном итоге состоит в том, чтобы найти наиболее распространенную подпоследовательность, относящуюся к определенным свойствам.

Затем вы также хотите получить справочную таблицу из (i, d) (где i - целое число, которое вы ищете, цель, а d - глубина в вашем дереве, M) к набору узлов вашей суффиксной ссылки, которые помечены «буквой» i (ваш алфавит состоит не из символов, а из целых чисел), расположенной на глубине d. Эту таблицу поиска можно построить, пройдя по вашей суффиксной ссылке (BFS или DFS). Вы даже можете хранить только тот узел, который соответствует наибольшему значению счетчика.

Оттуда для некоторого запроса (target, M) вы сначала посмотрите в таблицу поиска, а затем найдете узел в дереве с наибольшим значением счетчика. Это будет соответствовать наиболее часто встречающемуся «суффиксу» (или подпоследовательности) в списке списков.

Реализация довольно сложная, поскольку обобщенное суффиксное дерево не является тривиальной структурой (вообще), и его правильная реализация с изменениями не будет маленьким подвигом. Но я думаю, что это позволило бы получить очень эффективное время запроса.

Для реализации дерева суффиксов я бы порекомендовал вам читать только оригинальные статьи, пока вы не получите глубокое и реальное понимание их (например, this или that , s c* - h * b может быть вашим другом) по этому вопросу, а не онлайн-объяснения этого, которые пронизаны аппроксимациями и ошибками (даже этот пост может помочь получить первая идея, но в какой-то момент вас перенаправят, если ваша цель - реализовать правильную версию).