git.ozlabs.org Git - ccan/blob - ccan/edit_distance/edit_distance_rdl.c

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