큰 목록 내에서 반복 저널 찾기

Question

반복되는 패턴의 시작과 끝 위치를 찾으려는 큰 목록의 하위 목록 (약 16000)이 있습니다. 나는 반복이 있다는 것을 100 % 확신하지는 못했지만 하위 목록 순서에 나타나는 대각선 때문에 그렇게 믿을만한 이유가 있습니다. 하위 목록의 구조는이 스크립트의 다른 것들에 사용되는 방식으로 선호됩니다. 데이터는 다음과 같습니다

data = ['1100100100000010', 
     '1001001000000110', 
     '0010010000001100', 
     '0100100000011011', etc 

내가 언제 제약, 그러나 가장 빠른 방법에 싫은 내색되지 않을이 없습니다. 코드는 앞으로 호출 될 시작/끝 시퀀스와 목록 내의 위치를 ​​반환 할 수 있어야합니다. 좀 더 유용하게 사용할 수있는 데이터 배열이 있다면 필요하다면 다시 포맷 할 수 있습니다. 파이썬은 내가 지난 몇 개월 동안 배웠던 무언가이기 때문에 아직 처음부터 내 자신의 알고리즘을 만들 수는 없습니다. 고맙습니다!

Answer 1

다음은 인접한 반복 하위 시퀀스에 대해 문자열을 검색하는 몇 가지 간단한 코드입니다. minrun을 검사 할 가장 작은 하위 시퀀스의 길이로 설정하십시오. 매치마다 코드는 첫 번째 하위 시퀀스의 시작 인덱스, 하위 시퀀스의 길이 및 하위 시퀀스 자체를 인쇄합니다.

data = [ 
    '1100100100000010', 
    '1001001000000110', 
    '0010010000001100', 
    '0100100000011011', 
] 
data = ''.join(data) 

minrun = 3 
lendata = len(data) 
for runlen in range(minrun, lendata // 2): 
    i = 0 
    while i < lendata - runlen * 2: 
     s1 = data[i:i + runlen] 
     s2 = data[i + runlen:i + runlen * 2] 
     if s1 == s2: 
      print(i, runlen, s1) 
      i += runlen 
     else: 
      i += 1 

출력 우리는 인덱스 (15)에서 길이 (3)의 동일한 시퀀스를 얻을

1 3 100 
4 3 100 
8 3 000 
15 3 010 
18 3 010 
23 3 000 
32 3 001 
38 3 000 
47 3 001 
53 3 000 
17 15 001001000000110 
32 15 001001000000110 

주 18 = 15 + 3 010; 이는 010의 인접한 사본이 3 개 있음을 나타냅니다. 마찬가지로 길이 15의 색인 17에 인접한 사본 3 개가 있습니다.