Längste gemeinsame Teilkette von mehr als zwei Strings - Python

Question

Ich bin für eine Python-Bibliothek der Suche nach der Suche nach der längsten gemeinsamen Unterkette von eine Menge von Strings . Es gibt zwei Möglichkeiten, dieses Problem zu lösen:

• mit Suffix Bäume
• mit dynamischer Programmierung.

Methode implementiert ist nicht wichtig. Es ist wichtig, kann es verwendet werden für eine Menge von Strings (nicht nur zwei Strings).

Answer 1

Diese gepaart Funktionen werden die längste gemeinsame Zeichenfolge in jeder beliebigen Array von Strings finden:

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

Kein Zweifel, der Algorithmus verbessert werden könnte, und ich habe nicht viel Kontakt mit Python hatte, vielleicht könnte es syntaktisch als auch effizienter sein, aber es sollte die Arbeit machen.

EDIT: , um die zweite Funktion in is_substr ausgekleideten wie von J.F. Sebastian demonstriert. Verbrauch bleibt gleich. . Hinweis: keine Änderung Algorithmus

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, das hilft,

Jason.

Answer 2

Ich ziehe dies für is_substr, wie ich es ein bisschen besser lesbar und intuitiv finden:

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

Dies kann kürzer gemacht werden:

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)

Set sind (wahrscheinlich) implementiert als Hash-Karten, die dies eine ineffiziente Bit macht. Wenn Sie (1) einen Satz Datentyp als Trie implementieren und (2) speichern nur die Postfix in der Trie und dann jeden Knoten zwingen, einen Endpunkt zu sein (diese wäre das Äquivalent alle Teil der Zugabe), dann wird in der Theorie würde ich denke, dieses Baby ist ziemlich Speicher effizient, vor allem, da Kreuzungen der Versuche sind super-einfach.

Dies ist jedoch kurz und vorzeitige Optimierung ist die Wurzel einer signifikanten Menge vergeudeter Zeit.

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

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

Hinweis Das fügt sehr wenig zu jtjacques' Antwort. Aber hoffentlich, soll dies besser lesbar sein und schneller und es nicht in einem Kommentar passen, also warum ich dies in einer Antwort bin Entsendung. Ich bin nicht zufrieden über shortest_of, ehrlich zu sein.

Answer 6

Sie könnten das Suffixbaum Modul verwenden, die ein Wrapper auf einer ANSI-C-Implementierung allgemeinen Suffix Bäume basierte. Das Modul ist einfach zu handhaben ....

Schauen Sie sich auf: hier

Answer 7

Wenn jemand sucht nach einer generalisierten Version, die auch eine Liste von Sequenzen von beliebigen Objekten annehmen kann:

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