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

Question

Je suis à la recherche d'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, il peut être utilisé pour un ensemble de chaînes (non seulement deux cordes).

Answer 1

Ces fonctions paires trouverez la plus longue chaîne commune dans un ensemble 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 n'ai pas eu beaucoup d'exposition à Python, alors peut-être il pourrait être plus efficace syntaxiquement aussi bien, mais il doit faire le travail.

EDIT: in-doublé la seconde fonction de is_substr comme démontré par J. F. Sebastian. Utilisation reste le 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

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 3

Cela peut se faire plus court:

def long_substr(data):
  substrs = lambda x: {x[i:i+j] for i in range(len(x)) for j in range(len(x) - i + 1)}
  s = substrs(data[0])
  for val in data[1:]:
    s.intersection_update(substrs(val))
  return max(s, key=len)

ensemble de sont (probablement) mis en œuvre en tant que hachage cartes, ce qui en fait un peu inefficace. Si vous (1) mettre en œuvre un type ensemble comme Trie et (2) enregistrer uniquement les suffixes 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 assez efficace de la mémoire, d'autant plus que les intersections des essais sont super facile.

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

Answer 4

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 5

# 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

Disclaimer 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 cadrait pas dans un commentaire, donc pourquoi je poste ceci dans une réponse. Je ne suis pas satisfait de shortest_of, pour être honnête.

Answer 6

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 à:

Answer 7

Si quelqu'un est à la recherche d'une version généralisée qui peut également 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!'])