1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#!/usr/bin/awk
#
# See ../README.md
#
#
# Run as: awk -f ch-2.awk < input-file
#
#
# Return the minimum of 3 values
#
function min (a, b, c) {
return a < b ? a < c ? a : c\
: b < c ? b : c
}
#
# This is an implementation of the Wagner Fischer algorithm, which
# calculates the Levenshtein distance.
#
# See https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorithm
#
{
for (i = 0; i <= length ($1); i ++) {
for (j = 0; j <= length ($2); j ++) {
distance [i, j] = i == 0 || j == 0 ? i + j\
: min(distance [i - 1, j] + 1,
distance [i, j - 1] + 1,
distance [i - 1, j - 1] +\
(substr ($1, i, 1) == substr ($2, j, 1) ? 0 : 1))
}
}
print distance [length ($1), length ($2)]
}
|
