أفضل طريقة لتحديد ما إذا كان التسلسل موجودًا في تسلسل آخر في بايثون

Question

هذا تعميم لمشكلة "تحتوي السلسلة على سلسلة فرعية" على (المزيد) من الأنواع التعسفية.

بالنظر إلى تسلسل (مثل قائمة أو صف)، ما هي أفضل طريقة لتحديد ما إذا كان هناك تسلسل آخر بداخله؟على سبيل المكافأة، يجب أن يُرجع فهرس العنصر الذي يبدأ منه التسلسل التالي:

مثال للاستخدام (التسلسل في التسلسل):

>>> seq_in_seq([5,6],  [4,'a',3,5,6])
3
>>> seq_in_seq([5,7],  [4,'a',3,5,6])
-1 # or None, or whatever

حتى الآن، أعتمد فقط على القوة الغاشمة، وهي تبدو بطيئة وقبيحة وخرقاء.

Answer 1

وI الثانية خوارزمية كانوث-موريس-برات. بالمناسبة، مشكلتك (والحل KMP) هو بالضبط صفة 5.13 في بيثون كتاب الطبخ 2nd طبعة. يمكنك العثور على رمز ذات الصلة في http://code.activestate.com/recipes/117214/

ويجدها <م> جميع في المتتالية الصحيحة في تسلسل معين، ويجب أن تستخدم مكرر:

>>> for s in KnuthMorrisPratt([4,'a',3,5,6], [5,6]): print s
3
>>> for s in KnuthMorrisPratt([4,'a',3,5,6], [5,7]): print s
(nothing)

Answer 2

وفيما يلي O(n*m) نهج القوة الغاشمة (على غرار <لأ href = "https://stackoverflow.com/questions/425604/best-way-to-determine-if-a-sequence-is-in-another- تسلسل في بيثون # 425764 "> @ mcella في الإجابة ). قد يكون أسرع من تنفيذ خوارزمية كانوث-موريس-برات في O(n+m) بيثون نقية (انظر <لأ href = "https://stackoverflow.com/questions/425604/best-way-to-determine-if-a-sequence- هو-في آخر تسلسل في والثعبان # 425838 "> @ جريج ليند الإجابة ) ل <م> صغيرة تسلسل الإدخال.

#!/usr/bin/env python
def index(subseq, seq):
    """Return an index of `subseq`uence in the `seq`uence.

    Or `-1` if `subseq` is not a subsequence of the `seq`.

    The time complexity of the algorithm is O(n*m), where

        n, m = len(seq), len(subseq)

    >>> index([1,2], range(5))
    1
    >>> index(range(1, 6), range(5))
    -1
    >>> index(range(5), range(5))
    0
    >>> index([1,2], [0, 1, 0, 1, 2])
    3
    """
    i, n, m = -1, len(seq), len(subseq)
    try:
        while True:
            i = seq.index(subseq[0], i + 1, n - m + 1)
            if subseq == seq[i:i + m]:
               return i
    except ValueError:
        return -1

if __name__ == '__main__':
    import doctest; doctest.testmod()

وأتساءل كيف كبير هو صغيرة في هذه الحالة؟

Answer 3

ونفس الشيء كسلسلة مطابقة سيدي ... كانوث-موريس-برات سلسلة مطابقة

Answer 4

ونهج بسيط: تحويل إلى سلاسل والاعتماد على مطابقة السلسلة

مثال باستخدام قوائم الجمل:

 >>> f = ["foo", "bar", "baz"]
 >>> g = ["foo", "bar"]
 >>> ff = str(f).strip("[]")
 >>> gg = str(g).strip("[]")
 >>> gg in ff
 True

مثال باستخدام الصفوف من سلاسل:

>>> x = ("foo", "bar", "baz")
>>> y = ("bar", "baz")
>>> xx = str(x).strip("()")
>>> yy = str(y).strip("()")
>>> yy in xx
True

مثال باستخدام قوائم الأرقام:

>>> f = [1 , 2, 3, 4, 5, 6, 7]
>>> g = [4, 5, 6]
>>> ff = str(f).strip("[]")
>>> gg = str(g).strip("[]")
>>> gg in ff
True

Answer 5

>>> def seq_in_seq(subseq, seq):
...     while subseq[0] in seq:
...         index = seq.index(subseq[0])
...         if subseq == seq[index:index + len(subseq)]:
...             return index
...         else:
...             seq = seq[index + 1:]
...     else:
...         return -1
... 
>>> seq_in_seq([5,6], [4,'a',3,5,6])
3
>>> seq_in_seq([5,7], [4,'a',3,5,6])
-1

وآسف لأنني لست خبيرا الخوارزمية، انها مجرد أسرع شيء رأيي يمكن التفكير في الوقت الراهن، على الأقل أعتقد أنها تبدو جميلة (بالنسبة لي) وكان لي متعة الترميز ذلك. ؛ -)

وأغلب الظن انها نفس الشيء نهج القوة الغاشمة الخاص بك يقوم به.

Answer 6

ويمكن أن تكون القوة الغاشمة على ما يرام لأنماط الصغيرة.

لأكبر منها، والنظر في أهو-Corasick خوارزمية .

Answer 7

وهنا هو تنفيذ آخر KMP:

from itertools import tee

def seq_in_seq(seq1,seq2):
    '''
    Return the index where seq1 appears in seq2, or -1 if 
    seq1 is not in seq2, using the Knuth-Morris-Pratt algorithm

    based heavily on code by Neale Pickett <neale@woozle.org>
    found at:  woozle.org/~neale/src/python/kmp.py

    >>> seq_in_seq(range(3),range(5))
    0
    >>> seq_in_seq(range(3)[-1:],range(5))
    2
    >>>seq_in_seq(range(6),range(5))
    -1
    '''
    def compute_prefix_function(p):
        m = len(p)
        pi = [0] * m
        k = 0
        for q in xrange(1, m):
            while k > 0 and p[k] != p[q]:
                k = pi[k - 1]
            if p[k] == p[q]:
                k = k + 1
            pi[q] = k
        return pi

    t,p = list(tee(seq2)[0]), list(tee(seq1)[0])
    m,n = len(p),len(t)
    pi = compute_prefix_function(p)
    q = 0
    for i in range(n):
        while q > 0 and p[q] != t[i]:
            q = pi[q - 1]
        if p[q] == t[i]:
            q = q + 1
        if q == m:
            return i - m + 1
    return -1

Answer 8

لقد تأخرت قليلًا عن الحفلة، ولكن إليك شيئًا بسيطًا باستخدام الخيوط:

>>> def seq_in_seq(sub, full):
...     f = ''.join([repr(d) for d in full]).replace("'", "")
...     s = ''.join([repr(d) for d in sub]).replace("'", "")
...     #return f.find(s) #<-- not reliable for finding indices in all cases
...     return s in f
...
>>> seq_in_seq([5,6], [4,'a',3,5,6])
True
>>> seq_in_seq([5,7], [4,'a',3,5,6])
False
>>> seq_in_seq([4,'abc',33], [4,'abc',33,5,6])
True

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

Answer 9

وثمة نهج آخر، وذلك باستخدام مجموعات:

set([5,6])== set([5,6])&set([4,'a',3,5,6])
True