Finden von Mustern in der Liste

Question

Ich suche derzeit nach einer Möglichkeit, Muster in einer Liste von ganzen Zahlen zu finden, aber die Methode, die ich verwenden werde, wäre natürlich auch auf Strings und andere Listen mit verschiedenen Elementen anwendbar. Jetzt lass mich erklären, wonach ich suche.

Ich möchte das längste sich wiederholende Muster in einer Liste von ganzen Zahlen finden. Zum Beispiel

[1, 2, 3, 4, 1, 2, 3] 
# This list would give 1, 2, 3 

Überlappende Muster sollten verworfen werden. (Nicht sicher)

[1, 1, 1, 1, 1] 
# Should give 1, 1 Not 1, 1, 1, 1 

Hier ist, was nicht mir geholfen hat.

Finding patterns in a list (Hat die Logik hinter der ersten Antwort nicht verstehen, sehr wenig Erklärung. Und zweitens Antwort löst das Problem nur, wenn das Muster vor der Lösung bekannt ist.)

Finding integer pattern from a list (Muster gegeben und die Anzahl des Auftretens Anders als meine Frage.)

Longest common subsequence problem (Die meisten Leute haben sich mit diesem Problem beschäftigt, aber es ist nicht nahe bei mir. Ich brauche konsekutive Elemente während der Suche nach einem Muster. Allerdings werden dabei einzelne Elemente als Teilfolgen gezählt.)

Hier was ich versucht habe.

def pattern(seq): 
    n = len(seq) 
    c = defaultdict(int) # Counts of each subsequence 
    for i in xrange(n): 
     for j in xrange(i + 1, min(n, n/2 + i)): 
      # Used n/2 because I figured if a pattern is being searched 
      # It cant be longer that the half of the list. 
      c[tuple(seq[i:j])] += 1  
    return c 

Wie Sie sehen, es alle Teil-Listen findet und für Wiederholungen überprüfen. Ich fand diesen Ansatz ein wenig naiv (und ineffizient) und ich brauche einen besseren Weg. Bitte hilf mir. Danke im Voraus.

Anmerkung1: Die Liste ist vorbestimmt, aber wegen meines Algorithmusfehlers kann ich nur einige Teile der Liste überprüfen, bevor ich den Computer einfriere. So kann das Muster, das ich finde, sehr wohl länger sein als die Hälfte der Suchliste, es kann sogar länger sein als die Suchliste selbst, da ich nur einen Teil der ursprünglichen Liste durchsuche. Wenn Sie eine bessere Methode präsentieren als Ich benutze, ich kann einen größeren Teil der ursprünglichen Liste suchen, damit ich eine bessere Chance habe, das Muster zu finden. (Wenn es einen gibt.)

Hinweis2: Hier ist ein Teil der Liste, wenn Sie es selbst testen möchten. Es scheint wirklich, dass es ein Muster gibt, aber ich kann nicht sicher sein, bevor ich es mit einem zuverlässigen Code teste. Sample List

Note3: Ich gehe dies als ernstes Problem des Data Mining. Und versuchen zu lernen, wenn Sie eine lange Erklärung geben. Dies ist ein viel wichtigeres Problem als LCS, aber LCS ist viel beliebter: D Diese Methode, die ich versuche zu finden, fühlt sich an wie die Methoden, mit denen Wissenschaftler DNA-Muster finden.

Answer 1

Der Kodex

die "keine Überlappung" Anforderung Ignorieren, hier ist der Code, den ich verwenden:

def pattern(seq): 
     storage = {} 
     for length in range(1,len(seq)/2+1): 
       valid_strings = {} 
       for start in range(0,len(seq)-length+1): 
         valid_strings[start] = tuple(seq[start:start+length]) 
       candidates = set(valid_strings.values()) 
       if len(candidates) != len(valid_strings.values()): 
         print "Pattern found for " + str(length) 
         storage = valid_strings 
       else: 
         print "No pattern found for " + str(length) 
         return set(filter(lambda x: storage.values().count(x) > 1, storage.values())) 
     return storage 

dass Verwendung, I 8 verschiedene Muster mit einer Länge von 303 in ihrem Datensatz gefunden. Das Programm lief auch ziemlich schnell.

Pseudocode Version

define patterns(sequence): 
    list_of_substrings = {} 
    for each valid length: ### i.e. lengths from 1 to half the list's length 
     generate a dictionary my_dict of all sub-lists of size length 
     if there are repeats: 
      list_of_substrings = my_dict 
     else: 
      return all repeated values in list_of_substrings 
    return list_of_substrings #### returns {} when there are no patterns