Найти повторяющийся узор в строке - PullRequest
Новая
       20

Найти повторяющийся узор в строке

0 голосов
/ 25 октября 2018

Предположим, у меня есть длинная строка: 

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

Я начал с создания структурного представления (преобразование [AZ] в «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 ...

Мой вопрос: как мне распознать шаблон в каждой строке на лету, а затем получить совпадения?

ПРИМЕЧАНИЕ: Шаблоннеизвестно, но известно, что некоторый набор символов повторяется через некоторое время

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

Ответы [ 2 ]

0 голосов
/ 25 октября 2018

Если вы знаете, что все ваши целевые строки начинаются с шаблона в верхнем регистре 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 для удовлетворения этих различных требований.

Если шаблон действительно периодический, то вы можете получитьпокончим с чем-то похожим на частотный анализ, но тогда вы должны знать кое-что о том, «что» является периодическим (например, «числа не являются периодом»), и затем надеяться, что строка будет достаточно длинной, чтобы обеспечить значимый периодический сигнал.Это то, к чему @zwer обращается ... «какие свойства паттерна вы ожидаете».

0 голосов
/ 25 октября 2018

Вы можете попытаться использовать time series analysis сезонность, чтобы получить похожие шаблоны в последовательности

, для этого вы можете попробовать преобразовать строку в целые числа и применить season_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()

Наблюдаемая сезонность и тренд последовательности enter image description here

, затем с наблюдаемым периодом вы можете разделитьпоследовательность

Редактировать

Чтобы найти периодичность последовательности без визуального контроля,

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

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

Out: 

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