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

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

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

[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

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

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

Поиск целочисленного шаблона из списка (Шаблон задан и требуется количество вхождений. Отличается от моего вопроса.)

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

Вот что я пробовал.

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

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

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

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

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

Ответы

Ответ 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 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