在字符串中查找重复模式

Question

假设我有一个长字符串：

AX 90 10 20 AX 30 14 50 ER 40 50 68 ...

我需要的是

['AX 90 10 20', 'AX 30 14 50', 'ER 40 50 68',...]

我不想使用正则表达式，因为我会得到不同的重复模式，例如下面的内容，上面的正则表达式不适用于下面的内容

WE 12 (09/09) ER 14 (12/56) TO 90 (45/67) ...

我开始为第一个示例创建结构表示（将 [A-Z] 转换为 'A' 并将 [0-9] 转换为 '9'）

AX 90 10 20 AX 30 14 50 ER 40 50 68 ...
to
AA 99 99 99 AA 99 99 99 AA 99 99 99 ...

我的问题是，如何动态识别每个字符串中的模式然后进行匹配？

注意： 模式未知，但已知某些字符集会在一段时间后重复出现

我不想使用手动编写的正则表达式。如果系统生成正则表达式，那就没问题了。

Answer 1

您可以尝试使用 time series analysis 季节性来按顺序获得相似的模式

为此，您可以尝试将字符串转换为整数，然后应用 seasonal_decompose 并使用 statsmodels ，然后您可以从图中观察重复模式的周期。

from matplotlib import pyplot
from statsmodels.tsa.seasonal import seasonal_decompose
a = 'AX 90 10 20 AX 30 14 50 ER 40 50 68'
a = list(map(ord,a))
series = pd.Series(a ,index = pd.date_range('1-1-2011',pd.to_datetime('1-1-2011')+np.timedelta64(len(a)-1,'D'),freq='D'))
result = seasonal_decompose(series, model='additive')

result.observed.plot()
result.trend.plot()
pyplot.rcParams["figure.figsize"] = (20,3)
pyplot.show()

观察到的季节性和序列趋势

然后用观察到的周期你可以拆分序列

编辑

无需目测即可找出序列的周期性，

我们可以利用autocorrelation和显示周期性的信号相关滞后来找到信号的周期性。这样我们就可以对模式进行切片以检索相似的模式

def autocorr(x):
    n = x.size
    norm = (x - np.mean(x))
    result = np.correlate(norm, norm, mode='same')
    acorr = result[n//2 + 1:] / (x.var() * np.arange(n-1, n//2, -1))
    lag = np.abs(acorr).argmax() + 1
    return lag
period = autocorr(np.array(a))



#Here the pattern is repeating for each period of 12 values, you can pick the period also 
period = 12
for i in range(0,len(a),period):
    print(''.join(map(chr,a[i:i+period])))

输出：

AX 90 10 20 
AX 30 14 50 
ER 40 50 68

Answer 2

如果您知道您的目标字符串都以 N 长度（此处为 2）大写模式开头，我不确定这是否复杂。

以下是可能的解决方案：

import re # only used in is_token, but not technically needed

def is_token(t):
    return re.match(r'^[A-Z]+$', t)

def get_token_candidate_at(s, idx):
    return s[idx:idx+2]

def emit_items(s):
    delim_start = -1
    for i,_ in enumerate(s):
        token = get_token_candidate_at(s, i)

        if is_token(token):
            if delim_start >= 0:
                yield s[delim_start:i]
            delim_start = i

    if delim_start > 0: # get the last one
        yield s[delim_start:]

> list(emit_items("WE 12 (09/09) ER 14 (12/56) TO 90 (45/67)"))
  ['WE 12 (09/09) ', 'ER 14 (12/56) ', 'TO 90 (45/67)']

> list(emit_items("WE12(09/09)ER14(12/56)TO90(45/67)"))
  ['WE12(09/09)', 'ER14(12/56)', 'TO90(45/67)']

> list(emit_items("AZ893249EE886342TT125435"))
  ['AZ893249', 'EE886342', 'TT125435']

如果他们有不同的开始，您可以更改 is_token 和 get_token_candidate_at 以满足这些不同的要求。

如果模式确实是周期性的，那么您也许可以通过类似于频率分析的方法逃脱，但是您必须知道 "what" 是周期性的（例如 'non-numbers are period'）然后希望字符串足够长以提供有意义的周期信号。这就是@zwer 的意思..."what are the properties of the pattern that you are expecting".

在字符串中查找重复模式

Find repeating pattern in a string

python

string

pattern-recognition