Допустим, у меня есть 2 строки, которые очень похожи. Я хочу найти другую строку, близкую к s1 и s2 с точки зрения расстояния Левенштейна.

 import Levenshtein
s1 = 'aaabbbccc'
s2 = 'abacbbbccde'
dist = Levenshtein.distance(s1, s2)
print(dist)
mid_str = get_avg_string(s1, s2)
 

Какой может быть эффективная реализация функции:

 def get_avg_string(s1, s2):
    return ''
 

Мне нужно, чтобы эти переменные:

 sum_lev = Levenshtein.distance(s1, mid_str)   Levenshtein.distance(s2, mid_str)
diff_lev = abs(Levenshtein.distance(s1, mid_str) - Levenshtein.distance(s2, mid_str)
 

быть минимальным (я думаю sum_lev , будет равно dist и diff_lev <= 1 ).

Я боюсь, что то, о чем вы просите, невозможно, поскольку проблема NP-сложная. Я попытаюсь изложить несколько ключевых понятий, объясняющих, почему это так, но я бы посоветовал вам поискать центральные строки и строки Штайнера.

Предположим, что у вас есть набор строк с именем S. Оптимальная строка Штайнера — это строка, которая минимизирует сумму расстояний каждой строки в S до самой себя (также известная как ошибка консенсуса). Это соответствует первому свойству, которое вы вызвали sum_lev . Оптимальная строка Штайнера обычно неоднозначна и не является частью исходного набора S (но не обязательно должна быть).

Проблема, с которой вы сталкиваетесь, заключается в том, что не существует эффективного способа вычисления оптимальной строки Штайнера. Даже если вам удастся ограничить пространство поиска, у вас все равно будет экспоненциальное количество кандидатов. Следовательно, проблема NP-сложная.

Можно доказать, что S всегда содержит строку, которая является разумным приближением к оптимальной строке Штайнера. Поэтому, даже если вы обращаете внимание только на первое из ваших двух свойств, лучший вариант, который у вас есть, — просто выбрать одну из ваших исходных строк. Поскольку вы, по-видимому, имеете дело только с двумя строками, не должно иметь значения, какую из них вы выберете.

TL; DR

Подводя итог, вы имеете дело с NP-сложной проблемой, которая не может быть решена эффективно, а только приближена. Если вы имеете дело только с двумя строками, искомая строка может быть аппроксимирована одной из заданных строк. Мне жаль, что это, вероятно, не тот ответ, на который вы надеялись, но, надеюсь, он все же был несколько полезен.

Предположение

Итак, прежде всего, давайте предположим string1 , что (назовем это s1 ) — это до и string2 (назовем это s2 ) после преобразования. Таким образом, мы можем легко разделить операции добавления и удаления символов.

Пример

Давайте рассмотрим приведенный вами пример. Levenshtein.distance(s1='aaabbbccc', s2='abacbbbccde') Это означает, что мы задаем вопрос, сколько операций отделяет эти строки (сколько стоит мутировать одну в другую).

Матрица Левенштейна

Теперь, когда мы предполагаем s1 , что это начальная точка, давайте посмотрим, что дает нам алгоритм.
Мы можем вычислить это расстояние между s1 и s2 , и оно выдает целое значение 4
Оно исходит из последнего значения вычисленной матрицы Левенштейна, например:

Пройдитесь по матрице Левенштейна

Как мы можем видеть, есть места, где значение увеличивается и где оно остается неизменным.
Если мы перейдем к матрице из верхнего левого угла, мы должны прочитать ее как:

• переход вниз означает: добавление символа в s1 строку
• правильный путь означает: удаление символа из s1 строки
• движение по диагонали вниз вправо означает: замена символа

Наша цель — добраться до нижнего правого угла, а результирующее значение — это стоимость (или расстояние), которая с ним связана.

Изменение расстояния в матрице

Давайте посмотрим, как матрица изменит свои значения, когда мы изменим последнее значение, s1
поскольку мы видим, что предыдущее пересечение c x d изменилось на d x d , и теперь стоимость в этом месте не увеличивается, что приводит к уменьшению расстояния между этими строками.
Мы видим, что небольшие изменения в s1 приведут к изменению расстояния 1 , и если мы сравним оригинал s1 с измененным:

Это выглядит чертовски близко с точки зрения расстояния Левенштейна.

Заключение

Потенциально существует алгоритм для генерации довольно большого количества строк, похожих на s1 и s2 .
Он будет перебирать сгенерированную матрицу и изменять один символ в строке для генерации следующего решения.
Мы должны рассмотреть несколько изменений, внесенных в исходную матрицу. И затем для каждого нового решения мы потенциально хотим вычислить новую матрицу Левенштейна и использовать ее в качестве следующего источника для генерации решений.
И мы никогда не должны рассматривать только понижение этих значений, что привело бы к созданию только части потенциальных решений.

Важно учитывать одну вещь. С точки зрения расстояния Левенштейна не имеет значения, сравниваем ли мы символ a с b или a с c , важно только то, что «Это один и тот же символ?» если нет, нам не важно его значение.

Небольшое расширение ответа @Matze — когда вам нужно решить NP-сложную задачу, вы можете использовать генетический алгоритм, чтобы найти какое-то решение, которое может быть лучше, чем просто взять одну из строк за конечное время (нет гарантий, что это будет лучше или даже лучше, чем одна из исходных строк)

Это не решение, но с чего-то начать; немедленным улучшением будет функция, eq_len_strings которая выравнивает строки вправо; также вы можете использовать подстроки s1 on s2 , чтобы создать свою первую среднюю строку (поскольку это помогает уменьшить расстояние Левенштейна), а затем просто _ заполнить любым символомв вашем алфавите так search_mid_string же.

Еще одно улучшение заключается в том, чтобы избегать (вопреки тому, что я делаю) заполнения всех пробелов ( _ ), возможно, добавляя пустую строку в ваш алфавит или учитывая разницу в длине для обеих строк.

 import Levenshtein

def eq_len_strings(s1, s2):
    if len(s1) < len(s2):
        s1 = s1.ljust(len(s1) len(s2)-len(s1), '_')
    elif len(s1) > len(s2):
        s2 = s2.ljust(len(s2) len(s1)-len(s2), '_')
    return s1, s2

def keep_eq_chars(s1, s2):
    s = ''
    for char1, char2 in zip(s1, s2):
        if char1 == '_' or char2 == '_' or char1 != char2:
            s  = '_'
        else:
            s  = char1
    return s

def search_mid_string(s1, s2):
    alph = set(list(s1 s2))
    s1e, s2e = eq_len_strings(s1, s2)
    # start string
    s_mid = list(keep_eq_chars(s1e, s2e))
    
    alternate = 0
    for i in range(len(s_mid)):
        char1 = s1[i] if i < len(s1)-1 else '_'
        char2 = s2[i] if i < len(s2)-1 else '_'
        if s_mid[i] == '_':
            if alternate == 0 and char1 != '_':
                s_mid[i] = char1
                alternate = 1
            elif alternate == 1 and char2 != '_':
                s_mid[i] = char2
                alternate = 0
            else:
                s_mid[i] = ''
    s1_to_s2_dist = Levenshtein.distance(s1, s2)
    s1_to_mid_dist = Levenshtein.distance(s1, ''.join(s_mid))
    s2_to_mid_dist = Levenshtein.distance(s2, ''.join(s_mid))
    ans = {
        's1_to_s2_dist': s1_to_s2_dist,
        's1_to_mid_dist': s1_to_mid_dist,
        's2_to_mid_dist': s2_to_mid_dist,
        's_mid': ''.join(s_mid)
    }
    return ans
 

С заданными строками:

 s1 = 'aaabbbccc'
s2 = 'abacbbbccde'

search_mid_string(s1, s2)

// Output
>{'s1_to_s2_dist': 4,
> 's1_to_mid_dist': 2,
> 's2_to_mid_dist': 3,
> 's_mid': 'aaacbbcccd'}
 

Это не решение, а очень простая идея поиска строки, близкой к двум строкам:

 import Levenshtein

s1 = 'aaabbbccc'
s2 = 'abacbbbccde'

dist = Levenshtein.distance(s1, s2)
print(dist)

def get_avg_string(s1, s2):
    s2, s1 = sorted([s1, s2], key=len)
    s3 = ''.join(a if i amp; 1 else b for i, (a, b) in enumerate(zip(s1, s2)))
    return s3

mid_str = get_avg_string(s1, s2)

print(Levenshtein.distance(s1, mid_str))
print(Levenshtein.distance(s2, mid_str))
 

Вывод:

 4
2
3
 

Объяснение функции

 def get_avg_string(s1, s2):
    s2, s1 = sorted([s1, s2], key=len)
    s3 = ''.join(a if i amp; 1 else b for i, (a, b) in enumerate(zip(s1, s2)))
    return s3
 

Цикл

 for i, (a, b) in enumerate(zip(s1, s2))
 

будет выполняться итерация по строкам s1 и s2 параллельно с использованием zip() метода вместе с индексом каждой итерации с enumerate() помощью метода.

Условие

 a if i amp; 1 else b
 

возьмет часть из s1 , a , если индекс нечетный (если amp; 1 возвращает 1 , а не 0 ), иначе часть из s2 , b .

Я использовал

 s2, s1 = sorted([s1, s2], key=len)
 

чтобы сделать строку ниже, возьмите первый символ из самой длинной строки.

Вот код, который возвращает список всех строк между s1 и s2. Таким образом, вы можете выбрать ту, что посередине.

 def get_all_avg_strings(s1, s2):
    import Levenshtein
    dist = Levenshtein.distance(s1, s2)
    s1_new = s1
    intermediate_strings = [s1_new]
    for i in range(dist):
        e = Levenshtein.editops(s1_new, s2)
        s1_new = Levenshtein.apply_edit(e[:1], s1_new, s2)
        intermediate_strings.append(s1_new)
    check = Levenshtein.distance(s2, s1_new)
    if check != 0:
        print('Some error here!')
        exit()
    return intermediate_strings[1:-1]
 

Затем вы можете создать запрошенную функцию как:

 def get_avg_string(s1, s2):
    avg = get_all_avg_strings(s1, s2)
    if len(avg) > 0:
        s = avg[len(avg) // 2]
    else:
        s = s1
    return s