changeset 10443:13d9d9fee7b5

Use a second, less quick upper bound based on character occurrence counts.
author Ralf Wildenhues <Ralf.Wildenhues@gmx.de>
date Tue, 16 Sep 2008 03:16:11 +0200
parents 86be59f0ff1b
children e7595530873e
files ChangeLog lib/fstrcmp.c
diffstat 2 files changed, 54 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+2008-09-15  Ralf Wildenhues  <Ralf.Wildenhues@gmx.de>
+
+	* lib/fstrcmp.c (fstrcmp_bounded): Use a second, less quick upper bound
+	based on character occurrence counts.
+
 2008-09-15  Eric Blake  <ebb9@byu.net>
 
 	tests: avoid some compiler warnings
--- a/lib/fstrcmp.c
+++ b/lib/fstrcmp.c
@@ -141,6 +141,55 @@
       if (upper_bound < lower_bound)
 	/* Return an arbitrary value < LOWER_BOUND.  */
 	return 0.0;
+
+#if CHAR_BIT <= 8
+      /* When X and Y are both small, avoid the overhead of setting up an
+	 array of size 256.  */
+      if (xvec_length + yvec_length >= 20)
+	{
+	  /* Compute a less quick upper bound.
+	     Each edit is an insertion or deletion of a character, hence
+	     modifies the occurrence count of a character by 1 and leaves the
+	     other occurrence counts unchanged.
+	     Therefore, when starting from a sequence X and ending at a
+	     sequence Y, and denoting the occurrence count of C in X with
+	     OCC (X, C), with N edits,
+	       sum_C | OCC (X, C) - OCC (Y, C) | <= N.
+	     (Proof by induction over N.)
+	     So, at the end, we will have
+	       edit_count >= sum_C | OCC (X, C) - OCC (Y, C) |,
+	     and hence
+	       result
+		 = (xvec_length + yvec_length - edit_count)
+		   / (xvec_length + yvec_length)
+		 <= (xvec_length + yvec_length - sum_C | OCC(X,C) - OCC(Y,C) |)
+		    / (xvec_length + yvec_length).
+	   */
+	  int occ_diff[UCHAR_MAX + 1]; /* array C -> OCC(X,C) - OCC(Y,C) */
+	  int sum;
+
+	  /* Determine the occurrence counts in X.  */
+	  memset (occ_diff, 0, sizeof (occ_diff));
+	  for (i = xvec_length - 1; i >= 0; i--)
+	    occ_diff[(unsigned char) string1[i]]++;
+	  /* Subtract the occurrence counts in Y.  */
+	  for (i = yvec_length - 1; i >= 0; i--)
+	    occ_diff[(unsigned char) string2[i]]--;
+	  /* Sum up the absolute values.  */
+	  sum = 0;
+	  for (i = 0; i <= UCHAR_MAX; i++)
+	    {
+	      int d = occ_diff[i];
+	      sum += (d >= 0 ? d : -d);
+	    }
+
+	  upper_bound = 1.0 - (double) sum / (xvec_length + yvec_length);
+
+	  if (upper_bound < lower_bound)
+	    /* Return an arbitrary value < LOWER_BOUND.  */
+	    return 0.0;
+	}
+#endif
     }
 
   /* set the info for each string.  */