सूची में पैटर्न ढूंढना

Question

मैं वर्तमान में पूर्णांक की सूची में पैटर्न खोजने का एक तरीका खोज रहा हूं, लेकिन जिस विधि का मैं उपयोग करने जा रहा हूं वह स्ट्रिंग्स और अन्य सूचियों के साथ पाठ्यक्रम के विभिन्न तत्वों पर लागू होगा। अब मुझे बताएं कि मैं क्या देख रहा हूं।

मैं पूर्णांक की सूची में सबसे लंबा दोहराव पैटर्न ढूंढना चाहता हूं। उदाहरण के लिए,

[1, 2, 3, 4, 1, 2, 3] 
# This list would give 1, 2, 3 

ओवरलैपिंग पैटर्न को त्याग दिया जाना चाहिए। (कुछ नहीं)

[1, 1, 1, 1, 1] 
# Should give 1, 1 Not 1, 1, 1, 1 

यहाँ मुझे मदद नहीं की है।

Finding patterns in a list (पहला जवाब है, बहुत कम स्पष्टीकरण के पीछे तर्क समझ में नहीं आता था। और दूसरा जवाब समस्या केवल तभी पैटर्न को सुलझाने से पहले जाना जाता है को हल करती है।)

Finding integer pattern from a list (पैटर्न दिया जाता है और घटना की संख्या है चाहता है। मेरे प्रश्न से अलग।)

Longest common subsequence problem (अधिकांश लोग इस समस्या से निपटते हैं, हालांकि यह मेरे करीब नहीं है। मुझे पैटर्न की खोज करते समय लगातार तत्वों की आवश्यकता होती है। हालांकि इसमें, अलग-अलग तत्वों को भी बाद के रूप में गिना जाता है।)

यहां मैंने जो कोशिश की।

def pattern(seq): 
    n = len(seq) 
    c = defaultdict(int) # Counts of each subsequence 
    for i in xrange(n): 
     for j in xrange(i + 1, min(n, n/2 + i)): 
      # Used n/2 because I figured if a pattern is being searched 
      # It cant be longer that the half of the list. 
      c[tuple(seq[i:j])] += 1  
    return c 

आप देखते हैं, यह सब उप-सूचियों पाता है और दोहराता के लिए जाँच के रूप में। मैंने इस दृष्टिकोण को थोड़ा सा निष्क्रिय (और अक्षम) पाया और मुझे बेहतर तरीके की आवश्यकता है। क्रिप्या मेरि सहायता करे। अग्रिम में धन्यवाद।

नोट 1: सूची पूर्व निर्धारित है लेकिन मेरी एल्गोरिदम विफलता के कारण, मैं केवल कंप्यूटर को फ्रीज करने से पहले सूची के कुछ हिस्सों को देख सकता हूं। तो जिस पैटर्न को मैं खोजने की कोशिश कर रहा हूं वह खोज सूची के आधे से भी अधिक लंबा हो सकता है, यह खोज सूची से भी लंबा हो सकता है क्योंकि मैं मूल सूची का केवल एक हिस्सा खोज रहा हूं। अगर आप एक बेहतर तरीका पेश करते हैं मैं उपयोग कर रहा हूं, मैं मूल सूची का एक बड़ा हिस्सा खोज सकता हूं इसलिए पैटर्न खोजने में मुझे एक बेहतर मौका मिलेगा। (यदि कोई है।)

नोट 2: यदि आप इसे स्वयं परीक्षण करना चाहते हैं तो यहां सूची का एक हिस्सा है। यह वास्तव में ऐसा लगता है कि एक पैटर्न है, लेकिन मैं इसे विश्वसनीय कोड के साथ परीक्षण करने से पहले सुनिश्चित नहीं हो सकता। Sample List

Note3: मैं इस डाटा माइनिंग का एक गंभीर समस्या के रूप में दृष्टिकोण। और यदि आप एक लंबी व्याख्या करते हैं तो सीखने की कोशिश करेंगे। यह एलसीएस की तुलना में एक और अधिक महत्वपूर्ण समस्या की तरह लगता है, हालांकि एलसीएस अधिक लोकप्रिय है: डी इस विधि को मैं खोजने की कोशिश कर रहा हूं वैज्ञानिकों द्वारा डीएनए पैटर्न खोजने के तरीकों की तरह लगता है।

Answer 1

कोड

"कोई अतिव्यापी" आवश्यकता की अनदेखी करते हुए यहाँ कोड मैं प्रयोग किया जाता है:

def pattern(seq): 
     storage = {} 
     for length in range(1,len(seq)/2+1): 
       valid_strings = {} 
       for start in range(0,len(seq)-length+1): 
         valid_strings[start] = tuple(seq[start:start+length]) 
       candidates = set(valid_strings.values()) 
       if len(candidates) != len(valid_strings.values()): 
         print "Pattern found for " + str(length) 
         storage = valid_strings 
       else: 
         print "No pattern found for " + str(length) 
         return set(filter(lambda x: storage.values().count(x) > 1, storage.values())) 
     return storage 

कि का उपयोग करना, मैं अपने डेटासेट में लंबाई 303 के 8 अलग पैटर्न पाया। कार्यक्रम भी बहुत तेजी से भाग गया।

स्यूडोकोड संस्करण

define patterns(sequence): 
    list_of_substrings = {} 
    for each valid length: ### i.e. lengths from 1 to half the list's length 
     generate a dictionary my_dict of all sub-lists of size length 
     if there are repeats: 
      list_of_substrings = my_dict 
     else: 
      return all repeated values in list_of_substrings 
    return list_of_substrings #### returns {} when there are no patterns