La plus longue chaîne commune de plus de deux chaînes - Python
-
04-10-2019 - |
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).
La solution
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.
Autres conseils
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
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.
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
# 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.
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!'])