Hvordan Definer Rediger avstanden mellom to strenger

Den Levenshtein algoritme, ofte referert til som redigere avstand, er det minste antall redigere operasjoner for å forvandle en rekke data, kildestreng, inn i en annen, målet streng. Sekvenser av bokstaver eller tall omfatter strenger av data. Gyldige redigere virksomhet omfatter substitusjon, innsetting eller sletting. Programmer som stavekontroll og autokorrekturverktøy utnytte denne algoritmen i sin drift. Mens algoritmen som brukes av datamaskiner og smarttelefoner ser skremmende å forstå den grunnleggende prosessen med å definere en endring avstanden er relativt enkel.

Bruksanvisning

1 Skriv eller skriv dine to strenger på en side slik at kilder strengen er justert rett over målet streng. For eksempel:

cat (kilde streng)
skjebne (mål streng)

2 Identifisere de datapunkter hvor en streng er forskjellig fra den andre. For eksempel:

Cat (kilde streng)
Fate (mål streng)

Bokstavene forskjellig ved det første sted (C og F), og målet strengen har en ytterligere datapunkt (E).

3 Påfør minste antall redigere operasjoner (innsetting, sletting, substitusjon) mulige å endre kildestrengen til målet strengen. Tell endringer. For eksempel:

Cat -> erstatning F for C og sett E -> skjebne

Endringen krever to redigeringsoperasjoner, et bytte og en innsetting, og kan ikke være ferdig i færre. Derfor redigerings avstanden mellom "cat" og "skjebne" er to.