텍스트 파일 내에서 패턴을 검색하는 빠른 알고리즘

나는 두 배의 배열, 대략 200,000 x 100 개의 열을 가지고 있으며 주어진 패턴과 가장 유사한 시퀀스를 포함하는 행을 찾는 빠른 알고리즘을 찾고 있습니다. 패턴은 10 개에서 100 개까지의 요소가 될 수 있습니다. 파이썬을 사용하고 있으므로 무차별 방식 (아래 코드 : 각 행을 반복하고 열 인덱스를 시작하고 각 점에서 유클리드 거리를 계산)에 약 3 분이 걸립니다.텍스트 파일 내에서 패턴을 검색하는 빠른 알고리즘

numpy.correlate 함수는이 문제를 훨씬 빨리 (20 초 이내에 동일한 데이터 세트를 통해 실행) 해결할 것을 약속합니다. 그러나 전체 행에 걸쳐 패턴의 슬라이딩 내적을 단순히 계산합니다. 즉, 유사성을 비교하기 위해 먼저 결과를 정규화해야합니다. 교차 상관 관계를 정규화하려면 데이터의 각 슬라이스의 표준 편차를 계산해야합니다. 즉, 처음에는 numpy.correlate를 사용하는 속도 향상을 즉각적으로 무효화합니다.

파이썬에서 정규화 된 상호 상관을 신속하게 계산할 수 있습니까? 아니면 C에서 무차별 대입 메소드를 코딩해야할까요? 데이터는 2D NumPy와 배열에있는 경우

def norm_corr(x,y,mode='valid'): 
    ya=np.array(y) 
    slices=[x[pos:pos+len(y)] for pos in range(len(x)-len(y)+1)] 
    return [np.linalg.norm(np.array(z)-ya) for z in slices] 

similarities=[norm_corr(arr,pointarray) for arr in arraytable]

출처

2012-02-06 sbrother

나는 잘 모르겠다. 그래서 아이디어를 내고있다 : 아마도 더 빠른 슬라이딩 방법이 stddev를 계산할 것인가? – liori

호기심을 더하려고합니다. 내 컴퓨터에서 코드를 시도한 결과 7 초 만에 실행되었습니다. 내가 슬라이스 배열 개체의 양을 만들려고하지 않는 것이 좋습니다 것이지만, 아직 어떻게 해야할지 모르겠다. –

, 당신은 (LEN (패턴) 열로 200000 행) 그것에서 2 차원 조각을 한 번에 모든 행에 대한 표준을 계산할 수 있습니다. 그런 다음 for 루프에서 창을 오른쪽으로 밉니다.

ROWS = 200000 
COLS = 100 
PATLEN = 20 
#random data for example's sake 
a = np.random.rand(ROWS,COLS) 
pattern = np.random.rand(PATLEN) 

tmp = np.empty([ROWS, COLS-PATLEN]) 
for i in xrange(COLS-PATLEN): 
    window = a[:,i:i+PATLEN] 
    tmp[:,i] = np.sum((window-pattern)**2, axis=1) 

result = np.sqrt(tmp)

출처

2012-02-06 20:47:48

정확히 내가 뭘 찾고 있었는지, 고마워! – sbrother

텍스트 파일 내에서 패턴을 검색하는 빠른 알고리즘

답변

관련 문제