Levenshtein distance/Alignment: Difference between revisions
Added 11l
m (→{{header|Phix}}: added syntax colouring the hard way) |
Alextretyak (talk | contribs) (Added 11l) |
||
Line 18:
You can either implement an algorithm, or use a dedicated library (thus showing us how it is named in your language).
<br><br>
=={{header|11l}}==
{{trans|Nim}}
<lang 11l>F levenshteinAlign(aa, bb)
V a = aa.lowercase()
V b = bb.lowercase()
V costs = [[0] * (b.len + 1)] * (a.len + 1)
L(j) 0 .. b.len
costs[0][j] = j
L(i) 1 .. a.len
costs[i][0] = i
L(j) 1 .. b.len
V tmp = costs[i - 1][j - 1] + Int(a[i - 1] != b[j - 1])
costs[i][j] = min(1 + min(costs[i - 1][j], costs[i][j - 1]), tmp)
V aPathRev = ‘’
V bPathRev = ‘’
V i = a.len
V j = b.len
L i != 0 & j != 0
V tmp = costs[i - 1][j - 1] + Int(a[i - 1] != b[j - 1])
I costs[i][j] == tmp
aPathRev ‘’= a[--i]
bPathRev ‘’= b[--j]
E I costs[i][j] == 1 + costs[i - 1][j]
aPathRev ‘’= a[--i]
bPathRev ‘’= ‘-’
E I costs[i][j] == 1 + costs[i][j - 1]
aPathRev ‘’= ‘-’
bPathRev ‘’= b[--j]
E
assert(0B, ‘Internal error’)
R (reversed(aPathRev), reversed(bPathRev))
V result = levenshteinAlign(‘place’, ‘palace’)
print(result[0])
print(result[1])
print()
result = levenshteinAlign(‘rosettacode’, ‘raisethysword’)
print(result[0])
print(result[1])</lang>
{{out}}
<pre>
p-lace
palace
r-oset-tacode
raisethysword
</pre>
=={{header|Arturo}}==
| |||