Longest common substring approach using suffix arrays I am trying to speed up a function to return the longest common substring.

The requirements:


The function takes two strings of arbitrary length (although on average they will be less than 50 chars each)
If two subsequences of the same length exist it can return either
Speed is the primary concern


This is what I have and it works according to my tests:

from os.path import commonprefix

class LongestCommonSubstr(object):


    def __init__(self, lstring, rstring):
        self.lstring = lstring+'0'
        self.rstring = rstring+'1'
        self._suffix_str_array = sorted(self._get_suffix_str(self.lstring) 
                                    + self._get_suffix_str(self.rstring))
        self.longest_common_substr = self._get_lcsubstr()

    @staticmethod
    def _get_suffix_str(string):

        return [string[i:] for i in range(len(string))]

    def _get_lcsubstr(self):

        try:
            substr_len =0
            max_len = 0
            lcs = None
            for i,n in enumerate(self._suffix_str_array):
                if n[-1] != self._suffix_str_array[i+1][-1]:
                    substr = commonprefix([n,self._suffix_str_array[i+1]])
                    substr_len = len(substr)
                    if substr_len &gt; max_len:
                        max_len = substr_len
                        lcs = substr

        except IndexError:
            pass
            return lcs


Can the code be made faster in pure Python? Is there a better option to differentiate the input strings when made into one sorted list than concatenating an ID to them?
OK then: since your concern is speed, let's track our progress with actual timing data. The first step is to run the code through the Python profiler. With the addition of a bit of driver code that just calls LongestCommonSubstr().longest_common_substr 10000 times, I get the following results:

$ python3.4 -m profile lcs_profile.py abcdeffghiklnopqr bdefghijklmnopmnop
         1130008 function calls in 3.083 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 :0(__build_class__)
        1    0.000    0.000    3.082    3.082 :0(exec)
        1    0.000    0.000    0.000    0.000 :0(hasattr)
   280000    0.257    0.000    0.257    0.000 :0(len)
   260000    0.330    0.000    0.330    0.000 :0(max)
   260000    0.350    0.000    0.350    0.000 :0(min)
        1    0.000    0.000    0.000    0.000 :0(setprofile)
    10000    0.042    0.000    0.042    0.000 :0(sorted)
        1    0.000    0.000    0.000    0.000 &lt;frozen importlib._bootstrap&gt;:2264(_handle_fromlist)
   260000    1.067    0.000    1.746    0.000 genericpath.py:69(commonprefix)
        1    0.022    0.022    3.082    3.082 lcs_profile.py:1(&lt;module&gt;)
    20000    0.069    0.000    0.157    0.000 lcs_profile.py:11(_get_suffix_str)
    20000    0.071    0.000    0.071    0.000 lcs_profile.py:13(&lt;listcomp&gt;)
    10000    0.807    0.000    2.794    0.000 lcs_profile.py:15(_get_lcsubstr)
        1    0.000    0.000    0.000    0.000 lcs_profile.py:3(LongestCommonSubstr)
    10000    0.067    0.000    3.060    0.000 lcs_profile.py:4(__init__)
        1    0.000    0.000    3.083    3.083 profile:0(&lt;code object &lt;module&gt; at 0x10996f030, file "lcs_profile.py", line 1&gt;)
        0    0.000             0.000          profile:0(profiler)


The most important column is the second one, tottime, marking the total amount of time consumed by each function (but not the functions it calls). The largest entries in that column are for the commonprefix function and the _get_lc_substr function, so those are the spots you should focus on optimizing.

To keep track of our progress, I coupled your class with the following driver program which prints the execution time for 10000 runs:

def lcs_longest_match(a, b):
    return LongestCommonSubstr(a, b).longest_common_substr
if __name__ == '__main__':
    import timeit, sys
    print('lcs    ', timeit.timeit('lcs_longest_match(sys.argv[1], sys.argv[2])',
                                   setup='from __main__ import lcs_longest_match',
                                   number=10000))


(this is for Python 3). A first run on my computer gives

$ python3.4 lcs.py abcdeffghiklnopqr bdefghijklmnopmnop
lcs     0.49046793299203273


I'll start with _get_lc_substr, since you wrote that code and it'll be easier to work through. The algorithm you use is to go through each pair of consecutive strings in the sorted suffix array, find the common prefix, and save that prefix only if it's longer than any common prefix already found. I can suggest a few improvements:


