Levenshteinavstånd

Hej!

Skulle behöva hjälp med att förstå hur man beräknar lägsta möjliga kostnad mellan två ord med Levenshteinavstånd. T.ex om vi har ordet sus och ska få brus, hur gör vi? Hittar inget när jag googlar. Vet hur man ställer upp orden i en matris men inte hur man beräknar avståndet.

sus till snus, avståndet 1
sus till brus, avståndet 2

osv...

Men behöver man inte skriva upp matrisen typ? För hur annars vet man det kortaste? Insertion och deletion kostar ju 1 men substitution(när man ersätter en bokstav med en annan) kostar 2.

Glöm substitution! En substitution är inget annat än en "borttagning" följt av ett "tillägg". Den kortaste vägen är ju den som kräver lika många operationer som det skiljer i tecken mellan de två strängarna, så jag förstår inte riktigt frågan.

Till exempel ditt exempel med "sus" till "brus". Det krävs minst två "tillägg" ty "brus" har fyra unika bokstäver medan "sus" bara har två. Det krävs en "borttagning", ty "sus" har en bokstav dubblerad, medan "brus" har endast unika bokstäver.

sus -> us -> rus -> brus (3 poäng)

Aa men vill lära mig hur man räknar ut på det korrekta sättet med matrisen.

Det här är väsentligt mer matte än språk, och TS får nog mer hjälp i FyMaTeK.

Språk --> Fysik, matematik och teknologi
/Moderator