टेक्स्ट फ़ाइल

Question

में पैटर्न की खोज करने के लिए फास्ट एल्गोरिदम मेरे पास 100 कॉलम द्वारा लगभग 200,000 पंक्तियां युगल की एक सरणी है, और मैं पंक्तियों को खोजने के लिए एक तेज़ एल्गोरिदम ढूंढ रहा हूं जिसमें अनुक्रमित पैटर्न के समान अनुक्रम होते हैं (द पैटर्न 10 से 100 तत्वों से कहीं भी हो सकता है)। मैं अजगर का उपयोग कर रहा हूं, इसलिए ब्रूट फोर्स विधि (नीचे कोड: प्रत्येक पंक्ति पर लूपिंग और कॉलम इंडेक्स शुरू करना, और प्रत्येक बिंदु पर यूक्लिडियन दूरी की गणना करना) लगभग तीन मिनट लगते हैं।

numpy.correlate फ़ंक्शन इस समस्या को बहुत तेज़ी से हल करने का वादा करता है (20 सेकंड से भी कम समय में उसी डेटासेट पर चल रहा है)। हालांकि, यह पूरी पंक्ति पर पैटर्न के एक स्लाइडिंग डॉट उत्पाद की गणना करता है, जिसका अर्थ है कि समानता की तुलना करने के लिए मुझे पहले परिणामों को सामान्य करना होगा। क्रॉस-सहसंबंध को सामान्य करने के लिए डेटा के प्रत्येक टुकड़े के मानक विचलन की गणना करने की आवश्यकता होती है, जो पहले स्थान पर numpy.correlate का उपयोग करने की गति सुधार को तुरंत अस्वीकार करता है।

क्या पाइथन में सामान्यीकृत क्रॉस-सहसंबंध की गणना करना संभव है? या मुझे सी में ब्रूट फोर्स विधि को कोड करने का सहारा लेना होगा?

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

अपने डेटा एक 2D Numpy सरणी में है, तो आप एक 2 डी टुकड़ा इसे से (200000 पंक्तियों लेन (पैटर्न) स्तंभों के आधार पर) लेने के लिए और एक ही बार में सभी पंक्तियों के लिए आदर्श की गणना कर सकते हैं। फिर लूप के लिए विंडो को दाईं ओर स्लाइड करें।

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)