Come si calcola la distanza di Levenshtein?

levenshtein.py

def build_matrix(a: str, b: str) -> list[list[int]]:
    """Costruisci la matrice di distanza date le stringhe a e b."""
    
    # Crea una matrice vuota di dimensioni (len(a) + 1) * (len(b) + 1)
    #     c o n o
    #   . . . . .
    # c . . . . .
    # o . . . . . 
    # s . . . . .
    # a . . . . .
    
    dim_x = len(a) + 1
    dim_y = len(b) + 1
    matrix = [[None for _ in dim_y] for _ in dim_x]
    
    # Imposta i valori nella prima riga e colonna ai valori della distanza dall'angolo in alto a sinistra
    #     c o n o
    #   0 1 2 3 4
    # c 1 . . . .
    # o 2 . . . . 
    # s 3 . . . .
    # a 4 . . . .
    
    for x in range(dim_x):
        matrix[x][0] = x
    for y in range(dim_y):
        matrix[0][y] = y
        
    # Itera su ogni cella rimasta libera per assegnarle un valore
    
    for x in range(dim_x - 1):
        for y in range(dim_y - 1):
            # Spostati all'inizio delle celle vuote
            x += 1
            y += 1
                
            # Definisci (per chiarezza) i costi di inserimento e rimozione
            cost_add = 1
            cost_rem = 1
                
            # Calcola il costo per effettuare una sostituzione in quella cella
            cost_sub = 0 if a[x] == b[y] else 1
            
            # Scegli l'operazione con il costo minore
            matrix[x][y] = min(
            
                # Inserimento
                d[x-1][y] + cost_add,
            
                # Rimozione
                d[x][y-1] + cost_rem,
                
                # Sostituzione
                d[x-1][y-1] + cost_sub,
                
            )

    # Restituisci il risultato
    #     c o n o
    #   0 1 2 3 4
    # c 1 0 1 2 3
    # o 2 1 0 1 2 
    # s 3 2 1 1 2
    # a 4 3 2 2 2
    
    return matrix
        
        
def find_distance(matrix: list[list[int]]) -> int:
    """Data una matrice di distanza, trova il valore della distanza di Levenshtein."""                                        
    
    dim_x = len(matrix)                                        
    dim_y = len(matrix[0])
    
    # È il valore in basso a destra!
    return matrix[dim_x][dim_y]