Iterating over pairs of consecutive elements is a common task that has a fairly standard recipe, pairwise(iterable), given in the documentation for the itertools module. You can use the implementation from the more-itertools package if you want. This also lets you get rid of the try/except block (which probably didn't affect runtime much, but it helps code clarity).
Python has a built-in function, max, to find the maximum value of an iterable. If you use it, then the nuts and bolts of the loop as well as the compare-and-store-if-greater process get handled internally by the interpreter, which should be faster than doing them manually in pure Python.
Repeatedly accessing an attribute of an object, namely the method self._suffix_str_array, is slower than accessing it once and storing it locally as a new variable.


Let's check the effect of these changes on the runtime of the driver program:

lcs     0.49046793299203273
optlcs1 0.4739605739887338
optlcs2 0.4895538759883493
optlcs3 0.4828952929965453


Not much of a change. Actually, using max is slower here, so let's discard that change.

Time now to take a closer look at commonprefix.


If you look at the source code of this function,

def commonprefix(m):
    "Given a list of pathnames, returns the longest common leading component"
    if not m: return ''
    s1 = min(m)
    s2 = max(m)
    for i, c in enumerate(s1):
        if c != s2[i]:
            return s1[:i]
    return s1


you see that it goes through some preliminary steps relating to the fact that it needs to handle a list of potentially several paths. You only ever have two strings to compare, so you can skip that - and in fact, if you look back at the profiling data, you'll see that these calls to max and min do take up a significant amount of time. Therefore, it makes sense to implement your own version of commonprefix without the max and min calls.


This makes a big difference in the runtime, cutting it down by over 30%:

lcs     0.49046793299203273
optlcs3 0.4828952929965453
optlcs4 0.3215277789859101



If you think about it, you don't even really need the common prefix itself, except for the one string you actually return from _get_lcsubstr. You only need its length, so you can decide which substring is the longest. So instead of using a function that finds the full common prefix, just write one that will give you its length. You store the length, along with one of the strings, and at the end of _get_lcsubstr, use the length to trim the stored string.

def _get_lcsubstr(self):
    # initialize
    for s1, s2 in mt.pairwise(suffix_str_array):
        if s1[-1] != s2[-1]:
            substr_len = get_common_prefix_length(s1, s2)
            if substr_len &gt; max_len:
                max_len = substr_len
                max_substr = s1
    return max_substr[:max_len]



This shaves another few percent off the runtime:

lcs     0.49046793299203273
optlcs4 0.3215277789859101
optlcs5 0.30241094100347254



If it's faster to avoid computing a substring in your commonprefix replacement, you might think of doing the same thing when you're finding the suffixes in the first place. In other words, instead of calculating all the suffixes of a string in _get_suffix_str, just make a list of (index, which_string) tuples to represent the suffixes. Then whenever you need to actually compare two suffixes, instead of taking a substring of the original string, you just start comparing characters at the required indices.

There are two problems with this in practice: first, Python isn't well suited to iterating from an arbitrary point in the middle of a string. In a language like C, where strings are character pointers, this would work out quite well, because you can jump into the middle of the string by advancing a pointer. But in Python, iterating from the middle of a string requires you to either start from the beginning and just skip the first several characters, or bypass the whole iteration mechanism and use a for loop with an integer index to access characters inside the string by their indices (which typically involves more Python code that is relatively inefficient). And besides, the other reason is you need to create the substrings anyway to sort them. If you try to do it so that you use the substrings as comparison keys without actually storing them, the program spends a lot of time converting between a substring and its index.


All told, the changes you need to make to the code to use indices everywhere wind up hurting, not helping. Here's the timing result:

lcs     0.49046793299203273
optlcs5 0.30241094100347254
optlcs6 0.3683815289987251


At this point, you can spend a lot of time making little tweaks to try to squeeze some extra performance out of the program, but I don't think there are any major performance gains left. It's already something like 40% faster than the original, which is not bad.

Of course, as dawg wrote in a comment, you can accomplish this task using Python's standard module difflib.

def difflib_longest_match(a, b):
    i, j, k = difflib.SequenceMatcher(a=a, b=b
        ).find_longest_match(0, len(a), 0, len(b))
    return a[i:i+k]


I have no idea what's in the difflib code (well, I could look, but I'll leave that as an exercise), but it's clearly heavily optimized for this kind of task. It's another 25% faster than my best version of your program:

