أطول فرعية شائعة من أكثر من سلسلتين - بيثون

Question

أنا أبحث عن مكتبة Python للعثور على أطول سلسلة فرعية مشتركة من مجموعة من الأوتار. هناك طريقتان لحل هذه المشكلة :

• باستخدام أشجار لاحقة
• باستخدام البرمجة الديناميكية.

الطريقة التي تم تنفيذها ليست مهمة. من المهم استخدامه مجموعة من الأوتار (ليس فقط سلسلتين).

Answer 1

ستجد هذه الوظائف المقترنة أطول سلسلة مشتركة في أي مجموعة تعسفية من الأوتار:

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

مما لا شك فيه أنه يمكن تحسين الخوارزمية ولم يكن لدي الكثير من التعرض للبيثون ، لذلك ربما يكون أكثر كفاءة أيضًا ، ولكن يجب أن تقوم بهذه المهمة.

تعديل: تصطف في وظيفة IS_SUBSTR الثانية كما يتضح من JF Sebastian. الاستخدام لا يزال كما هو. ملاحظة: لا تغيير إلى الخوارزمية.

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

أتمنى أن يساعدك هذا،

جيسون.

Answer 2

أنا أفضل هذا ل is_substr, ، كما أجدها أكثر قابلية للقراءة وبديهية:

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 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)

يتم تنفيذ المجموعة (ربما) كخرائط تجزئة ، مما يجعل هذا غير فعال بعض الشيء. إذا قمت (1) بتطبيق نوع البيانات المحدد كـ trie و (2) ، فما عليك سوى تخزين الإثارات في trie ثم أجبرت كل عقدة على أن تكون نقطة نهاية (سيكون هذا مكافئًا لإضافة جميع السلاسل الفرعية) ، ثم من الناحية النظرية أعتقد هذا الطفل فعال في الذاكرة ، خاصة وأن تقاطعات المحاولات سهلة للغاية.

ومع ذلك ، فإن هذا التحسين قصير الأوان هو جذر كمية كبيرة من الوقت الضائع.

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

تنصل هذا يضيف القليل جدا إلى إجابة jtjacques. ومع ذلك ، نأمل أن يكون هذا أكثر قابلية للقراءة و أسرع و لم يتناسب مع تعليق ، وبالتالي لماذا أقوم بنشر هذا في إجابة. أنا لست راضيًا shortest_of, ، صدقا.

Answer 6

يمكنك استخدام وحدة Lavorixtree التي هي غلاف يعتمد على تنفيذ ANSI C لأشجار اللاحقة المعممة. الوحدة النمطية سهلة التعامل ...

ألق نظرة على: هنا

Answer 7

إذا كان شخص ما يبحث عن نسخة معممة يمكنها أيضًا أخذ قائمة بتسلسلات الكائنات التعسفية:

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