Thuật toán nhanh để tìm kiếm mẫu trong tệp văn bản

Question

Tôi có một mảng đôi, khoảng 200.000 hàng bởi 100 cột và tôi đang tìm một thuật toán nhanh để tìm các hàng có chứa các chuỗi tương tự nhất với mẫu đã cho (mẫu có thể ở bất kỳ đâu từ 10 đến 100 phần tử). Tôi đang sử dụng python, do đó, phương pháp bạo lực (mã bên dưới: lặp qua mỗi hàng và chỉ mục cột bắt đầu, và tính toán khoảng cách Euclide tại mỗi điểm) mất khoảng ba phút.

Chức năng numpy.correlate hứa hẹn sẽ giải quyết vấn đề này nhanh hơn nhiều (chạy trên cùng một tập dữ liệu trong chưa đầy 20 giây). Tuy nhiên, nó chỉ đơn giản là tính toán một sản phẩm chấm trượt của mẫu trên toàn bộ hàng, có nghĩa là để so sánh sự tương tự tôi sẽ phải chuẩn hóa kết quả trước tiên. Bình thường hóa mối tương quan chéo đòi hỏi tính toán độ lệch chuẩn của mỗi phần dữ liệu, điều này ngay lập tức phủ nhận việc cải thiện tốc độ sử dụng numpy.correlate ngay từ đầu.

Có thể tính toán tương quan chéo chuẩn hóa nhanh chóng trong python không? Hoặc tôi sẽ phải nghỉ mát để mã hóa phương pháp bạo lực trong C?

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] 

Answer 1

Nếu dữ liệu của bạn nằm trong mảng 2D Numpy, bạn có thể lấy lát 2D từ cột 200.000 hàng (mẫu) và tính toán chỉ tiêu cho tất cả các hàng cùng một lúc. Sau đó trượt cửa sổ sang phải trong vòng lặp 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)