Text alignment: extracting matching sequence using python

Question

My goal is to extract the aligned matching sequence in two text passages. Next are my texts:

txt1='the heavy lorry crashed into the building at midnight'
txt2='what a heavy lorry it is that crashed into the building'

Expected output:

'heavy lorry'
'crashed into the building'

My attempt:

def sequ(s1,s2):
    _split1=s1.split()
    _split2=s2.split()
    _match=''.join(list(set(_split1) & set(_split2)))
    return _match

print sequ(txt1, txt2)

Result: heavybuildingintocrashedthelorry

......distorted result.

Any suggestions as to how to arrive at the expected result? Thanks.

Answer 1

difflib.SequenceMatcher.get_matching_blocks does exactly what you want.

import difflib

def sequ(s1, s2):
    words1 = s1.split()
    words2 = s2.split()
    matcher = difflib.SequenceMatcher(a=words1, b=words2)
    for block in matcher.get_matching_blocks():
        if block.size == 0:
            continue
        yield ' '.join(words1[block.a:block.a+block.size])

txt1 = 'the heavy lorry crashed into the building at midnight'
txt2 = 'what a heavy lorry it is that crashed into the building'
print list(sequ(txt1, txt2))

output:

['heavy lorry', 'crashed into the building']

Answer 2

txt1='the heavy lorry crashed into the building at midnight'
txt2='what a heavy lorry it is that crashed into the building'

s1, s2 = txt1.split(), txt2.split()
l1, l2 = len(s1), len(s2)
set1 = {" ".join(s1[j:j+i]) for i in range(1,l1+1) for j in range(l1+1-i)}
set2 = {" ".join(s2[j:j+i]) for i in range(1,l2+1) for j in range(l2+1-i)}
r = sorted(set1.intersection(set2), key = lambda x: len(x.split()))
rs = [j for k,j in enumerate(r) if all(j not in r[i] for i in range(k+1,len(r)))]
print rs
# ['heavy lorry', 'crashed into the building']