La plus longue sous-chaîne commune de plus de deux chaînes - Python

Question

Je cherche une bibliothèque Python pour trouver la plus longue sous-chaîne commune de un ensemble de chaînes. Il y a deux façons de résoudre ce problème:

• à l'aide d'arbres suffixe
• en utilisant la programmation dynamique.

méthode mise en œuvre n'a pas d'importance. Il est important qu'il peut être utilisé pour un ensemble de chaînes (pas seulement deux chaînes).

Answer 1

Ces fonctions paires trouveront la plus longue chaîne commune dans une gamme arbitraire de chaînes:

def long_substr(data): 
    substr = '' 
    if len(data) > 1 and len(data[0]) > 0: 
     for i in range(len(data[0])): 
      for j in range(len(data[0])-i+1): 
       if j > len(substr) and is_substr(data[0][i:i+j], data): 
        substr = data[0][i:i+j] 
    return substr 

def is_substr(find, data): 
    if len(data) < 1 and len(find) < 1: 
     return False 
    for i in range(len(data)): 
     if find not in data[i]: 
      return False 
    return True 


print long_substr(['Oh, hello, my friend.', 
        'I prefer Jelly Belly beans.', 
        'When hell freezes over!']) 

Sans doute l'algorithme pourrait être amélioré et je ne l'ai pas eu beaucoup d'exposition à Python, alors peut-être que cela pourrait être plus efficace sur le plan syntaxique, mais cela devrait faire l'affaire.

EDIT: dans la deuxième fonction is_substr comme démontré par J.F. Sebastian. L'utilisation reste la même. Note: pas de changement à l'algorithme.

def long_substr(data): 
    substr = '' 
    if len(data) > 1 and len(data[0]) > 0: 
     for i in range(len(data[0])): 
      for j in range(len(data[0])-i+1): 
       if j > len(substr) and all(data[0][i:i+j] in x for x in data): 
        substr = data[0][i:i+j] 
    return substr 

Hope this helps,

Jason.

Answer 2

def common_prefix(strings): 
    """ Find the longest string that is a prefix of all the strings. 
    """ 
    if not strings: 
     return '' 
    prefix = strings[0] 
    for s in strings: 
     if len(s) < len(prefix): 
      prefix = prefix[:len(s)] 
     if not prefix: 
      return '' 
     for i in range(len(prefix)): 
      if prefix[i] != s[i]: 
       prefix = prefix[:i] 
       break 
    return prefix 

De http://bitbucket.org/ned/cog/src/tip/cogapp/whiteutils.py

Answer 3

# this does not increase asymptotical complexity 
# but can still waste more time than it saves. TODO: profile 
def shortest_of(strings): 
    return min(strings, key=len) 

def long_substr(strings): 
    substr = "" 
    if not strings: 
     return substr 
    reference = shortest_of(strings) #strings[0] 
    length = len(reference) 
    #find a suitable slice i:j 
    for i in xrange(length): 
     #only consider strings long at least len(substr) + 1 
     for j in xrange(i + len(substr) + 1, length + 1): 
      candidate = reference[i:j] # ↓ is the slice recalculated every time? 
      if all(candidate in text for text in strings): 
       substr = candidate 
    return substr 

Avertissement Cela ajoute très peu à la réponse de jtjacques. Cependant, espérons-le, cela devrait être plus lisible et plus rapide et il ne correspondait pas à un commentaire, donc pourquoi je poste ceci dans une réponse. Je ne suis pas satisfait de shortest_of, pour être honnête.

Answer 4

Vous pouvez utiliser le module qui est un arbre des suffixes emballage basé sur une implémentation ANSI C d'arbres suffixe généralisés. Le module est facile à manipuler ....

Jetez un oeil à: here

Answer 5

Je préfère cela pour is_substr, que je trouve un peu plus lisible et intuitive:

def is_substr(find, data): 
    """ 
    inputs a substring to find, returns True only 
    if found for each data in data list 
    """ 

    if len(find) < 1 or len(data) < 1: 
    return False # expected input DNE 

    is_found = True # and-ing to False anywhere in data will return False 
    for i in data: 
    print "Looking for substring %s in %s..." % (find, i) 
    is_found = is_found and find in i 
    return is_found 

Answer 6

Si quelqu'un est à la recherche d'une version généralisée qui peut aussi prendre une liste de séquences d'objets arbitraires:

def get_longest_common_subseq(data): 
    substr = [] 
    if len(data) > 1 and len(data[0]) > 0: 
     for i in range(len(data[0])): 
      for j in range(len(data[0])-i+1): 
       if j > len(substr) and is_subseq_of_any(data[0][i:i+j], data): 
        substr = data[0][i:i+j] 
    return substr 

def is_subseq_of_any(find, data): 
    if len(data) < 1 and len(find) < 1: 
     return False 
    for i in range(len(data)): 
     if not is_subseq(find, data[i]): 
      return False 
    return True 

# Will also return True if possible_subseq == seq. 
def is_subseq(possible_subseq, seq): 
    if len(possible_subseq) > len(seq): 
     return False 
    def get_length_n_slices(n): 
     for i in xrange(len(seq) + 1 - n): 
      yield seq[i:i+n] 
    for slyce in get_length_n_slices(len(possible_subseq)): 
     if slyce == possible_subseq: 
      return True 
    return False 

print get_longest_common_subseq([[1, 2, 3, 4, 5], [2, 3, 4, 5, 6]]) 

print get_longest_common_subseq(['Oh, hello, my friend.', 
            'I prefer Jelly Belly beans.', 
            'When hell freezes over!']) 

Answer 7

Cela peut se faire plus court:Les ensembles sont (probablement) implémentés sous forme de tables de hachage, ce qui rend cela un peu inefficace. Si vous (1) mettre en œuvre un type de jeu en tant que structure arborescente et (2) enregistrer uniquement les postfixes dans la structure arborescente, puis forcer chaque noeud à un point final (ce serait l'équivalent d'ajouter tous les sous-chaînes), alors en théorie, je suppose ce bébé est plutôt efficace sur le plan de la mémoire, d'autant plus que les intersections d'essais sont super faciles.

Néanmoins, ceci est l'optimisation à court et prématurée est la racine d'une quantité importante de temps perdu.