Levenshtein distance/Alignment: Difference between revisions
Content added Content deleted
| Line 160: | Line 160: | ||
⟳ ic:(1 |..| source.count) ¦ l_distance [ic, 1] := ic - 1 ⟲ |
⟳ ic:(1 |..| source.count) ¦ l_distance [ic, 1] := ic - 1 ⟲ |
||
⟳ ij:(1 |..| target.count) ¦ l_distance [1, ij] := ij - 1 ⟲ |
⟳ ij:(1 |..| target.count) ¦ l_distance [1, ij] := ij - 1 ⟲ |
||
| ⚫ | |||
⟳ ic:(2 |..| source.count) ¦ |
|||
| ⚫ | |||
if ic > 1 and jc > 1 then |
|||
if source [ic] = target [jc] then -- same char |
|||
l_distance [ic, jc] := l_distance [ic - 1, jc - 1] |
|||
else -- diff char |
|||
del := l_distance [ic - 1, jc] -- delete? |
|||
ins := l_distance [ic, jc - 1] -- insert? |
|||
subst := l_distance [ic - 1, jc -1] -- substitute/swap? |
|||
l_distance [ic, jc] := del.min (ins.min (subst)) + 1 |
|||
end |
|||
end |
end |
||
⟲ |
⟲ |
||