git.ozlabs.org Git - ccan/blob - 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 }