Celle riempite
Distanza di edit
Lettere mantenute

  • In riempimento
  • Letta
  • Risposta

Scopri di più sulla distanza di edit

Distanza di edit (distanza di Levenshtein)

Quante modifiche di una sola lettera trasformano kitten in sitting? Tre: sostituire k con s, sostituire e con i e aggiungere una g. Questo numero è la distanza di edit: così i correttori ortografici ordinano i suggerimenti e i biologi confrontano i geni. Scrivi due parole e guarda una tabella trovarla. Premi Avvia per guardare la tabella che si riempie, oppure Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi. Scrivi due parole: la prima scorre lungo il lato sinistro della tabella, la seconda lungo il lato superiore. Ogni cella contiene il numero minimo di modifiche che trasformano le lettere fino alla sua riga nelle lettere fino alla sua colonna. Alla fine le modifiche vengono rilette a partire dalla cella in basso a destra. Nuovo esempio sceglie un'altra coppia di parole. Con il riquadro selezionato, le frecce vanno avanti e indietro di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.

Come funziona

  1. Scrivi due parole: la prima scorre lungo il lato sinistro della tabella, la seconda lungo il lato superiore.
  2. Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi.
  3. Guarda ogni cella prendere il più economico dei suoi tre vicini, poi osserva le modifiche rilette in arancione.

Come funziona la tabella

Una cella contiene il numero minimo di modifiche che trasformano le lettere della prima parola fino alla sua riga nelle lettere della seconda parola fino alla sua colonna. La prima riga conta gli inserimenti, che costruiscono la seconda parola dal nulla, e la prima colonna conta le cancellazioni. Se le due lettere di una cella sono uguali, la cella copia quella in alto a sinistra: non serve nessuna modifica. Altrimenti vale uno in più del minimo dei tre vicini: in alto a sinistra per una sostituzione, sopra per una cancellazione e a sinistra per un inserimento.

Rileggere le modifiche

La cella in basso a destra è la distanza di edit. Partendo da lì, l'app trova da quale vicino viene il valore della cella e si sposta su di esso: in diagonale per una lettera mantenuta o sostituita, in alto per una cancellata, a sinistra per una inserita. Letti a partire dall'angolo in alto a sinistra, i passi formano una lista di modifiche più corta possibile, mostrata sotto la tabella: una lettera semplice viene mantenuta, k→s è una sostituzione, −e una cancellazione e +g un inserimento.

Domande frequenti

Che cos'è la distanza di Levenshtein?

È un altro nome di questa distanza di edit: il numero minimo di inserimenti, cancellazioni e sostituzioni di una sola lettera che trasformano una stringa in un'altra. Prende il nome da Vladimir Levenshtein, che la descrisse nel 1965.

Qual è la distanza di edit tra kitten e sitting?

3: sostituire k con s, sostituire e con i e inserire g alla fine. La tabella mostra che non esiste una lista di modifiche più corta.

Quanto è veloce l'algoritmo della distanza di edit?

Per parole di lunghezza m e n la tabella ha (m + 1)·(n + 1) celle, ognuna riempita in un passo, quindi richiede un tempo O(m·n). Se serve solo la distanza, bastano due righe della tabella.

Quali altre distanze di edit esistono?

La distanza di Damerau–Levenshtein conta come una sola modifica anche lo scambio di due lettere vicine, cosa adatta agli errori di battitura. La distanza di Hamming ammette solo sostituzioni e vale per stringhe della stessa lunghezza. La distanza LCS ammette solo inserimenti e cancellazioni.

Viene inviato qualcosa da qualche parte?

No. Tutto viene calcolato nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.

Pronto a provarlo?

Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.

Vai all'editor