L'algoritmo Levenshtein, comunemente indicato come modificare la distanza, è il numero minimo di operazioni di modifica necessari per trasformare una stringa di dati, la stringa di origine, in un altro, la stringa di destinazione. Sequenze di lettere o numeri comprendono stringhe di dati. Validi operazioni di modifica includono la sostituzione, inserimento o la cancellazione. Programmi come strumenti di controllo ortografico e correzione automatica utilizzano questo algoritmo nel loro funzionamento. Mentre il sistema algoritmo utilizzato dai computer e telefoni intelligenti appare scoraggiante per comprendere il processo di base di definire una distanza di modifica è relativamente semplice.

istruzione

1 Scrivere o digitare le due stringhe in una pagina così la stringa fonti è allineato direttamente sopra la stringa di destinazione. Per esempio:

cat (stringa di origine)
destino (stringa di destinazione)

2 Identificare i punti di dati in cui una stringa differisce dall'altro. Per esempio:

Cat (stringa di origine)
Fate (stringa di destinazione)

Le lettere differire nel primo posto (C e F), e la stringa di destinazione ha un punto di dati supplementare (E).

3 Applicare il minor numero di operazioni di modifica (inserimento, cancellazione, sostituzione) possibili per cambiare la stringa di origine per la stringa di destinazione. Contare le modifiche. Per esempio:

Cat -> sostituto F per C ed inserire E -> FATE

Il cambiamento richiede due operazioni di modifica, una sostituzione e un inserimento, e non può essere completata in meno. Pertanto, la distanza di montaggio tra "gatto" e "destino" è due.