<jupyter_start><jupyter_text>EDIT DISTANCE**Problema:** date due stringhe $a$ e $b$, individuare una strategia per calcolare il numero minimo di operazioni necessario a trasformare $a$ in $b$, avendo come possibili operazioni l'inserimento di un carattere, la cancellazione di un carattere, e la sostituzione di un carattere.<jupyter_code>a = 'ceni'
b = 'cane'<jupyter_output><empty_output><jupyter_text>SOLUZIONE 1- Se $a$ è nulla allora occorre aggiungere un numero di caratteri pari alla lunghezza di $b$- Se $b$ è nulla allora occorre aggiungere un numero di caratteri pari alla lunghezza di $a$- Se l'ultimo carattere di $a$ e $b$ è lo stesso, allora il costo è quello che calcoliamo per le sottostringhe $a_{-1}$ e $b_{-1}$- Se infine gli ultimi caratteri di $a$ e $b$ sono diversi, occorre fare un'operazione per l'ultimo carattere più il costo inferiore per le tre coppie di sottostringhe da cui è possibile arrivare all'ultimo carattere<jupyter_code>def edist(a, b, cost=0, depth=0): 
    # print(a, b, cost, depth)
    if len(a) == 0:
        return len(b)
    elif len(b) == 0:
        return len(a)
    elif a[-1] == b[-1]:
        return edist(a[:-1], b[:-1], cost, depth = depth + 1)
    else:
        return 1 + min([
            edist(a[:-1], b, cost + 1, depth = depth + 1),
            edist(a, b[:-1], cost + 1, depth = depth + 1),
            edist(a[:-1], b[:-1], cost + 1, depth = depth + 1)
        ])
edist('casa', 'pasta')<jupyter_output><empty_output><jupyter_text>SOLUZIONE 2    casto    012345    c1    a2    s3    a4$E(i, j) = \min \{E(i-1, j) + 1; E(i, j-1) + 1; E(i-1,i-1) + k\}$, where $k = 1$ if $s_1(i) \neq s_2(j), k = 0$ otherwise<jupyter_code>import numpy as np
def nf(a, b):
    m = np.zeros((len(a) + 1, len(b) + 1))
    m[0,:] = list(range(len(b) + 1))
    m[:,0] = list(range(len(a) + 1))
    for row in range(1, len(a) + 1):
        for col in range(1, len(b) + 1):
            if a[row-1] != b[col-1]:
                k = min([m[row-1,col] + 1, m[row,col-1] + 1, m[row-1,col-1] + 1])
            else:
                k = min([m[row-1,col] + 1, m[row,col-1] + 1, m[row-1,col-1]])
            m[row,col] = k
    return m
m = nf('alfia', 'fiala')
m
m<jupyter_output><empty_output><jupyter_text>Esercizio - Implementare una variante di `nf` in cui la sostituzione di un carattere costa 2 invece di 1- Trovare il percorso di costo inferiore per andare dalla posizione `0,0` alla posizione `-1,-1`<jupyter_code>def ddist(a, b):
    m = np.zeros((len(a)+1, len(b)+1))
    for v in range(len(b) + 1):
        m[0][v] = v
    for v in range(len(a) + 1):
        m[v][0] = v
    return m
x = ddist('casa', 'casto')
import numpy as np
def D(a, b):
    row = range(0, len(b)+1)
    col = range(0, len(a)+1)
    m = np.zeros((len(a)+1, len(b)+1))
    m[0,:] = row
    m[:,0] = col
    for i, x in enumerate(a):
        iM = i + 1
        for j, y in enumerate(b):
            jM = j + 1 
            if x == y:
                cost = 0
            else:
                cost = 1
            cost += min([
                m[iM-1,jM-1], 
                m[iM,jM-1]+(1-cost),
                m[iM-1,jM]+(1-cost),
            ])
            m[iM,jM] = cost
    return m
r = D('casa', 'casto')
r<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.16179637034758537, 'fraction_numerical': 0.030452168563518917, 'mean_word_length': 2.463258785942492, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 17, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '480063', 'license': 'MIT', 'n_tokens_mistral': 1374, 'n_tokens_neox': 1331, 'n_words': 385, 'path': 'edit_distance.ipynb', 'repo_name': 'layachisara/mastercobra', 'size': '3251'}