Поиск шаблонов в списке

Question

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

Я хочу найти самый длинный повторяющийся шаблон в списке целых чисел. Например,

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

Перекрывающие шаблоны следует отбрасывать. (Не уверен)

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

Вот что мне не помог.

Finding patterns in a list (не понял логику первого ответа, очень мало объяснений. И второй ответ решает проблему только тогда, когда модель известна до решения.)

Finding integer pattern from a list (Pattern дается и число возникновения разумеется. Разница, чем мой вопрос.)

Longest common subsequence problem (Большинство людей занималось этой проблемой, однако оно не близко к моему. Мне нужны последовательные элементы при поиске шаблона. Однако в этом отдельные элементы также учитываются как подпоследовательности.)

Здесь я попробовал.

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 

Как вы видите, он находит все подсписки и проверить повторы. Я нашел этот подход немного наивным (и неэффективным), и мне нужен лучший способ. Пожалуйста, помогите мне. Заранее спасибо.

Note1: Список предопределен, но из-за отказа моих алгоритмов я могу проверить некоторые части списка перед замораживанием компьютера. Таким образом, шаблон, который я пытаюсь найти, может быть намного длиннее половины списка поиска. Он может даже быть длиннее самого списка поиска, потому что я ищу только часть исходного списка. Если вы представляете лучший метод, чем Я использую, я могу искать большую часть исходного списка, поэтому у меня будет больше шансов найти шаблон. (Если таковой имеется.)

Примечание2: Вот часть списка, если вы хотите протестировать его самостоятельно. Кажется, что есть шаблон, но я не могу быть уверен, прежде чем тестировать его с помощью надежного кода. Sample List

Note3: подхожу это как серьезную проблему интеллектуального анализа данных. И попробуем узнать, если вы сделаете длинное объяснение. Это похоже на гораздо более важную проблему, чем LCS, однако LCS намного более популярен: D Этот метод, который я пытаюсь найти, похож на методы, которые ученые используют для поиска ДНК-образцов.

Answer 1

Кодекс

Игнорирование «без перекрытия» требование, вот код, который я использовал:

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 

Используя это, я нашел 8 различных моделей длиной 303 в наборе данных. Программа работала довольно быстро.

ПСЕВДОКОД Версия

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