Какой самый эффективный способ идентификации повторный образец в массиве объектов с использованием Python

Question

У меня есть два массива 5 объектов

а = [ «а», «б», «с», «d», 'е', 'е', 'е', 'е']

Ь = [ 'а', 'б', 'd', 'е', 'е', 'е']

Я хотел бы идентифицировать повторяющиеся рисунки более чем одного объекта и их появления, такие как

[ 'а', 'Ь']: 2

[ 'е', 'е']: 3

[ 'е', 'е', 'е']: 2

Первая последовательность ['a', 'b'] появляется один раз в a и один раз в b, поэтому общее число 2. Вторая последовательность ['e', 'f'] появляется дважды в a, один раз в b, поэтому общая 3. Третья последовательность ['f', 'e', ​​'f'] появляется один раз в a и один раз в b, поэтому общая сумма 2.

Есть ли хороший способ сделать это в Python?

Также вселенная объектов ограничена. Интересно, есть ли эффективное решение, использующее хэш-таблицу?

Answer 1

Если подход используется только для двух списков, должен работать следующий подход. Я не уверен, что это наиболее эффективное решение.

Хорошее описание поиска n-граммов дано в this blog post.

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

Затем мы находим все последовательности для каждого из списков путем объединения последовательностей для отдельных списков. Тогда у нас есть счетчик каждой последовательности и ее счет.

Наконец, мы возвращаем словарь всех последовательностей, которые происходят более одного раза.

def find_repeating(list_a, list_b): 
    min_len = 2 

    def find_ngrams(input_list, n): 
     return zip(*[input_list[i:] for i in range(n)]) 

    seq_list_a = [] 
    for seq_len in range(min_len, len(list_a) + 1): 
     seq_list_a += [val for val in find_ngrams(list_a, seq_len)] 

    seq_list_b = [] 
    for seq_len in range(min_len, len(list_b) + 1): 
     seq_list_b += [val for val in find_ngrams(list_b, seq_len)] 

    all_sequences = seq_list_a + seq_list_b 

    counter = {} 
    for seq in all_sequences: 
     counter[seq] = counter.get(seq, 0) + 1 

    filtered_counter = {k: v for k, v in counter.items() if v > 1} 

    return filtered_counter 

Дайте мне знать, если вы не уверены ни о чем.

>>> list_a = ['a', 'b', 'c', 'd', 'e', 'f', 'e', 'f'] 
>>> list_b = ['a', 'b', 'd', 'f', 'e', 'f'] 
>>> print find_repeating(list_a, list_b) 
{('f', 'e'): 2, ('e', 'f'): 3, ('f', 'e', 'f'): 2, ('a', 'b'): 2} 

Answer 2

Когда вы сказали, что вы ищете эффективного решения, моя первая мысль была о подходах к решению longest common subsequence problem. Но в вашем случае нам действительно нужно перечислить все общие подпоследовательности, чтобы мы могли их сосчитать, поэтому решение динамического программирования не будет выполнено. Вот мое решение. Это, конечно, меньше, чем решение SSSINISTER (в основном потому, что я использую класс collections.Counter).

#!/usr/bin/env python3 

def find_repeating(sequence_a, sequence_b, min_len=2): 
    from collections import Counter 

    # Find all subsequences 
    subseq_a = [tuple(sequence_a[start:stop]) for start in range(len(sequence_a)-min_len+1) 
     for stop in range(start+min_len,len(sequence_a)+1)] 
    subseq_b = [tuple(sequence_b[start:stop]) for start in range(len(sequence_b)-min_len+1) 
     for stop in range(start+min_len,len(sequence_b)+1)] 

    # Find common subsequences 
    common = set(tup for tup in subseq_a if tup in subseq_b) 

    # Count common subsequences 
    return Counter(tup for tup in (subseq_a + subseq_b) if tup in common) 

В результате ...

>>> list_a = ['a', 'b', 'c', 'd', 'e', 'f', 'e', 'f'] 
>>> list_b = ['a', 'b', 'd', 'f', 'e', 'f'] 
>>> print(find_repeating(list_a, list_b)) 
Counter({('e', 'f'): 3, ('f', 'e'): 2, ('a', 'b'): 2, ('f', 'e', 'f'): 2}) 

Преимущество использования collections.Counter в том, что вы не только не нужно производить фактический код для перебора и посчитайте, вы получите доступ ко всем dict методов, а также несколько специализированных методов использования этих счетчиков ,