Для дискретных последовательностей (строки символов, последовательности ДНК, ну или временные ряды после HIPPO(если кто то еще помнит, то первые посты в канале были посвещены как раз SSM и дискретизации рядов через HIPPO)) расстояние Левенштейна определяется как минимальное число операций вставки, удаления или замены символа, необходимых для преобразования одной последовательности в другую. Функция удовлетворяет всем аксиомам метрики и вычисляется динамическим программированием за O(|s| * |t|):

def levenshtein(s, t):

    m, n = len(s), len(t)

    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(m + 1):

        dp[i][0] = i

    for j in range(n + 1):

        dp[0][j] = j

    for i in range(1, m + 1):

        for j in range(1, n + 1):

            cost = 0 if s[i - 1] == t[j - 1] else 1

            dp[i][j] = min(

                dp[i - 1][j] + 1,

                dp[i][j - 1] + 1,

                dp[i - 1][j - 1] + cost,

            )

    return dp[m][n]

Варианты edit distance включают расстояние Дамерау-Левенштейна с дополнительной операцией транспозиции, расстояние Хэмминга для последовательностей одинаковой длины с разрешённой только операцией замены, и weighted edit distance с переменной стоимостью операций. Для биоинформатики применяется Needleman-Wunsch с матрицами замещения, отражающими биологическую вероятность мутации.

Edit distance применима в TDA для построения комплексов на пространстве последовательностей - например, для анализа разнообразия репертуара T-cell receptor или сравнения протеомов.

#TDA101