检测未知来源的时间段

Question

如何检测无限序列中的重复数字？我试过Floyd&Brent检测算法,但什么都没有......我有一个生成器,产生0到9(含)的数字,我必须认识到它的一个时期.

示例测试用例:

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, 1))

>>> gen = source()
>>> period(gen)
(1, 0, 1, 4, 8, 2, 1, 3, 3, 1)

Answer 1

经验方法

这是一个有趣的问题.您问题的更一般形式是:

给定未知长度的重复序列,确定信号的周期.

确定重复频率的过程称为傅里叶变换.在您的示例情况下,信号是干净且离散的,但即使连续的噪声数据,以下解决方案也能正常工作!该FFT将尝试通过在所谓的"波空间"或"傅立叶空间"接近他们复制的输入信号的频率.基本上,该空间中的峰值对应于重复信号.信号的周期与峰值的最长波长有关.

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, i.e. 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()