La plus longue sous-chaîne commune à partir de plus de deux chaînes de caractères - Python

Question

Je cherche une bibliothèque python pour trouver la plus longue sous-chaîne commune à partir d'un ensemble de chaînes python.

J'ai lu qu'il existe deux façons de résoudre ce problème : - l'une utilisant les arbres de suffixes - l'autre utilisant la programmation dynamique.

La méthode mise en œuvre n'est pas importante. Sinon, il est important d'avoir une implémentation qui peut être utilisée pour un ensemble de chaînes de caractères et pas seulement pour deux chaînes de caractères.

Merci,

Answer 1

Ces fonctions jumelées permettent de trouver la plus longue chaîne commune dans un tableau arbitraire de chaînes de caractères :

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!'])

Il ne fait aucun doute que l'algorithme pourrait être amélioré et je n'ai pas été très exposé à Python, donc peut-être qu'il pourrait être plus efficace sur le plan syntaxique également, mais il devrait faire l'affaire.

EDIT : a intégré la deuxième fonction is_substr telle que démontrée par J.F. Sebastian. L'utilisation reste la même. Note : aucun changement dans 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

J'espère que cela vous aidera,

Jason.

Answer 2

Je préfère cela pour is_substr car je le trouve un peu plus lisible et intuitif :

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

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 4

# 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

Avis de non-responsabilité Cela ajoute très peu à la réponse de jtjacques. Cependant, j'espère que cela sera plus lisible. et plus rapide et Cela ne rentrait pas dans un commentaire, c'est pourquoi je le poste dans une réponse. Je ne suis pas satisfait de shortest_of pour être honnête.

Answer 5

Vous pouvez utiliser le module SuffixTree qui est une enveloppe basée sur une implémentation C ANSI des arbres de suffixes généralisés. Le module est facile à manipuler....

Jetez un coup d'oeil : ici