edit_distance: calculate edit distance between strings
[ccan] / ccan / edit_distance / edit_distance.c
1 /** @file
2  * Defines shared edit distance functions.
3  *
4  * @copyright 2016 Kevin Locke <kevin@kevinlocke.name>
5  *            MIT license - see LICENSE file for details
6  */
7 #include "edit_distance-params.h"
8 #include "edit_distance-private.h"
9
10 ed_dist edit_distance(const ed_elem *src, ed_size slen,
11                       const ed_elem *tgt, ed_size tlen, enum ed_measure measure)
12 {
13         /* Remove common prefix. */
14         while (slen > 0 && tlen > 0 && ED_ELEM_EQUAL(src[0], tgt[0])) {
15                 ++src;
16                 ++tgt;
17                 --slen;
18                 --tlen;
19         }
20
21         /* Remove common suffix. */
22         while (slen > 0 && tlen > 0 &&
23                ED_ELEM_EQUAL(src[slen - 1], tgt[tlen - 1])) {
24                 --slen;
25                 --tlen;
26         }
27
28 #if defined(ED_COST_IS_SYMMETRIC)
29         /* Use smaller array for src. */
30         if (slen > tlen) {
31                 ED_SWAP(src, tgt, const ed_elem *);
32                 ED_SWAP(slen, tlen, ed_size);
33         }
34 #endif
35
36         /* Early return when all insertions. */
37         if (slen == 0) {
38 #ifdef ED_INS_COST_CONST
39                 return (ed_dist)tlen *ED_INS_COST();
40 #else
41                 ed_dist result = 0;
42                 for (ed_size i = 0; i < tlen; ++i) {
43                         result += ED_INS_COST(tgt[i]);
44                 }
45                 return result;
46 #endif
47         }
48 #ifndef ED_COST_IS_SYMMETRIC
49         /* Early return when all deletions. */
50         if (tlen == 0) {
51 # ifdef ED_DEL_COST_CONST
52                 return (ed_dist)slen *ED_DEL_COST();
53 # else
54                 ed_dist result = 0;
55                 for (ed_size i = 0; i < slen; ++i) {
56                         result += ED_DEL_COST(src[i]);
57                 }
58                 return result;
59 # endif
60         }
61 #endif
62
63 #if defined(ED_HAS_ELEM) && \
64                 defined(ED_INS_COST_CONST) && \
65                 defined(ED_SUB_COST_CONST)
66         /* Fast search for single-element source. */
67         if (slen == 1) {
68                 /* Always tlen - 1 inserts (of non-src elements). */
69                 ed_dist result = (ed_dist)(tlen - 1) * ED_INS_COST();
70                 if (!ED_HAS_ELEM(tgt, src[0], tlen)) {
71                         if (measure == EDIT_DISTANCE_LCS) {
72                                 /* If src is not present, delete + insert. */
73                                 result += ED_DEL_COST(src[0]) + ED_INS_COST();
74                         } else {
75                                 /* If src is not present, substitute it out. */
76                                 result += ED_SUB_COST(,);
77                         }
78                 }
79                 return result;
80         }
81 #endif
82
83 #if !defined(ED_COST_IS_SYMMETRIC) && \
84                 defined(ED_HAS_ELEM) && \
85                 defined(ED_DEL_COST_CONST) && \
86                 defined(ED_SUB_COST_CONST)
87         /* Fast search for single-element target. */
88         if (tlen == 1) {
89                 /* Always slen - 1 deletes (of non-tgt elements). */
90                 ed_dist result = (ed_dist)(slen - 1) * ED_DEL_COST();
91                 if (!ED_HAS_ELEM(src, tgt[0], slen)) {
92                         if (measure == EDIT_DISTANCE_LCS) {
93                                 /* If tgt is not present, delete + insert. */
94                                 result += ED_INS_COST(tgt[0]) + ED_DEL_COST();
95                         } else {
96                                 /* If tgt is not present, substitute it out. */
97                                 result += ED_SUB_COST(,);
98                         }
99                 }
100                 return result;
101         }
102 #endif
103
104         switch (measure) {
105         case EDIT_DISTANCE_LCS:
106                 return edit_distance_lcs(src, slen, tgt, tlen);
107         case EDIT_DISTANCE_LEV:
108                 return edit_distance_lev(src, slen, tgt, tlen);
109         case EDIT_DISTANCE_RDL:
110                 return edit_distance_rdl(src, slen, tgt, tlen);
111         case EDIT_DISTANCE_DL:
112                 return edit_distance_dl(src, slen, tgt, tlen);
113         }
114
115         return (ed_dist)-1;
116 }