Самая длинная общая подстрока между двумя длинными списками

Question

У меня есть два очень длинных списка, и я хочу найти самую длинную общую подстроку для каждого элемента первого списка во втором списке.

Упрощенный пример

L1= ["a_b_c","d_e_f"] 
L2=["xx""xy_a","xy_b_c","z_d_e","zl_d","z_d_e_y"] 

Так что я хочу, чтобы найти лучший матч за "a_b_c" в L2 ("xy_b_c"), то лучший матч за "d_e_f" в L2 ("z_d_e_y") , Лучшее совпадение для меня - это строка с самыми длинными общими символами. В я смотрел на примерах для Левенштейн, который работает для небольших списков просто отлично (http://www.stavros.io/posts/finding-the-levenshtein-distance-in-python/), но мой список L2 имеет 163531 элементов и он не смог найти даже один матч за последние 15 минут ..

У меня нет CS-фона, может кто-нибудь указать мне на какой-то лучший алгоритм (или даже лучше, на его реализацию? :)) Спасибо тонну.

Текущий код (копируются от ссылки и кто-то еще из StackOverflow):

L1= ["a_b_c","d_e_f"] 
L2=["xx""xy_a","xy_b_c","z_d_e","zl_d","z_d_e_y"] 

def levenshtein_distance(first, second): 
    """Find the Levenshtein distance between two strings.""" 
    if len(first) > len(second): 
     first, second = second, first 
    if len(second) == 0: 
     return len(first) 
    first_length = len(first) + 1 
    second_length = len(second) + 1 
    distance_matrix = [[0] * second_length for x in range(first_length)] 
    for i in range(first_length): 
     distance_matrix[i][0] = i 
    for j in range(second_length): 
     distance_matrix[0][j]=j 
    for i in xrange(1, first_length): 
     for j in range(1, second_length): 
      deletion = distance_matrix[i-1][j] + 1 
      insertion = distance_matrix[i][j-1] + 1 
      substitution = distance_matrix[i-1][j-1] 
      if first[i-1] != second[j-1]: 
       substitution += 1 
      distance_matrix[i][j] = min(insertion, deletion, substitution) 
    return distance_matrix[first_length-1][second_length-1] 

for string in L1: 
    print sorted(L2,key = lambda x:levenshtein_distance(x,string))[0] 

Edit- просто нажмите Ctrl + C, и он дал мне неправильный (но близко) ответ через 15 минут. То только для первой строки и есть их много осталось ..

Answer 1

Используйте difflib модуль:

>>> from functools import partial 
>>> from difflib import SequenceMatcher 
def func(x, y): 
    s = SequenceMatcher(None, x, y) 
    return s.find_longest_match(0, len(x), 0, len(y)).size 
... 
for item in L1: 
    f = partial(func, item) 
    print max(L2, key=f) 
...  
xy_b_c 
z_d_e_y 

Answer 2

Вы также можете посмотреть на The Levenshtein Python C extension module. Если бы я тестировал его на случайной строке в вашем примере, он, по-видимому, был примерно в 150 раз быстрее, чем реализация python. И используйте max, как показано на рисунке Ashwini Chaudhary.