パイソン

Question

を使用してオブジェクトの配列内の繰り返しパターンを識別する最も効率的な方法は何私は5つのオブジェクトの二つの配列

= [「A」、「B」、「C」、「D」を有し、 'E'、 'F'、 'E'、 'F']

B = [ 'A'、 'B'、 'D'、 'F'、 'E'、 'F']

複数のオブジェクトとその出現の繰り返しパターンを特定したいと思います。

[ 'A'、 'B']：2

[ 'E'、 'F']：3

[ 'F'、 'E'、 'F']：2

最初のシーケンス['a'、 'b']はaに1回、bに1回出現したので、合計数2となります。2番目のシーケンス['e'、 'f']は、 3番目のシーケンス['f'、 'e'、 'f']はaに1回、bに1回出現し、合計2になります。

これを行うには良い方法がありますか？

また、オブジェクトの世界は限られています。ハッシュテーブルを利用する効率的なソリューションがあるのだろうか？

Answer 1

このアプローチが2つのリストのみである場合は、次のアプローチが有効です。私はこれが最も効率的な解決策であるかどうかはわかりません。

find n-gramsの良い説明は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方法の全てへのアクセスだけでなく、それらのカウントを使用するためのいくつかの特殊な方法を得ることです。