edit_distance: calculate edit distance between strings
[ccan] / ccan / edit_distance / _info
1 #include "config.h"
2 #include <stdio.h>
3 #include <string.h>
4
5 /**
6  * edit_distance - calculate the edit distance between two strings
7  *
8  * The edit distance quantifies the similarity between two strings based on the
9  * number of modifications necessary to turn one string into the other.  There
10  * are several edit distance measures which differ in the operations which are
11  * permitted and the cost (aka weight) of the operations.  This module provides
12  * functions for calculating the Longest Common Subsequence (LCS), Levenshtein,
13  * and Damerau-Levenshtein (restricted and unrestricted) distances.  Weighted
14  * versions of these functions can be created by defining cost functions as
15  * preprocessor macros when compiling this module.  Distances over other array
16  * types (e.g. wide strings, integers, structs) can be accomplished by defining
17  * the element type and equality test macros.
18  *
19  * Example:
20  * #include <limits.h>  // UINT_MAX
21  * #include <stdio.h>   // fprintf, printf
22  * #include <stdlib.h>  // EXIT_*
23  * #include <string.h>  // strlen
24  *
25  * #include <ccan/edit_distance/edit_distance.h>
26  *
27  * const char *counties[] = {
28  *      "Anglesey",
29  *      "Brecknockshire",
30  *      "Cardiganshire",
31  *      "Carmarthenshire",
32  *      "Caernarfonshire",
33  *      "Denbighshire",
34  *      "Flintshire",
35  *      "Glamorgan",
36  *      "Merionethshire",
37  *      "Monmouthshire",
38  *      "Montgomeryshire",
39  *      "Pembrokeshire",
40  *      "Radnorshire",
41  *      NULL
42  * };
43  *
44  * int main(int argc, char *argv[])
45  * {
46  *      if (argc != 2) {
47  *              fprintf(stderr, "Usage: %s <guess>\n", argv[0]);
48  *              return EXIT_FAILURE;
49  *      }
50  *      const char *guess = argv[1];
51  *
52  *      unsigned int bestdist = UINT_MAX;
53  *      const char *bestcounty = NULL;
54  *      for (const char **pcounty = counties; *pcounty; ++pcounty) {
55  *              const char *county = *pcounty;
56  *              unsigned int dist = edit_distance(guess, strlen(guess),
57  *                              county, strlen(county), EDIT_DISTANCE_RDL);
58  *              if (dist < bestdist) {
59  *                      bestdist = dist;
60  *                      bestcounty = county;
61  *              }
62  *      }
63  *
64  *      printf("You were probably trying to spell %s\n", bestcounty);
65  *      return EXIT_SUCCESS;
66  * }
67  * License: MIT
68  * Author: Kevin Locke <kevin@kevinlocke.name>
69  */
70 int main(int argc, char *argv[])
71 {
72         /* Expect exactly one argument */
73         if (argc != 2) {
74                 return 1;
75         }
76
77         if (strcmp(argv[1], "depends") == 0) {
78                 return 0;
79         }
80
81         if (strcmp(argv[1], "testdepends") == 0) {
82                 printf("ccan/array_size\n");
83                 printf("ccan/build_assert\n");
84                 printf("ccan/tap\n");
85                 return 0;
86         }
87
88         return 1;
89 }