granicus.if.org Git - postgresql/blob - src/backend/utils/adt/levenshtein.c

   1 /*-------------------------------------------------------------------------
   2  *
   3  * levenshtein.c
   4  *        Levenshtein distance implementation.
   5  *
   6  * Original author:  Joe Conway <mail@joeconway.com>
   7  *
   8  * This file is included by varlena.c twice, to provide matching code for (1)
   9  * Levenshtein distance with custom costings, and (2) Levenshtein distance with
  10  * custom costings and a "max" value above which exact distances are not
  11  * interesting.  Before the inclusion, we rely on the presence of the inline
  12  * function rest_of_char_same().
  13  *
  14  * Written based on a description of the algorithm by Michael Gilleland found
  15  * at http://www.merriampark.com/ld.htm.  Also looked at levenshtein.c in the
  16  * PHP 4.0.6 distribution for inspiration.  Configurable penalty costs
  17  * extension is introduced by Volkan YAZICI <volkan.yazici@gmail.com.
  18  *
  19  * Copyright (c) 2001-2015, PostgreSQL Global Development Group
  20  *
  21  * IDENTIFICATION
  22  *      src/backend/utils/adt/levenshtein.c
  23  *
  24  *-------------------------------------------------------------------------
  25  */
  26 #define MAX_LEVENSHTEIN_STRLEN          255
  27
  28 /*
  29  * Calculates Levenshtein distance metric between supplied csrings, which are
  30  * not necessarily null-terminated.  Generally (1, 1, 1) penalty costs suffices
  31  * for common cases, but your mileage may vary.
  32  *
  33  * One way to compute Levenshtein distance is to incrementally construct
  34  * an (m+1)x(n+1) matrix where cell (i, j) represents the minimum number
  35  * of operations required to transform the first i characters of s into
  36  * the first j characters of t.  The last column of the final row is the
  37  * answer.
  38  *
  39  * We use that algorithm here with some modification.  In lieu of holding
  40  * the entire array in memory at once, we'll just use two arrays of size
  41  * m+1 for storing accumulated values. At each step one array represents
  42  * the "previous" row and one is the "current" row of the notional large
  43  * array.
  44  *
  45  * If max_d >= 0, we only need to provide an accurate answer when that answer
  46  * is less than or equal to the bound.  From any cell in the matrix, there is
  47  * theoretical "minimum residual distance" from that cell to the last column
  48  * of the final row.  This minimum residual distance is zero when the
  49  * untransformed portions of the strings are of equal length (because we might
  50  * get lucky and find all the remaining characters matching) and is otherwise
  51  * based on the minimum number of insertions or deletions needed to make them
  52  * equal length.  The residual distance grows as we move toward the upper
  53  * right or lower left corners of the matrix.  When the max_d bound is
  54  * usefully tight, we can use this property to avoid computing the entirety
  55  * of each row; instead, we maintain a start_column and stop_column that
  56  * identify the portion of the matrix close to the diagonal which can still
  57  * affect the final answer.
  58  */
  59 int
  60 #ifdef LEVENSHTEIN_LESS_EQUAL
  61 varstr_levenshtein_less_equal(const char *source, int slen, const char *target,
  62                                                           int tlen, int ins_c, int del_c, int sub_c,
  63                                                           int max_d)
  64 #else
  65 varstr_levenshtein(const char *source, int slen, const char *target, int tlen,
  66                                    int ins_c, int del_c, int sub_c)
  67 #endif
  68 {
  69         int                     m,
  70                                 n;
  71         int                *prev;
  72         int                *curr;
  73         int                *s_char_len = NULL;
  74         int                     i,
  75                                 j;
  76         const char *y;
  77
  78         /*
  79          * For varstr_levenshtein_less_equal, we have real variables called
  80          * start_column and stop_column; otherwise it's just short-hand for 0 and
  81          * m.
  82          */
  83 #ifdef LEVENSHTEIN_LESS_EQUAL
  84         int                     start_column,
  85                                 stop_column;
  86
  87 #undef START_COLUMN
  88 #undef STOP_COLUMN
  89 #define START_COLUMN start_column
  90 #define STOP_COLUMN stop_column
  91 #else
  92 #undef START_COLUMN
  93 #undef STOP_COLUMN
  94 #define START_COLUMN 0
  95 #define STOP_COLUMN m
  96 #endif
  97
  98         /*
  99          * A common use for Levenshtein distance is to match attributes when building
 100          * diagnostic, user-visible messages.  Restrict the size of
 101          * MAX_LEVENSHTEIN_STRLEN at compile time so that this is guaranteed to
 102          * work.
 103          */
 104         StaticAssertStmt(NAMEDATALEN <= MAX_LEVENSHTEIN_STRLEN,
 105                                          "Levenshtein hinting mechanism restricts NAMEDATALEN");
 106
 107         m = pg_mbstrlen_with_len(source, slen);
 108         n = pg_mbstrlen_with_len(target, tlen);
 109
 110         /*
 111          * We can transform an empty s into t with n insertions, or a non-empty t
 112          * into an empty s with m deletions.
 113          */
 114         if (!m)
 115                 return n * ins_c;
 116         if (!n)
 117                 return m * del_c;
 118
 119         /*
 120          * For security concerns, restrict excessive CPU+RAM usage. (This
 121          * implementation uses O(m) memory and has O(mn) complexity.)
 122          */
 123         if (m > MAX_LEVENSHTEIN_STRLEN ||
 124                 n > MAX_LEVENSHTEIN_STRLEN)
 125                 ereport(ERROR,
 126                                 (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
 127                                  errmsg("argument exceeds the maximum length of %d bytes",
 128                                                 MAX_LEVENSHTEIN_STRLEN)));
 129
 130 #ifdef LEVENSHTEIN_LESS_EQUAL
 131         /* Initialize start and stop columns. */
 132         start_column = 0;
 133         stop_column = m + 1;
 134
 135         /*
 136          * If max_d >= 0, determine whether the bound is impossibly tight.  If so,
 137          * return max_d + 1 immediately.  Otherwise, determine whether it's tight
 138          * enough to limit the computation we must perform.  If so, figure out
 139          * initial stop column.
 140          */
 141         if (max_d >= 0)
 142         {
 143                 int                     min_theo_d; /* Theoretical minimum distance. */
 144                 int                     max_theo_d; /* Theoretical maximum distance. */
 145                 int                     net_inserts = n - m;
 146
 147                 min_theo_d = net_inserts < 0 ?
 148                         -net_inserts * del_c : net_inserts * ins_c;
 149                 if (min_theo_d > max_d)
 150                         return max_d + 1;
 151                 if (ins_c + del_c < sub_c)
 152                         sub_c = ins_c + del_c;
 153                 max_theo_d = min_theo_d + sub_c * Min(m, n);
 154                 if (max_d >= max_theo_d)
 155                         max_d = -1;
 156                 else if (ins_c + del_c > 0)
 157                 {
 158                         /*
 159                          * Figure out how much of the first row of the notional matrix we
 160                          * need to fill in.  If the string is growing, the theoretical
 161                          * minimum distance already incorporates the cost of deleting the
 162                          * number of characters necessary to make the two strings equal in
 163                          * length.  Each additional deletion forces another insertion, so
 164                          * the best-case total cost increases by ins_c + del_c. If the
 165                          * string is shrinking, the minimum theoretical cost assumes no
 166                          * excess deletions; that is, we're starting no further right than
 167                          * column n - m.  If we do start further right, the best-case
 168                          * total cost increases by ins_c + del_c for each move right.
 169                          */
 170                         int                     slack_d = max_d - min_theo_d;
 171                         int                     best_column = net_inserts < 0 ? -net_inserts : 0;
 172
 173                         stop_column = best_column + (slack_d / (ins_c + del_c)) + 1;
 174                         if (stop_column > m)
 175                                 stop_column = m + 1;
 176                 }
 177         }
 178 #endif
 179
 180         /*
 181          * In order to avoid calling pg_mblen() repeatedly on each character in s,
 182          * we cache all the lengths before starting the main loop -- but if all
 183          * the characters in both strings are single byte, then we skip this and
 184          * use a fast-path in the main loop.  If only one string contains
 185          * multi-byte characters, we still build the array, so that the fast-path
 186          * needn't deal with the case where the array hasn't been initialized.
 187          */
 188         if (m != slen || n != tlen)
 189         {
 190                 int                     i;
 191                 const char *cp = source;
 192
 193                 s_char_len = (int *) palloc((m + 1) * sizeof(int));
 194                 for (i = 0; i < m; ++i)
 195                 {
 196                         s_char_len[i] = pg_mblen(cp);
 197                         cp += s_char_len[i];
 198                 }
 199                 s_char_len[i] = 0;
 200         }
 201
 202         /* One more cell for initialization column and row. */
 203         ++m;
 204         ++n;
 205
 206         /* Previous and current rows of notional array. */
 207         prev = (int *) palloc(2 * m * sizeof(int));
 208         curr = prev + m;
 209
 210         /*
 211          * To transform the first i characters of s into the first 0 characters of
 212          * t, we must perform i deletions.
 213          */
 214         for (i = START_COLUMN; i < STOP_COLUMN; i++)
 215                 prev[i] = i * del_c;
 216
 217         /* Loop through rows of the notional array */
 218         for (y = target, j = 1; j < n; j++)
 219         {
 220                 int                *temp;
 221                 const char *x = source;
 222                 int                     y_char_len = n != tlen + 1 ? pg_mblen(y) : 1;
 223
 224 #ifdef LEVENSHTEIN_LESS_EQUAL
 225
 226                 /*
 227                  * In the best case, values percolate down the diagonal unchanged, so
 228                  * we must increment stop_column unless it's already on the right end
 229                  * of the array.  The inner loop will read prev[stop_column], so we
 230                  * have to initialize it even though it shouldn't affect the result.
 231                  */
 232                 if (stop_column < m)
 233                 {
 234                         prev[stop_column] = max_d + 1;
 235                         ++stop_column;
 236                 }
 237
 238                 /*
 239                  * The main loop fills in curr, but curr[0] needs a special case: to
 240                  * transform the first 0 characters of s into the first j characters
 241                  * of t, we must perform j insertions.  However, if start_column > 0,
 242                  * this special case does not apply.
 243                  */
 244                 if (start_column == 0)
 245                 {
 246                         curr[0] = j * ins_c;
 247                         i = 1;
 248                 }
 249                 else
 250                         i = start_column;
 251 #else
 252                 curr[0] = j * ins_c;
 253                 i = 1;
 254 #endif
 255
 256                 /*
 257                  * This inner loop is critical to performance, so we include a
 258                  * fast-path to handle the (fairly common) case where no multibyte
 259                  * characters are in the mix.  The fast-path is entitled to assume
 260                  * that if s_char_len is not initialized then BOTH strings contain
 261                  * only single-byte characters.
 262                  */
 263                 if (s_char_len != NULL)
 264                 {
 265                         for (; i < STOP_COLUMN; i++)
 266                         {
 267                                 int                     ins;
 268                                 int                     del;
 269                                 int                     sub;
 270                                 int                     x_char_len = s_char_len[i - 1];
 271
 272                                 /*
 273                                  * Calculate costs for insertion, deletion, and substitution.
 274                                  *
 275                                  * When calculating cost for substitution, we compare the last
 276                                  * character of each possibly-multibyte character first,
 277                                  * because that's enough to rule out most mis-matches.  If we
 278                                  * get past that test, then we compare the lengths and the
 279                                  * remaining bytes.
 280                                  */
 281                                 ins = prev[i] + ins_c;
 282                                 del = curr[i - 1] + del_c;
 283                                 if (x[x_char_len - 1] == y[y_char_len - 1]
 284                                         && x_char_len == y_char_len &&
 285                                         (x_char_len == 1 || rest_of_char_same(x, y, x_char_len)))
 286                                         sub = prev[i - 1];
 287                                 else
 288                                         sub = prev[i - 1] + sub_c;
 289
 290                                 /* Take the one with minimum cost. */
 291                                 curr[i] = Min(ins, del);
 292                                 curr[i] = Min(curr[i], sub);
 293
 294                                 /* Point to next character. */
 295                                 x += x_char_len;
 296                         }
 297                 }
 298                 else
 299                 {
 300                         for (; i < STOP_COLUMN; i++)
 301                         {
 302                                 int                     ins;
 303                                 int                     del;
 304                                 int                     sub;
 305
 306                                 /* Calculate costs for insertion, deletion, and substitution. */
 307                                 ins = prev[i] + ins_c;
 308                                 del = curr[i - 1] + del_c;
 309                                 sub = prev[i - 1] + ((*x == *y) ? 0 : sub_c);
 310
 311                                 /* Take the one with minimum cost. */
 312                                 curr[i] = Min(ins, del);
 313                                 curr[i] = Min(curr[i], sub);
 314
 315                                 /* Point to next character. */
 316                                 x++;
 317                         }
 318                 }
 319
 320                 /* Swap current row with previous row. */
 321                 temp = curr;
 322                 curr = prev;
 323                 prev = temp;
 324
 325                 /* Point to next character. */
 326                 y += y_char_len;
 327
 328 #ifdef LEVENSHTEIN_LESS_EQUAL
 329
 330                 /*
 331                  * This chunk of code represents a significant performance hit if used
 332                  * in the case where there is no max_d bound.  This is probably not
 333                  * because the max_d >= 0 test itself is expensive, but rather because
 334                  * the possibility of needing to execute this code prevents tight
 335                  * optimization of the loop as a whole.
 336                  */
 337                 if (max_d >= 0)
 338                 {
 339                         /*
 340                          * The "zero point" is the column of the current row where the
 341                          * remaining portions of the strings are of equal length.  There
 342                          * are (n - 1) characters in the target string, of which j have
 343                          * been transformed.  There are (m - 1) characters in the source
 344                          * string, so we want to find the value for zp where (n - 1) - j =
 345                          * (m - 1) - zp.
 346                          */
 347                         int                     zp = j - (n - m);
 348
 349                         /* Check whether the stop column can slide left. */
 350                         while (stop_column > 0)
 351                         {
 352                                 int                     ii = stop_column - 1;
 353                                 int                     net_inserts = ii - zp;
 354
 355                                 if (prev[ii] + (net_inserts > 0 ? net_inserts * ins_c :
 356                                                                 -net_inserts * del_c) <= max_d)
 357                                         break;
 358                                 stop_column--;
 359                         }
 360
 361                         /* Check whether the start column can slide right. */
 362                         while (start_column < stop_column)
 363                         {
 364                                 int                     net_inserts = start_column - zp;
 365
 366                                 if (prev[start_column] +
 367                                         (net_inserts > 0 ? net_inserts * ins_c :
 368                                          -net_inserts * del_c) <= max_d)
 369                                         break;
 370
 371                                 /*
 372                                  * We'll never again update these values, so we must make sure
 373                                  * there's nothing here that could confuse any future
 374                                  * iteration of the outer loop.
 375                                  */
 376                                 prev[start_column] = max_d + 1;
 377                                 curr[start_column] = max_d + 1;
 378                                 if (start_column != 0)
 379                                         source += (s_char_len != NULL) ? s_char_len[start_column - 1] : 1;
 380                                 start_column++;
 381                         }
 382
 383                         /* If they cross, we're going to exceed the bound. */
 384                         if (start_column >= stop_column)
 385                                 return max_d + 1;
 386                 }
 387 #endif
 388         }
 389
 390         /*
 391          * Because the final value was swapped from the previous row to the
 392          * current row, that's where we'll find it.
 393          */
 394         return prev[m - 1];
 395 }