Levenshtein distance/Alignment: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: added syntax colouring the hard way) |
Alextretyak (talk | contribs) (Added 11l) |
||
| Line 18: | Line 18: | ||
You can either implement an algorithm, or use a dedicated library (thus showing us how it is named in your language). |
You can either implement an algorithm, or use a dedicated library (thus showing us how it is named in your language). |
||
<br><br> |
<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}}== |
=={{header|Arturo}}== |
||