lcs     0.49046793299203273
optlcs5 0.30241094100347254
difflib 0.2154458940058248


So if you really want to do this not for educational purposes, just use difflib.



Here is the content of the test script I used.

import difflib
import itertools as it
import more_itertools as mt
from os.path import commonprefix

class LongestCommonSubstr(object):
    def __init__(self, lstring, rstring):
        self.lstring = lstring+'0'
        self.rstring = rstring+'1'
        self._suffix_str_array = sorted(self._get_suffix_str(self.lstring) 
                                    + self._get_suffix_str(self.rstring))
        self.longest_common_substr = self._get_lcsubstr()

    @staticmethod
    def _get_suffix_str(string):
        return [string[i:] for i in range(len(string))]

    def _get_lcsubstr(self):
        try:
            substr_len =0
            max_len = 0
            lcs = None
            for i,n in enumerate(self._suffix_str_array):
                if n[-1] != self._suffix_str_array[i+1][-1]:
                    substr = commonprefix([n,self._suffix_str_array[i+1]])
                    substr_len = len(substr)
                    if substr_len &gt; max_len:
                        max_len = substr_len
                        lcs = substr

        except IndexError:
            pass
        return lcs

class OptimizedLongestCommonSubstr1(object):
    def __init__(self, lstring, rstring):
        self.lstring = lstring+'0'
        self.rstring = rstring+'1'
        self._suffix_str_array = sorted(self._get_suffix_str(self.lstring) 
                                    + self._get_suffix_str(self.rstring))
        self.longest_common_substr = self._get_lcsubstr()

    @staticmethod
    def _get_suffix_str(string):
        return [string[i:] for i in range(len(string))]

    def _get_lcsubstr(self):
        substr_len =0
        max_len = 0
        lcs = None
        for s1, s2 in mt.pairwise(self._suffix_str_array):
            if s1[-1] != s2[-1]:
                substr = commonprefix([s1,s2])
                substr_len = len(substr)
                if substr_len &gt; max_len:
                    max_len = substr_len
                    lcs = substr
        return lcs

class OptimizedLongestCommonSubstr2(object):
    def __init__(self, lstring, rstring):
        self.lstring = lstring+'0'
        self.rstring = rstring+'1'
        self._suffix_str_array = sorted(self._get_suffix_str(self.lstring) 
                                    + self._get_suffix_str(self.rstring))
        self.longest_common_substr = self._get_lcsubstr()

    @staticmethod
    def _get_suffix_str(string):
        return [string[i:] for i in range(len(string))]

    def _get_lcsubstr(self):
        return max((commonprefix([s1,s2]) for s1, s2 in mt.pairwise(self._suffix_str_array) if s1[-1] != s2[-1]), key=len)

class OptimizedLongestCommonSubstr3(object):
    def __init__(self, lstring, rstring):
        self.lstring = lstring+'0'
        self.rstring = rstring+'1'
        self._suffix_str_array = sorted(self._get_suffix_str(self.lstring) 
                                    + self._get_suffix_str(self.rstring))
        self.longest_common_substr = self._get_lcsubstr()

    @staticmethod
    def _get_suffix_str(string):
        return [string[i:] for i in range(len(string))]

    def _get_lcsubstr(self):
        s_array = self._suffix_str_array
        return max((commonprefix([s1,s2]) for s1, s2 in mt.pairwise(s_array) if s1[-1] != s2[-1]), key=len)

class OptimizedLongestCommonSubstr4(object):
    def __init__(self, lstring, rstring):
        self.lstring = lstring+'0'
        self.rstring = rstring+'1'
        self._suffix_str_array = sorted(self._get_suffix_str(self.lstring) 
                                    + self._get_suffix_str(self.rstring))
        self.longest_common_substr = self._get_lcsubstr()

    @staticmethod
    def _get_suffix_str(string):
        return [string[i:] for i in range(len(string))]
    @staticmethod
    def _get_common_prefix(s1, s2):
        for i, c in enumerate(s1):
            if c != s2[i]:
                return s1[:i]
        return s1

    def _get_lcsubstr(self):
        s_array = self._suffix_str_array
        gcp = self._get_common_prefix
        substr_len =0
        max_len = 0
        lcs = None
        for s1, s2 in mt.pairwise(s_array):
            if s1[-1] != s2[-1]:
                substr = gcp(s1, s2)
                substr_len = len(substr)
                if substr_len &gt; max_len:
                    max_len = substr_len
                    lcs = substr
        return lcs


