https://coral.shoes/morse-trainer/edit-distance.js

1// distance(given, typed) returns a list, where each element can either be a correctly typed char, incorrectly typed char, extra char or missing char
2
3const MAX_DISTANCE = 10; // hopefully the user isn't too bad
4
5// TODO: Ignore / handle spaces?
6
7function distance(given, typed) {
8    let lev_table = Array(given.length + 1).fill(Array(typed.length + 1).fill(-1)).map(a => a.slice());
9    let edit_table = Array(given.length + 1).fill(Array(typed.length + 1).fill(null)).map(a => a.slice());
10    // lev_table[i][j] = edit distance from given[i:] to typed[j:]
11    function distance_fill(i, j) {
12        let bail = Math.abs(i - j) > MAX_DISTANCE;
13        if (i > given.length || j > typed.length) {
14            return null;
15        }
16        if (lev_table[i][j] !== -1) {
17            return edit_table[i][j].slice();
18        }
19        let result = +"Infinity";
20        let edits = [];
21        let optimal = false;
22
23        if (i == given.length) {
24            result = typed.length - j;
25            if (result > 0) {
26                edits = [{"type": "extra_rest", "length": result}];
27            }
28        } else if (j === typed.length) {
29            result = 0.1 * (given.length - i);
30            if (result > 0) {
31                edits = [{"type": "missing_end", "length": given.length - i}];
32            }
33        } else {
34            if (i < given.length && j < typed.length) {
35                let edits_ = distance_fill(i + 1, j + 1);
36                let result_ = lev_table[i + 1][j + 1];
37                if (given[i] === typed[j]) {
38                    edits_.unshift({"type": "correct", "char": given[i]});
39                    optimal = true;
40                } else {
41                    edits_.unshift({"type": "incorrect", "given": given[i], "typed": typed[j]});
42                    result_++;
43                }
44                if (result_ < result) {
45                    result = result_;
46                    edits = edits_;
47                }
48            }
49            if (j < typed.length && !optimal && !bail) {
50                let edits_ = distance_fill(i, j + 1);
51                let result_ = 1 + lev_table[i][j + 1];
52                edits_.unshift({"type": "extraneous", "char": typed[j]});
53                if (result_ < result) {
54                    result = result_;
55                    edits = edits_;
56                }
57            }
58            if (i < given.length && !optimal && !bail) {
59                let edits_ = distance_fill(i + 1, j);
60                let result_ = 1 + lev_table[i + 1][j];
61                edits_.unshift({"type": "missing", "char": given[i]});
62                if (result_ < result) {
63                    result = result_;
64                    edits = edits_;
65                }
66            }
67        }
68
69        lev_table[i][j] = result;
70        edit_table[i][j] = edits;
71        return edits.slice();
72    }
73
74    let edits = distance_fill(0, 0);
75    return edits;
76}