lib/fstrcmp.c

   1 /* Functions to make fuzzy comparisons between strings
   2    Copyright (C) 1988-1989, 1992-1993, 1995, 2001-2003, 2006, 2008
   3    Free Software Foundation, Inc.
   4
   5    This program is free software: you can redistribute it and/or modify
   6    it under the terms of the GNU General Public License as published by
   7    the Free Software Foundation; either version 3 of the License, or
   8    (at your option) any later version.
   9
  10    This program is distributed in the hope that it will be useful,
  11    but WITHOUT ANY WARRANTY; without even the implied warranty of
  12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13    GNU General Public License for more details.
  14
  15    You should have received a copy of the GNU General Public License
  16    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  17
  18
  19    Derived from GNU diff 2.7, analyze.c et al.
  20
  21    The basic idea is to consider two vectors as similar if, when
  22    transforming the first vector into the second vector through a
  23    sequence of edits (inserts and deletes of one element each),
  24    this sequence is short - or equivalently, if the ordered list
  25    of elements that are untouched by these edits is long.  For a
  26    good introduction to the subject, read about the "Levenshtein
  27    distance" in Wikipedia.
  28
  29    The basic algorithm is described in:
  30    "An O(ND) Difference Algorithm and its Variations", Eugene Myers,
  31    Algorithmica Vol. 1 No. 2, 1986, pp. 251-266;
  32    see especially section 4.2, which describes the variation used below.
  33
  34    The basic algorithm was independently discovered as described in:
  35    "Algorithms for Approximate String Matching", E. Ukkonen,
  36    Information and Control Vol. 64, 1985, pp. 100-118.
  37
  38    Unless the 'find_minimal' flag is set, this code uses the TOO_EXPENSIVE
  39    heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N)
  40    at the price of producing suboptimal output for large inputs with
  41    many differences.  */
  42
  43 #include <config.h>
  44
  45 /* Specification.  */
  46 #include "fstrcmp.h"
  47
  48 #include <string.h>
  49 #include <stdbool.h>
  50 #include <stdio.h>
  51 #include <stdlib.h>
  52 #include <limits.h>
  53
  54 #include "glthread/lock.h"
  55 #include "glthread/tls.h"
  56 #include "minmax.h"
  57 #include "xalloc.h"
  58
  59 #ifndef uintptr_t
  60 # define uintptr_t unsigned long
  61 #endif
  62
  63
  64 #define ELEMENT char
  65 #define EQUAL(x,y) ((x) == (y))
  66 #define OFFSET int
  67 #define EXTRA_CONTEXT_FIELDS \
  68   /* The number of elements inserted, plus the number of elements deleted. */ \
  69   int edit_count;
  70 #define NOTE_DELETE(ctxt, xoff) ctxt->edit_count++
  71 #define NOTE_INSERT(ctxt, yoff) ctxt->edit_count++
  72 /* We don't need USE_HEURISTIC, since it is unlikely in typical uses of
  73    fstrcmp().  */
  74 #include "diffseq.h"
  75
  76
  77 /* Because fstrcmp is typically called multiple times, attempt to minimize
  78    the number of memory allocations performed.  Thus, let a call reuse the
  79    memory already allocated by the previous call, if it is sufficient.
  80    To make it multithread-safe, without need for a lock that protects the
  81    already allocated memory, store the allocated memory per thread.  Free
  82    it only when the thread exits.  */
  83
  84 static gl_tls_key_t buffer_key; /* TLS key for a 'int *' */
  85 static gl_tls_key_t bufmax_key; /* TLS key for a 'size_t' */
  86
  87 static void
  88 keys_init (void)
  89 {
  90   gl_tls_key_init (buffer_key, free);
  91   gl_tls_key_init (bufmax_key, NULL);
  92   /* The per-thread initial values are NULL and 0, respectively.  */
  93 }
  94
  95 /* Ensure that keys_init is called once only.  */
  96 gl_once_define(static, keys_init_once)
  97
  98
  99 double
 100 fstrcmp_bounded (const char *string1, const char *string2, double lower_bound)
 101 {
 102   struct context ctxt;
 103   int xvec_length = strlen (string1);
 104   int yvec_length = strlen (string2);
 105   int i;
 106
 107   size_t fdiag_len;
 108   int *buffer;
 109   size_t bufmax;
 110
 111   /* short-circuit obvious comparisons */
 112   if (xvec_length == 0 || yvec_length == 0)
 113     return (xvec_length == 0 && yvec_length == 0 ? 1.0 : 0.0);
 114
 115   if (lower_bound > 0)
 116     {
 117       /* Compute a quick upper bound.
 118          Each edit is an insertion or deletion of an element, hence modifies
 119          the length of the sequence by at most 1.
 120          Therefore, when starting from a sequence X and ending at a sequence Y,
 121          with N edits,  | yvec_length - xvec_length | <= N.  (Proof by
 122          induction over N.)
 123          So, at the end, we will have
 124            edit_count >= | xvec_length - yvec_length |.
 125          and hence
 126            result
 127              = (xvec_length + yvec_length - edit_count)
 128                / (xvec_length + yvec_length)
 129              <= (xvec_length + yvec_length - | yvec_length - xvec_length |)
 130                 / (xvec_length + yvec_length)
 131              = 2 * min (xvec_length, yvec_length) / (xvec_length + yvec_length).
 132        */
 133       volatile double upper_bound =
 134         (double) (2 * MIN (xvec_length, yvec_length))
 135         / (xvec_length + yvec_length);
 136
 137       if (upper_bound < lower_bound)
 138         /* Return an arbitrary value < LOWER_BOUND.  */
 139         return 0.0;
 140     }
 141
 142   /* set the info for each string.  */
 143   ctxt.xvec = string1;
 144   ctxt.yvec = string2;
 145
 146   /* Set TOO_EXPENSIVE to be approximate square root of input size,
 147      bounded below by 256.  */
 148   ctxt.too_expensive = 1;
 149   for (i = xvec_length + yvec_length;
 150        i != 0;
 151        i >>= 2)
 152     ctxt.too_expensive <<= 1;
 153   if (ctxt.too_expensive < 256)
 154     ctxt.too_expensive = 256;
 155
 156   /* Allocate memory for fdiag and bdiag from a thread-local pool.  */
 157   fdiag_len = xvec_length + yvec_length + 3;
 158   gl_once (keys_init_once, keys_init);
 159   buffer = (int *) gl_tls_get (buffer_key);
 160   bufmax = (size_t) (uintptr_t) gl_tls_get (bufmax_key);
 161   if (fdiag_len > bufmax)
 162     {
 163       /* Need more memory.  */
 164       bufmax = 2 * bufmax;
 165       if (fdiag_len > bufmax)
 166         bufmax = fdiag_len;
 167       /* Calling xrealloc would be a waste: buffer's contents does not need
 168          to be preserved.  */
 169       if (buffer != NULL)
 170         free (buffer);
 171       buffer = (int *) xnmalloc (bufmax, 2 * sizeof (int));
 172       gl_tls_set (buffer_key, buffer);
 173       gl_tls_set (bufmax_key, (void *) (uintptr_t) bufmax);
 174     }
 175   ctxt.fdiag = buffer + yvec_length + 1;
 176   ctxt.bdiag = ctxt.fdiag + fdiag_len;
 177
 178   /* Now do the main comparison algorithm */
 179   ctxt.edit_count = 0;
 180   compareseq (0, xvec_length, 0, yvec_length, 0,
 181               &ctxt);
 182
 183   /* The result is
 184         ((number of chars in common) / (average length of the strings)).
 185      The numerator is
 186         = xvec_length - (number of calls to NOTE_DELETE)
 187         = yvec_length - (number of calls to NOTE_INSERT)
 188         = 1/2 * (xvec_length + yvec_length - (number of edits)).
 189      This is admittedly biased towards finding that the strings are
 190      similar, however it does produce meaningful results.  */
 191   return ((double) (xvec_length + yvec_length - ctxt.edit_count)
 192           / (xvec_length + yvec_length));
 193 }