Эмпирические методы

Вот забавная проблема. Более общая форма вашего вопроса такова:

Учитывая повторяющуюся последовательность неизвестной длины, определите период сигнала.

Процесс определения повторяющихся частот известен как преобразование Фурье . В вашем примере случае сигнал чистый и дискретный, но следующее решение будет работать даже при непрерывных шумных данных! БПФ будет пытаться дублировать частоты входного сигнала, аппроксимируя их в так называемом «волновом пространстве» или «пространстве Фурье». В основном пик в этом пространстве соответствует повторяющемуся сигналу. Период вашего сигнала связан с самой длинной длиной волны, которая достигает максимума.

 import itertools # of course this is a fake one just to offer an example def source(): return itertools.cycle((1, 0, 1, 4, 8, 2, 1, 3, 3, 2)) import pylab as plt import numpy as np import scipy as sp # Generate some test data, ie our "observations" of the signal N = 300 vals = source() X = np.array([vals.next() for _ in xrange(N)]) # Compute the FFT W = np.fft.fft(X) freq = np.fft.fftfreq(N,1) # Look for the longest signal that is "loud" threshold = 10**2 idx = np.where(abs(W)>threshold)[0][-1] max_f = abs(freq[idx]) print "Period estimate: ", 1/max_f 

Это дает правильный ответ для этого случая 10 но если N не делит циклы чисто, вы получите приблизительную оценку. Мы можем визуализировать это через:

 plt.subplot(211) plt.scatter([max_f,], [np.abs(W[idx]),], s=100,color='r') plt.plot(freq[:N/2], abs(W[:N/2])) plt.xlabel(r"$f$") plt.subplot(212) plt.plot(1.0/freq[:N/2], abs(W[:N/2])) plt.scatter([1/max_f,], [np.abs(W[idx]),], s=100,color='r') plt.xlabel(r"$1/f$") plt.xlim(0,20) plt.show() 

Ответ Евгения Клюева дает возможность получить ответ, который может быть прав.

Определение

Предположим, что у вас есть последовательность D которая является повторяющейся последовательностью. То есть существует некоторая последовательность d длины L такая, что: D_i = d_{i mod L} , где t_i – i й элемент последовательности t который пронумерован из 0. Будем говорить, что последовательность d порождает D

теорема

Учитывая последовательность D которую вы знаете, порождается некоторой конечной последовательностью t . Учитывая некоторые d невозможно в конечное время решить, генерирует ли он D

доказательство

Поскольку нам разрешено только конечное время, мы можем получить доступ только к конечному числу элементов из D Предположим, что мы обращаемся к первым F элементам D Мы выбрали первый F потому что, если нам разрешено только доступ к конечному числу, множество, содержащее индексы элементов, к которым мы обращались, является конечным и, следовательно, имеет максимум. Пусть это максимум M Тогда мы можем положить F = M+1 , который все еще является конечным числом.

Пусть L – длина d и D_i = d_{i mod L} для i < F . Есть две возможности для D_F это либо то же, что и d_{F mod L} либо нет. В первом случае d похоже, работает, но в последнем случае это не так. Мы не можем знать, какой случай истинен, пока мы не D_F . Однако для этого потребуется доступ к элементам F+1 , но мы ограничены доступом F элементов.

Следовательно, для любого F у нас не будет достаточной информации, чтобы решить, порождает ли d порог D и поэтому невозможно узнать за конечное время, будет ли d порождать D

Выводы

В конечное время можно узнать, что последовательность d не порождает D , но это вам не поможет. Поскольку вы хотите найти последовательность d , которая генерирует D , но это включает в себя, среди прочего, возможность доказать, что некоторая последовательность порождает D

Если у вас нет дополнительной информации о D эта проблема неразрешима. Один бит информации, который сделает эту проблему разрешимой, – это верхняя граница длины кратчайшего d которая генерирует D Если вы знаете, что функция, генерирующая D имеет только известное количество конечного состояния, вы можете вычислить эту верхнюю границу.

Следовательно, мой вывод состоит в том, что вы не можете решить эту проблему, если вы немного измените спецификацию.

Поскольку ваша последовательность не имеет формы X _{n + 1} = f (X _n ), алгоритмы Флойда или Брента напрямую не применимы к вашему делу. Но они могут быть расширены для выполнения задачи:

1. Используйте алгоритм Флойда или Брента, чтобы найти некоторый повторяющийся элемент последовательности.
2. Найдите следующий элемент последовательности с тем же значением. Расстояние между этими элементами является предполагаемым периодом ( k ).
3. Помните следующие k элементов последовательности
4. Найти следующее вхождение этой k -элементной подпоследовательности.
5. Если расстояние между подпоследовательностями больше k , обновите k и продолжайте с шага 3.
6. Повторите шаг 4 несколько раз, чтобы проверить результат. Если максимальная длина повторяющейся подпоследовательности известна априорно, используйте соответствующее количество повторений. В противном случае используйте как можно больше повторений, потому что каждое повторение увеличивает правильность результата.

Если цикл последовательности начинается с первого элемента, проигнорируйте шаг 1 и начните с шага 2 (найдите следующий элемент последовательности, равный первому элементу).

Если цикличность последовательности не начинается с первого элемента, возможно, что алгоритм Флойда или Брента находит некоторый повторяющийся элемент последовательности, которая не принадлежит циклу. Поэтому разумно ограничить количество итераций на шагах 2 и 4, и если этот предел превышен, перейдите к шагу 1.

Я понятия не имею о том, как правильно применять алгоритмы здесь, но я также понимаю, что вы не можете точно знать, что вы обнаружили период, если вы потребляете только конечное число терминов. Во всяком случае, вот что я придумал, это очень наивная реализация, больше для обучения из комментариев, чем для обеспечения хорошего решения (я думаю).

 def guess_period(source, minlen=1, maxlen=100, trials=100): for n in range(minlen, maxlen+1): p = [j for i, j in zip(range(n), source)] if all([j for i, j in zip(range(n), source)] == p for k in range(trials)): return tuple(p) return None 

Однако этот «забывает» начальный порядок и возвращает кортеж, который является циклической перестановкой фактического периода:

 In [101]: guess_period(gen) Out[101]: (0, 1, 4, 8, 2, 1, 3, 3, 1, 1) 

Чтобы компенсировать это, вам нужно будет отслеживать смещение.