पायथन स्ट्रिंग पैटर्न मान्यता/संपीड़न

Question

मैं मूल रेगेक्स ठीक कर सकता हूं, लेकिन यह थोड़ा अलग है, अर्थात् मुझे नहीं पता कि पैटर्न क्या होने जा रहा है।

lst = ['asometxt0moretxt', 'bsometxt1moretxt', 'aasometxt10moretxt', 'zzsometxt999moretxt'] 

इस मामले आम पैटर्न आम पाठ की दो खंडों है में:

उदाहरण के लिए, मैं इसी तरह के तार की एक सूची है 'moretxt' शुरू 'sometxt' और और कुछ और है कि लंबाई में चर रहा है के द्वारा अलग ।

सामान्य स्ट्रिंग और चर स्ट्रिंग किसी भी क्रम में और किसी भी अवसर पर हो सकती है।

स्ट्रिंग्स की सूची को उनके सामान्य भागों और व्यक्तिगत विविधताओं में संक्षिप्त/संपीड़ित करने का एक अच्छा तरीका क्या होगा?

एक उदाहरण उत्पादन हो सकता है:

c = ['sometxt', 'moretxt'] 

v = [('a','0'), ('b','1'), ('aa','10'), ('zz','999')] 

Answer 1

कैसे जाना जाता पाठ, और फिर बंटवारे बाहर subbing के बारे में?

import re 
[re.sub('(sometxt|moretxt)', ',', x).split(',') for x in lst] 
# results in 
[['a', '0', ''], ['b', '1', ''], ['aa', '10', ''], ['zz', '999', '']] 

Answer 2

मुझे लगता है कि आपको स्ट्रिंग में अक्सर होने वाले सबस्ट्रिंग्स (पैटर्न) की पहचान करके शुरू करना चाहिए। चूंकि स्ट्रिंग्स के सेट में भरोसेमंद गिनती सबस्ट्रिंग्स कम्प्यूटेशनल रूप से महंगा है, इसलिए आपको कुछ स्मार्ट के साथ आने की आवश्यकता होगी।

मैंने generalized suffix trees(example here) का उपयोग करके बड़ी मात्रा में डेटा पर गिनती की है। एक बार जब आप डेटा में सबसे अधिक सब्सट्रिंग/पैटर्न जानते हैं, तो आप इसे वहां से ले जा सकते हैं।

Answer 3

गेंद रोलिंग प्राप्त करने के लिए यहां एक डरावना व्यक्ति है।

>>> import re 
>>> makere = lambda n: ''.join(['(.*?)(.+)(.*?)(.+)(.*?)'] + ['(.*)(\\2)(.*)(\\4)(.*)'] * (n - 1)) 
>>> inp = ['asometxt0moretxt', 'bsometxt1moretxt', 'aasometxt10moretxt', 'zzsometxt999moretxt'] 
>>> re.match(makere(len(inp)), ''.join(inp)).groups() 
('a', 'sometxt', '0', 'moretxt', '', 'b', 'sometxt', '1', 'moretxt', 'aa', '', 'sometxt', '10', 'moretxt', 'zz', '', 'sometxt', '999', 'moretxt', '') 

मुझे आशा है कि इसके सरासर कुरूपता बेहतर समाधान :)

Answer 4

यह समाधान दो सबसे लंबे समय तक आम सबस्ट्रिंग पाता है और इनपुट तार परिसीमित करने के लिए उन्हें का उपयोग करता प्रेरित करेंगी:

def an_answer_to_stackoverflow_question_1914394(lst): 
    """ 
    >>> lst = ['asometxt0moretxt', 'bsometxt1moretxt', 'aasometxt10moretxt', 'zzsometxt999moretxt'] 
    >>> an_answer_to_stackoverflow_question_1914394(lst) 
    (['sometxt', 'moretxt'], [('a', '0'), ('b', '1'), ('aa', '10'), ('zz', '999')]) 
    """ 
    delimiters = find_delimiters(lst) 
    return delimiters, list(split_strings(lst, delimiters)) 

