Riconoscimento/compressione del modello di stringa di Python

Question

Posso eseguire espressioni regolari di base, ma questo è leggermente diverso, ovvero non so quale sarà il modello.

Ad esempio, ho un elenco di stringhe simili:

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

In questo caso il modello comune è di due segmenti di testo comune: 'sometxt' e 'moretxt', partendo e separati da qualcos'altro che è di lunghezza variabile .

La stringa comune e la stringa variabile possono naturalmente verificarsi in qualsiasi ordine e in qualsiasi numero di occasioni.

Quale sarebbe un buon modo per condensare/comprimere l'elenco di stringhe nelle parti comuni e nelle singole varianti?

Un'uscita esempio potrebbe essere:

c = ['sometxt', 'moretxt'] 

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

Answer 1

Come circa subbing il testo noto, e quindi la scissione?

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

Answer 2

Immagino che dovresti iniziare identificando sottostringhe (schemi) che si verificano frequentemente nelle stringhe. Dal momento che contare ingenuamente sottostringhe in un set di stringhe è piuttosto dispendioso dal punto di vista computazionale, dovrai inventare qualcosa di intelligente.

Ho eseguito la sottostringa contando su una grande quantità di dati utilizzando generalized suffix trees(example here). Una volta che conosci le sottostringhe/pattern più frequenti nei dati, puoi prenderli da lì.

Answer 3

Ecco uno spaventoso per far rotolare la palla.

>>> 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', '') 

spero sua pura bruttezza ispirerà soluzioni migliori :)

Answer 4

Questa soluzione trova i due sottostringhe più lunga comuni e li utilizza per delimitare le stringhe di input:

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 e amici reperti i delimitatori:

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 divide le stringhe utilizzando i delimitatori:

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

questo aspetto molto simile al LZW algoritmo per i dati (testo) di compressione. Ci dovrebbero essere implementazioni Python là fuori, che potresti essere in grado di adattarsi alle tue necessità.

Suppongo che tu non abbia una conoscenza a priori di queste stringhe che si ripetono spesso.

Answer 6

Questo sembra essere un esempio di longest common subsequence problem. Un modo potrebbe essere quello di vedere come vengono generati diffs. Il Hunt-McIlroy algorithm sembra essere stato il primo, ed è il più semplice, soprattutto perché apparentemente non è euristico.

Il primo collegamento contiene una discussione dettagliata e esempi di codice (pseudo). Supponendo, ovviamente, non sono completamente del brano qui.