检测的未知源周期 [英] Detect period of unknown source

问题描述

如何检测重复的数字在一个无限序列？我试过弗洛伊德和放大器;布伦特检测算法，但落空... 我有一个发生器，它产生从0到9（含）的数字和我必须承认一个周期中它

例测试用例：

 进口itertools

＃当然，这是一个假的只是为了提供一个例子
高清源（）：
    返回itertools.cycle（（1，0，1，4，8 2，1，3,3，1））

＆GT;＆GT;＆GT;根=源（）
＆GT;＆GT;＆GT;周期（根）
（1，0，1，4，8 2，1，3,3，1）
 

解决方案

实证方法

下面是一个有趣的承担问题。你的问题的更一般的形式是这样的：

  

由于未知长度​​的重复序列，确定的期限   信号

要确定的重复频率被称为傅立叶变换的方法。在您的例子情况下，信号是干净的，离散的，但下面的解决方案，将工作，即使在连续噪声数据！所述 FFT 的将尝试通过近似它们在所谓的波空间，可以复制输入信号的频率或傅立叶空间。基本上在该空间中的峰对应于重复信号。您的信号的周期是有关到正在见顶最长波长

 进口itertools

＃当然，这是一个假的只是为了提供一个例子
高清源（）：
    返回itertools.cycle（（1，0，1，4，8 2，1，3,3，2））

进口pylab为PLT
进口numpy的为NP
进口SciPy的为SP

＃生成一些测试数据，即信号的我们的意见
N = 300
瓦尔斯=源（）
X = np.array（[vals.next（）为_中的xrange（N）]）

＃计算FFT
W = np.fft.fft（X）
频率= np.fft.fftfreq（N，1）

＃查找最长的信号，那就是响亮
阈值= 10 ** 2
IDX = np.where（ABS（W）＆GT;阈值）[0] [ -  1]

max_f = ABS（频率[IDX]）
打印期间估计：，1 / max_f
 

这给出了正确的答案这种情况下， 10 不过，如果 N 没有划分周期干净，你会得到一个接近的估计。我们可以通过想象这样的：

  plt.subplot（211）
plt.scatter（[max_f，]，[np.abs（W [IDX]），]，S = 100，颜色=R）
plt.plot（频率[N / 2]，ABS（W [N / 2]））
plt.xlabel（R$ F $）

plt.subplot（212）
plt.plot（1.0 /频率[N / 2]，ABS（W [N / 2]））
plt.scatter（[1 / max_f，]，[np.abs（W [IDX]），]，S = 100，颜色=R）
plt.xlabel（R$ 1 / F $）
plt.xlim（0,20）

plt.show（）
 

How to detect repeating digits in an infinite sequence? I tried Floyd & Brent detection algorithm but come to nothing... I have a generator that yields numbers ranging from 0 to 9 (inclusive) and I have to recognize a period in it.

Example test case:

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)

解决方案

Empirical methods

Here's a fun take on the problem. The more general form of your question is this:

Given a repeating sequence of unknown length, determine the period of the signal.

The process to determine the repeating frequencies is known as the Fourier Transform. In your example case the signal is clean and discrete, but the following solution will work even with continuous noisy data! The FFT will try to duplicate the frequencies of the input signal by approximating them in the so-called "wave-space" or "Fourier-space". Basically a peak in this space corresponds to a repeating signal. The period of your signal is related to the longest wavelength that is peaked.

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

This gives the correct answer for this case, 10 though if N didn't divide the cycles cleanly, you would get a close estimate. We can visualize this via:

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()

这篇关于检测的未知源周期的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！