2 * Defines Restricted Damerau-Levenshtein distance functions.
4 * @copyright 2016 Kevin Locke <kevin@kevinlocke.name>
5 * MIT license - see LICENSE file for details
7 #include <stdlib.h> /* free, malloc */
9 #include "edit_distance.h"
10 #include "edit_distance-params.h"
11 #include "edit_distance-private.h"
13 ed_dist edit_distance_rdl(const ed_elem *src, ed_size slen,
14 const ed_elem *tgt, ed_size tlen)
18 /* Optimization: Avoid malloc when required rows of distance matrix can
21 ed_dist stackdist[ED_STACK_DIST_VALS];
23 /* Two rows of the Wagner-Fischer distance matrix. */
24 ed_dist *distmem, *dist, *prevdist;
25 if (slen < ED_STACK_DIST_VALS / 2) {
28 prevdist = distmem + slen + 1;
30 distmem = malloc((slen + 1) * sizeof(ed_dist) * 2);
32 prevdist = distmem + slen + 1;
35 /* Initialize row with cost to delete src[0..i-1] */
37 for (i = 1; i <= slen; ++i) {
38 dist[i] = dist[i - 1] + ED_DEL_COST(src[i - 1]);
41 for (j = 1; j <= tlen; ++j) {
42 /* Value for dist[j-2][i-1] (two rows up, one col left). */
43 /* Note: dist[0] is not initialized when j == 1, var unused. */
44 ed_dist diagdist1 = prevdist[0];
45 /* Value for dist[j-2][i-2] (two rows up, two cols left).
46 * Initialization value only used to placate GCC. */
47 ed_dist diagdist2 = 0;
49 ED_SWAP(dist, prevdist, ed_dist *);
51 dist[0] = prevdist[0] + ED_INS_COST(tgt[j - 1]);
53 /* Loop invariant: dist[i] is the edit distance between first j
54 * elements of tgt and first i elements of src.
56 for (i = 1; i <= slen; ++i) {
57 ed_dist nextdiagdist = dist[i];
59 if (ED_ELEM_EQUAL(src[i - 1], tgt[j - 1])) {
60 /* Same as tgt upto j-2, src upto i-2. */
61 dist[i] = prevdist[i - 1];
63 /* Insertion is tgt upto j-2, src upto i-1
64 * + insert tgt[j-1] */
66 prevdist[i] + ED_INS_COST(tgt[j - 1]);
68 /* Deletion is tgt upto j-1, src upto i-2
69 * + delete src[i-1] */
71 dist[i - 1] + ED_DEL_COST(src[i - 1]);
73 /* Substitution is tgt upto j-2, src upto i-2
74 * + substitute tgt[j-1] for src[i-1] */
75 ed_dist subdist = prevdist[i - 1] +
76 ED_SUB_COST(src[i - 1], tgt[j - 1]);
78 /* Use best distance available */
79 dist[i] = ED_MIN3(insdist, deldist, subdist);
82 ED_ELEM_EQUAL(src[i - 2], tgt[j - 1]) &&
83 ED_ELEM_EQUAL(src[i - 1], tgt[j - 2])) {
84 ed_dist tradist = diagdist2 +
85 ED_TRA_COST(src[j - 2], src[j - 1]);
86 dist[i] = ED_MIN2(dist[i], tradist);
90 diagdist2 = diagdist1;
91 diagdist1 = nextdiagdist;
95 ed_dist total = dist[slen];
96 if (distmem != stackdist) {