class OptimizedLongestCommonSubstr5(object):
    def __init__(self, lstring, rstring):
        self.lstring = lstring+'0'
        self.rstring = rstring+'1'
        self._suffix_str_array = sorted(self._get_suffix_str(self.lstring) 
                                    + self._get_suffix_str(self.rstring))
        self.longest_common_substr = self._get_lcsubstr()

    @staticmethod
    def _get_suffix_str(string):
        return [string[i:] for i in range(len(string))]
    @staticmethod
    def _get_common_prefix_length(s1, s2):
        for i, c in enumerate(s1):
            if c != s2[i]:
                return i
        return len(s1)

    def _get_lcsubstr(self):
        s_array = self._suffix_str_array
        gcpl = self._get_common_prefix_length
        max_len = 0
        max_substr = ''
        for s1, s2 in mt.pairwise(s_array):
            if s1[-1] != s2[-1]:
                substr_len = gcpl(s1, s2)
                if substr_len &gt; max_len:
                    max_len = substr_len
                    max_substr = s1
        return max_substr[:max_len]

class OptimizedLongestCommonSubstr6(object):
    def __init__(self, lstring, rstring):
        self.lstring = lstring
        self.rstring = rstring
        self._suffix_str_array = sorted(
            [(i, True) for i, _ in enumerate(lstring)]
            + [(i, False) for i, _ in enumerate(rstring)],
            key=lambda t: (lstring if t[1] else rstring)[t[0]:])
        self.longest_common_substr = self._get_lcsubstr()

    @staticmethod
    def _get_common_prefix_length(s1, start1, s2, start2):
        for i, c in enumerate(it.islice(s1, start1, None)):
            if c != s2[i + start2]:
                return i
        return i

    def _get_lcsubstr(self):
        s_array = self._suffix_str_array
        gcpl = self._get_common_prefix_length
        max_len = 0
        max_start = 0
        max_substr = ''
        for (i1, b1), (i2, b2) in mt.pairwise(s_array):
            if b1 != b2:
                if b1:
                    s1 = self.lstring
                    s2 = self.rstring
                else:
                    s1 = self.rstring
                    s2 = self.lstring
                substr_len = gcpl(s1, i1, s2, i2)
                if substr_len &gt; max_len:
                    max_len = substr_len
                    max_start = i1
                    max_substr = s1
        return max_substr[max_start:max_start+max_len]

def lcs_longest_match(a, b):
    return LongestCommonSubstr(a, b).longest_common_substr

for n in it.count(1):
    if 'OptimizedLongestCommonSubstr{}'.format(n) in globals():
        exec('''def optimized_lcs_longest_match_{}(a, b):
    return OptimizedLongestCommonSubstr{}(a, b).longest_common_substr
'''.format(n, n))
    else:
        break

def optimized_lcs_longest_match(a, b):
    return OptimizedLongestCommonSubstr(a, b).longest_common_substr

def difflib_longest_match(a, b):
    i, j, k = difflib.SequenceMatcher(a=a, b=b).find_longest_match(0, len(a), 0, len(b))
    return a[i:i+k]

if __name__ == '__main__':
    import timeit, sys
    n_runs = 10000
    print('lcs    ', timeit.timeit('lcs_longest_match(sys.argv[1], sys.argv[2])', setup='from __main__ import lcs_longest_match', number=n_runs))
    for k in range(1, n):
        print('optlcs{}'.format(k), timeit.timeit(
            'optimized_lcs_longest_match_{}(sys.argv[1], sys.argv[2])'.format(k),
            setup='from __main__ import optimized_lcs_longest_match_{}'.format(k),
            number=n_runs))
    print('difflib', timeit.timeit('difflib_longest_match(sys.argv[1], sys.argv[2])', setup='from __main__ import difflib_longest_match', number=n_runs))

    print('control results:', difflib_longest_match(sys.argv[1], sys.argv[2]))    
    for k in range(1, n):
        print('test results {}: '.format(k), eval('optimized_lcs_longest_match_{}(sys.argv[1], sys.argv[2])'.format(k)))