find_delimiters और दोस्तों पाता है डिलीमीटर:

import itertools 

def find_delimiters(lst): 
    """ 
    >>> lst = ['asometxt0moretxt', 'bsometxt1moretxt', 'aasometxt10moretxt', 'zzsometxt999moretxt'] 
    >>> find_delimiters(lst) 
    ['sometxt', 'moretxt'] 
    """ 
    candidates = list(itertools.islice(find_longest_common_substrings(lst), 3)) 
    if len(candidates) == 3 and len(candidates[1]) == len(candidates[2]): 
     raise ValueError("Unable to find useful delimiters") 
    if candidates[1] in candidates[0]: 
     raise ValueError("Unable to find useful delimiters") 
    return candidates[0:2] 

def find_longest_common_substrings(lst): 
    """ 
    >>> lst = ['asometxt0moretxt', 'bsometxt1moretxt', 'aasometxt10moretxt', 'zzsometxt999moretxt'] 
    >>> list(itertools.islice(find_longest_common_substrings(lst), 3)) 
    ['sometxt', 'moretxt', 'sometx'] 
    """ 
    for i in xrange(min_length(lst), 0, -1): 
     for substring in common_substrings(lst, i): 
      yield substring 


def min_length(lst): 
    return min(len(item) for item in lst) 

def common_substrings(lst, length): 
    """ 
    >>> list(common_substrings(["hello", "world"], 2)) 
    [] 
    >>> list(common_substrings(["aabbcc", "dbbrra"], 2)) 
    ['bb'] 
    """ 
    assert length <= min_length(lst) 
    returned = set() 
    for i, item in enumerate(lst): 
     for substring in all_substrings(item, length): 
      in_all_others = True 
      for j, other_item in enumerate(lst): 
       if j == i: 
        continue 
       if substring not in other_item: 
        in_all_others = False 
      if in_all_others: 
       if substring not in returned: 
        returned.add(substring) 
        yield substring 

def all_substrings(item, length): 
    """ 
    >>> list(all_substrings("hello", 2)) 
    ['he', 'el', 'll', 'lo'] 
    """ 
    for i in range(len(item) - length + 1): 
     yield item[i:i+length] 

split_strings सीमांकक का उपयोग कर तार विभाजन:

import re 

def split_strings(lst, delimiters): 
    """ 
    >>> lst = ['asometxt0moretxt', 'bsometxt1moretxt', 'aasometxt10moretxt', 'zzsometxt999moretxt'] 
    >>> list(split_strings(lst, find_delimiters(lst))) 
    [('a', '0'), ('b', '1'), ('aa', '10'), ('zz', '999')] 
    """ 
    for item in lst: 
     parts = re.split("|".join(delimiters), item) 
     yield tuple(part for part in parts if part != '') 

Answer 5

यह ज्यादा के लिए डेटा (पाठ) संपीड़न LZW एल्गोरिथ्म की तरह लग रहे। वहाँ पाइथन कार्यान्वयन होना चाहिए, जो आप अपनी जरूरत के अनुरूप अनुकूलित कर सकते हैं।

मुझे लगता है कि आपके पास इन सब स्ट्रिंग्स का कोई प्राथमिक ज्ञान नहीं है जो अक्सर दोहराया जाता है।

Answer 6

यह longest common subsequence problem का एक उदाहरण प्रतीत होता है। एक तरीका यह देखने के लिए किया जा सकता है कि कैसे diffs उत्पन्न होते हैं। Hunt-McIlroy algorithm पहला ऐसा प्रतीत होता है, और यह इतना आसान है, खासकर जब से यह स्पष्ट रूप से गैर-ह्युरिस्टिक है।

पहले लिंक में विस्तृत चर्चा और (छद्म) कोड उदाहरण शामिल हैं। मान लीजिए, मैं बिल्कुल ट्रैक का पूरी तरह से नहीं हूं।