levenshtein.c 2.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
  1. // SPDX-License-Identifier: GPL-2.0
  2. #include "levenshtein.h"
  3. #include <errno.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. /*
  7. * This function implements the Damerau-Levenshtein algorithm to
  8. * calculate a distance between strings.
  9. *
  10. * Basically, it says how many letters need to be swapped, substituted,
  11. * deleted from, or added to string1, at least, to get string2.
  12. *
  13. * The idea is to build a distance matrix for the substrings of both
  14. * strings. To avoid a large space complexity, only the last three rows
  15. * are kept in memory (if swaps had the same or higher cost as one deletion
  16. * plus one insertion, only two rows would be needed).
  17. *
  18. * At any stage, "i + 1" denotes the length of the current substring of
  19. * string1 that the distance is calculated for.
  20. *
  21. * row2 holds the current row, row1 the previous row (i.e. for the substring
  22. * of string1 of length "i"), and row0 the row before that.
  23. *
  24. * In other words, at the start of the big loop, row2[j + 1] contains the
  25. * Damerau-Levenshtein distance between the substring of string1 of length
  26. * "i" and the substring of string2 of length "j + 1".
  27. *
  28. * All the big loop does is determine the partial minimum-cost paths.
  29. *
  30. * It does so by calculating the costs of the path ending in characters
  31. * i (in string1) and j (in string2), respectively, given that the last
  32. * operation is a substition, a swap, a deletion, or an insertion.
  33. *
  34. * This implementation allows the costs to be weighted:
  35. *
  36. * - w (as in "sWap")
  37. * - s (as in "Substitution")
  38. * - a (for insertion, AKA "Add")
  39. * - d (as in "Deletion")
  40. *
  41. * Note that this algorithm calculates a distance _iff_ d == a.
  42. */
  43. int levenshtein(const char *string1, const char *string2,
  44. int w, int s, int a, int d)
  45. {
  46. int len1 = strlen(string1), len2 = strlen(string2);
  47. int *row0 = malloc(sizeof(int) * (len2 + 1));
  48. int *row1 = malloc(sizeof(int) * (len2 + 1));
  49. int *row2 = malloc(sizeof(int) * (len2 + 1));
  50. int i, j;
  51. for (j = 0; j <= len2; j++)
  52. row1[j] = j * a;
  53. for (i = 0; i < len1; i++) {
  54. int *dummy;
  55. row2[0] = (i + 1) * d;
  56. for (j = 0; j < len2; j++) {
  57. /* substitution */
  58. row2[j + 1] = row1[j] + s * (string1[i] != string2[j]);
  59. /* swap */
  60. if (i > 0 && j > 0 && string1[i - 1] == string2[j] &&
  61. string1[i] == string2[j - 1] &&
  62. row2[j + 1] > row0[j - 1] + w)
  63. row2[j + 1] = row0[j - 1] + w;
  64. /* deletion */
  65. if (row2[j + 1] > row1[j + 1] + d)
  66. row2[j + 1] = row1[j + 1] + d;
  67. /* insertion */
  68. if (row2[j + 1] > row2[j] + a)
  69. row2[j + 1] = row2[j] + a;
  70. }
  71. dummy = row0;
  72. row0 = row1;
  73. row1 = row2;
  74. row2 = dummy;
  75. }
  76. i = row1[len2];
  77. free(row0);
  78. free(row1);
  79. free(row2);
  80. return i;
  81. }