home *** CD-ROM | disk | FTP | other *** search
/ Geek Gadgets 1 / ADE-1.bin / ade-dist / gettext-0.10.24-src.tgz / tar.out / fsf / gettext / lib / fstrcmp.c < prev    next >
C/C++ Source or Header  |  1996-09-28  |  16KB  |  637 lines
  1. /* Functions to make fuzzy comparisons between strings
  2.    Copyright (C) 1988, 1989, 1992, 1993, 1995 Free Software Foundation, Inc.
  3.  
  4.    This program is free software; you can redistribute it and/or modify
  5.    it under the terms of the GNU General Public License as published by
  6.    the Free Software Foundation; either version 2 of the License, or (at
  7.    your option) any later version.
  8.  
  9.    This program is distributed in the hope that it will be useful, but
  10.    WITHOUT ANY WARRANTY; without even the implied warranty of
  11.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12.    General Public License for more details.
  13.  
  14.    You should have received a copy of the GNU General Public License
  15.    along with this program; if not, write to the Free Software
  16.    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17.  
  18.  
  19.    Derived from GNU diff 2.7, analyze.c et al.
  20.  
  21.    The basic algorithm is described in:
  22.    "An O(ND) Difference Algorithm and its Variations", Eugene Myers,
  23.    Algorithmica Vol. 1 No. 2, 1986, pp. 251-266;
  24.    see especially section 4.2, which describes the variation used below.
  25.  
  26.    The basic algorithm was independently discovered as described in:
  27.    "Algorithms for Approximate String Matching", E. Ukkonen,
  28.    Information and Control Vol. 64, 1985, pp. 100-118.
  29.  
  30.    Modified to work on strings rather than files
  31.    by Peter Miller <pmiller@agso.gov.au>, October 1995 */
  32.  
  33. #ifdef HAVE_CONFIG_H
  34. # include "config.h"
  35. #endif
  36.  
  37. #ifdef HAVE_STRING_H
  38. # include <string.h>
  39. #else
  40. # include <strings.h>
  41. #endif
  42.  
  43. #include <stdio.h>
  44.  
  45. #ifdef HAVE_LIMITS_H
  46. # include <limits.h>
  47. #else
  48. # define INT_MAX ((int)(~(unsigned)0 >> 1))
  49. #endif
  50.  
  51. #include "system.h"
  52. #include "fstrcmp.h"
  53.  
  54.  
  55. /*
  56.  * Data on one input string being compared.
  57.  */
  58. struct string_data
  59. {
  60.   /* The string to be compared. */
  61.   const char *data;
  62.  
  63.   /* The length of the string to be compared. */
  64.   int data_length;
  65.  
  66.   /* The number of characters inserted or deleted. */
  67.   int edit_count;
  68. };
  69.  
  70. static struct string_data string[2];
  71.  
  72.  
  73. #ifdef MINUS_H_FLAG
  74.  
  75. /* This corresponds to the diff -H flag.  With this heuristic, for
  76.    strings with a constant small density of changes, the algorithm is
  77.    linear in the strings size.  This is unlikely in typical uses of
  78.    fstrcmp, and so is usually compiled out.  Besides, there is no
  79.    interface to set it true.  */
  80. static int heuristic;
  81.  
  82. #endif
  83.  
  84.  
  85. /* Vector, indexed by diagonal, containing 1 + the X coordinate of the
  86.    point furthest along the given diagonal in the forward search of the
  87.    edit matrix.  */
  88. static int *fdiag;
  89.  
  90. /* Vector, indexed by diagonal, containing the X coordinate of the point
  91.    furthest along the given diagonal in the backward search of the edit
  92.    matrix.  */
  93. static int *bdiag;
  94.  
  95. /* Edit scripts longer than this are too expensive to compute.  */
  96. static int too_expensive;
  97.  
  98. /* Snakes bigger than this are considered `big'.  */
  99. #define SNAKE_LIMIT    20
  100.  
  101. struct partition
  102. {
  103.   /* Midpoints of this partition.  */
  104.   int xmid, ymid;
  105.  
  106.   /* Nonzero if low half will be analyzed minimally.  */
  107.   int lo_minimal;
  108.  
  109.   /* Likewise for high half.  */
  110.   int hi_minimal;
  111. };
  112.  
  113.  
  114. /* NAME
  115.     diag - find diagonal path
  116.  
  117.    SYNOPSIS
  118.     int diag(int xoff, int xlim, int yoff, int ylim, int minimal,
  119.         struct partition *part);
  120.  
  121.    DESCRIPTION
  122.     Find the midpoint of the shortest edit script for a specified
  123.     portion of the two strings.
  124.  
  125.     Scan from the beginnings of the strings, and simultaneously from
  126.     the ends, doing a breadth-first search through the space of
  127.     edit-sequence.  When the two searches meet, we have found the
  128.     midpoint of the shortest edit sequence.
  129.  
  130.     If MINIMAL is nonzero, find the minimal edit script regardless
  131.     of expense.  Otherwise, if the search is too expensive, use
  132.     heuristics to stop the search and report a suboptimal answer.
  133.  
  134.    RETURNS
  135.     Set PART->(XMID,YMID) to the midpoint (XMID,YMID).  The diagonal
  136.     number XMID - YMID equals the number of inserted characters
  137.     minus the number of deleted characters (counting only characters
  138.     before the midpoint).  Return the approximate edit cost; this is
  139.     the total number of characters inserted or deleted (counting
  140.     only characters before the midpoint), unless a heuristic is used
  141.     to terminate the search prematurely.
  142.  
  143.     Set PART->LEFT_MINIMAL to nonzero iff the minimal edit script
  144.     for the left half of the partition is known; similarly for
  145.     PART->RIGHT_MINIMAL.
  146.  
  147.    CAVEAT
  148.     This function assumes that the first characters of the specified
  149.     portions of the two strings do not match, and likewise that the
  150.     last characters do not match.  The caller must trim matching
  151.     characters from the beginning and end of the portions it is
  152.     going to specify.
  153.  
  154.     If we return the "wrong" partitions, the worst this can do is
  155.     cause suboptimal diff output.  It cannot cause incorrect diff
  156.     output.  */
  157.  
  158. static int diag PARAMS ((int, int, int, int, int, struct partition *));
  159.  
  160. static int
  161. diag (xoff, xlim, yoff, ylim, minimal, part)
  162.      int xoff;
  163.      int xlim;
  164.      int yoff;
  165.      int ylim;
  166.      int minimal;
  167.      struct partition *part;
  168. {
  169.   int *const fd = fdiag;    /* Give the compiler a chance. */
  170.   int *const bd = bdiag;    /* Additional help for the compiler. */
  171.   const char *const xv = string[0].data;    /* Still more help for the compiler. */
  172.   const char *const yv = string[1].data;    /* And more and more . . . */
  173.   const int dmin = xoff - ylim;    /* Minimum valid diagonal. */
  174.   const int dmax = xlim - yoff;    /* Maximum valid diagonal. */
  175.   const int fmid = xoff - yoff;    /* Center diagonal of top-down search. */
  176.   const int bmid = xlim - ylim;    /* Center diagonal of bottom-up search. */
  177.   int fmin = fmid;
  178.   int fmax = fmid;        /* Limits of top-down search. */
  179.   int bmin = bmid;
  180.   int bmax = bmid;        /* Limits of bottom-up search. */
  181.   int c;            /* Cost. */
  182.   int odd = (fmid - bmid) & 1;
  183.  
  184.   /*
  185.      * True if southeast corner is on an odd diagonal with respect
  186.      * to the northwest.
  187.      */
  188.   fd[fmid] = xoff;
  189.   bd[bmid] = xlim;
  190.   for (c = 1;; ++c)
  191.     {
  192.       int d;            /* Active diagonal. */
  193.       int big_snake;
  194.  
  195.       big_snake = 0;
  196.       /* Extend the top-down search by an edit step in each diagonal. */
  197.       if (fmin > dmin)
  198.     fd[--fmin - 1] = -1;
  199.       else
  200.     ++fmin;
  201.       if (fmax < dmax)
  202.     fd[++fmax + 1] = -1;
  203.       else
  204.     --fmax;
  205.       for (d = fmax; d >= fmin; d -= 2)
  206.     {
  207.       int x;
  208.       int y;
  209.       int oldx;
  210.       int tlo;
  211.       int thi;
  212.  
  213.       tlo = fd[d - 1],
  214.         thi = fd[d + 1];
  215.  
  216.       if (tlo >= thi)
  217.         x = tlo + 1;
  218.       else
  219.         x = thi;
  220.       oldx = x;
  221.       y = x - d;
  222.       while (x < xlim && y < ylim && xv[x] == yv[y])
  223.         {
  224.           ++x;
  225.           ++y;
  226.         }
  227.       if (x - oldx > SNAKE_LIMIT)
  228.         big_snake = 1;
  229.       fd[d] = x;
  230.       if (odd && bmin <= d && d <= bmax && bd[d] <= x)
  231.         {
  232.           part->xmid = x;
  233.           part->ymid = y;
  234.           part->lo_minimal = part->hi_minimal = 1;
  235.           return 2 * c - 1;
  236.         }
  237.     }
  238.       /* Similarly extend the bottom-up search.  */
  239.       if (bmin > dmin)
  240.     bd[--bmin - 1] = INT_MAX;
  241.       else
  242.     ++bmin;
  243.       if (bmax < dmax)
  244.     bd[++bmax + 1] = INT_MAX;
  245.       else
  246.     --bmax;
  247.       for (d = bmax; d >= bmin; d -= 2)
  248.     {
  249.       int x;
  250.       int y;
  251.       int oldx;
  252.       int tlo;
  253.       int thi;
  254.  
  255.       tlo = bd[d - 1],
  256.         thi = bd[d + 1];
  257.       if (tlo < thi)
  258.         x = tlo;
  259.       else
  260.         x = thi - 1;
  261.       oldx = x;
  262.       y = x - d;
  263.       while (x > xoff && y > yoff && xv[x - 1] == yv[y - 1])
  264.         {
  265.           --x;
  266.           --y;
  267.         }
  268.       if (oldx - x > SNAKE_LIMIT)
  269.         big_snake = 1;
  270.       bd[d] = x;
  271.       if (!odd && fmin <= d && d <= fmax && x <= fd[d])
  272.         {
  273.           part->xmid = x;
  274.           part->ymid = y;
  275.           part->lo_minimal = part->hi_minimal = 1;
  276.           return 2 * c;
  277.         }
  278.     }
  279.  
  280.       if (minimal)
  281.     continue;
  282.  
  283. #ifdef MINUS_H_FLAG
  284.       /* Heuristic: check occasionally for a diagonal that has made lots
  285.          of progress compared with the edit distance.  If we have any
  286.          such, find the one that has made the most progress and return
  287.          it as if it had succeeded.
  288.  
  289.          With this heuristic, for strings with a constant small density
  290.          of changes, the algorithm is linear in the strings size.  */
  291.       if (c > 200 && big_snake && heuristic)
  292.     {
  293.       int best;
  294.  
  295.       best = 0;
  296.       for (d = fmax; d >= fmin; d -= 2)
  297.         {
  298.           int dd;
  299.           int x;
  300.           int y;
  301.           int v;
  302.  
  303.           dd = d - fmid;
  304.           x = fd[d];
  305.           y = x - d;
  306.           v = (x - xoff) * 2 - dd;
  307.  
  308.           if (v > 12 * (c + (dd < 0 ? -dd : dd)))
  309.         {
  310.           if
  311.             (
  312.               v > best
  313.               &&
  314.               xoff + SNAKE_LIMIT <= x
  315.               &&
  316.               x < xlim
  317.               &&
  318.               yoff + SNAKE_LIMIT <= y
  319.               &&
  320.               y < ylim
  321.             )
  322.             {
  323.               /* We have a good enough best diagonal; now insist
  324.              that it end with a significant snake.  */
  325.               int k;
  326.  
  327.               for (k = 1; xv[x - k] == yv[y - k]; k++)
  328.             {
  329.               if (k == SNAKE_LIMIT)
  330.                 {
  331.                   best = v;
  332.                   part->xmid = x;
  333.                   part->ymid = y;
  334.                   break;
  335.                 }
  336.             }
  337.             }
  338.         }
  339.         }
  340.       if (best > 0)
  341.         {
  342.           part->lo_minimal = 1;
  343.           part->hi_minimal = 0;
  344.           return 2 * c - 1;
  345.         }
  346.       best = 0;
  347.       for (d = bmax; d >= bmin; d -= 2)
  348.         {
  349.           int dd;
  350.           int x;
  351.           int y;
  352.           int v;
  353.  
  354.           dd = d - bmid;
  355.           x = bd[d];
  356.           y = x - d;
  357.           v = (xlim - x) * 2 + dd;
  358.  
  359.           if (v > 12 * (c + (dd < 0 ? -dd : dd)))
  360.         {
  361.           if (v > best && xoff < x && x <= xlim - SNAKE_LIMIT &&
  362.               yoff < y && y <= ylim - SNAKE_LIMIT)
  363.             {
  364.               /* We have a good enough best diagonal; now insist
  365.              that it end with a significant snake.  */
  366.               int k;
  367.  
  368.               for (k = 0; xv[x + k] == yv[y + k]; k++)
  369.             {
  370.               if (k == SNAKE_LIMIT - 1)
  371.                 {
  372.                   best = v;
  373.                   part->xmid = x;
  374.                   part->ymid = y;
  375.                   break;
  376.                 }
  377.             }
  378.             }
  379.         }
  380.         }
  381.       if (best > 0)
  382.         {
  383.           part->lo_minimal = 0;
  384.           part->hi_minimal = 1;
  385.           return 2 * c - 1;
  386.         }
  387.     }
  388. #endif /* MINUS_H_FLAG */
  389.  
  390.       /* Heuristic: if we've gone well beyond the call of duty, give up
  391.      and report halfway between our best results so far.  */
  392.       if (c >= too_expensive)
  393.     {
  394.       int fxybest;
  395.       int fxbest;
  396.       int bxybest;
  397.       int bxbest;
  398.  
  399.       /* Pacify `gcc -Wall'. */
  400.       fxbest = 0;
  401.       bxbest = 0;
  402.  
  403.       /* Find forward diagonal that maximizes X + Y.  */
  404.       fxybest = -1;
  405.       for (d = fmax; d >= fmin; d -= 2)
  406.         {
  407.           int x;
  408.           int y;
  409.  
  410.           x = fd[d] < xlim ? fd[d] : xlim;
  411.           y = x - d;
  412.  
  413.           if (ylim < y)
  414.         {
  415.           x = ylim + d;
  416.           y = ylim;
  417.         }
  418.           if (fxybest < x + y)
  419.         {
  420.           fxybest = x + y;
  421.           fxbest = x;
  422.         }
  423.         }
  424.       /* Find backward diagonal that minimizes X + Y.  */
  425.       bxybest = INT_MAX;
  426.       for (d = bmax; d >= bmin; d -= 2)
  427.         {
  428.           int x;
  429.           int y;
  430.  
  431.           x = xoff > bd[d] ? xoff : bd[d];
  432.           y = x - d;
  433.  
  434.           if (y < yoff)
  435.         {
  436.           x = yoff + d;
  437.           y = yoff;
  438.         }
  439.           if (x + y < bxybest)
  440.         {
  441.           bxybest = x + y;
  442.           bxbest = x;
  443.         }
  444.         }
  445.       /* Use the better of the two diagonals.  */
  446.       if ((xlim + ylim) - bxybest < fxybest - (xoff + yoff))
  447.         {
  448.           part->xmid = fxbest;
  449.           part->ymid = fxybest - fxbest;
  450.           part->lo_minimal = 1;
  451.           part->hi_minimal = 0;
  452.         }
  453.       else
  454.         {
  455.           part->xmid = bxbest;
  456.           part->ymid = bxybest - bxbest;
  457.           part->lo_minimal = 0;
  458.           part->hi_minimal = 1;
  459.         }
  460.       return 2 * c - 1;
  461.     }
  462.     }
  463. }
  464.  
  465.  
  466. /* NAME
  467.     compareseq - find edit sequence
  468.  
  469.    SYNOPSIS
  470.     void compareseq(int xoff, int xlim, int yoff, int ylim, int minimal);
  471.  
  472.    DESCRIPTION
  473.     Compare in detail contiguous subsequences of the two strings
  474.     which are known, as a whole, to match each other.
  475.  
  476.     The subsequence of string 0 is [XOFF, XLIM) and likewise for
  477.     string 1.
  478.  
  479.     Note that XLIM, YLIM are exclusive bounds.  All character
  480.     numbers are origin-0.
  481.  
  482.     If MINIMAL is nonzero, find a minimal difference no matter how
  483.     expensive it is.  */
  484.  
  485. static void compareseq PARAMS ((int, int, int, int, int));
  486.  
  487. static void
  488. compareseq (xoff, xlim, yoff, ylim, minimal)
  489.      int xoff;
  490.      int xlim;
  491.      int yoff;
  492.      int ylim;
  493.      int minimal;
  494. {
  495.   const char *const xv = string[0].data;    /* Help the compiler.  */
  496.   const char *const yv = string[1].data;
  497.  
  498.   /* Slide down the bottom initial diagonal. */
  499.   while (xoff < xlim && yoff < ylim && xv[xoff] == yv[yoff])
  500.     {
  501.       ++xoff;
  502.       ++yoff;
  503.     }
  504.  
  505.   /* Slide up the top initial diagonal. */
  506.   while (xlim > xoff && ylim > yoff && xv[xlim - 1] == yv[ylim - 1])
  507.     {
  508.       --xlim;
  509.       --ylim;
  510.     }
  511.  
  512.   /* Handle simple cases. */
  513.   if (xoff == xlim)
  514.     {
  515.       while (yoff < ylim)
  516.     {
  517.       ++string[1].edit_count;
  518.       ++yoff;
  519.     }
  520.     }
  521.   else if (yoff == ylim)
  522.     {
  523.       while (xoff < xlim)
  524.     {
  525.       ++string[0].edit_count;
  526.       ++xoff;
  527.     }
  528.     }
  529.   else
  530.     {
  531.       int c;
  532.       struct partition part;
  533.  
  534.       /* Find a point of correspondence in the middle of the strings.  */
  535.       c = diag (xoff, xlim, yoff, ylim, minimal, &part);
  536.       if (c == 1)
  537.     {
  538. #if 0
  539.       /* This should be impossible, because it implies that one of
  540.          the two subsequences is empty, and that case was handled
  541.          above without calling `diag'.  Let's verify that this is
  542.          true.  */
  543.       abort ();
  544. #else
  545.       /* The two subsequences differ by a single insert or delete;
  546.          record it and we are done.  */
  547.       if (part.xmid - part.ymid < xoff - yoff)
  548.         ++string[1].edit_count;
  549.       else
  550.         ++string[0].edit_count;
  551. #endif
  552.     }
  553.       else
  554.     {
  555.       /* Use the partitions to split this problem into subproblems.  */
  556.       compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal);
  557.       compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal);
  558.     }
  559.     }
  560. }
  561.  
  562.  
  563. /* NAME
  564.     fstrcmp - fuzzy string compare
  565.  
  566.    SYNOPSIS
  567.     double fstrcmp(const char *, const char *);
  568.  
  569.    DESCRIPTION
  570.     The fstrcmp function may be used to compare two string for
  571.     similarity.  It is very useful in reducing "cascade" or
  572.     "secondary" errors in compilers or other situations where
  573.     symbol tables occur.
  574.  
  575.    RETURNS
  576.     double; 0 if the strings are entirly dissimilar, 1 if the
  577.     strings are identical, and a number in between if they are
  578.     similar.  */
  579.  
  580. double
  581. fstrcmp (string1, string2)
  582.      const char *string1;
  583.      const char *string2;
  584. {
  585.   int i;
  586.  
  587.   size_t fdiag_len;
  588.   static int *fdiag_buf;
  589.   static size_t fdiag_max;
  590.  
  591.   /* set the info for each string.  */
  592.   string[0].data = string1;
  593.   string[0].data_length = strlen (string1);
  594.   string[1].data = string2;
  595.   string[1].data_length = strlen (string2);
  596.  
  597.   /* short-circuit obvious comparisons */
  598.   if (string[0].data_length == 0 && string[1].data_length == 0)
  599.     return 1.0;
  600.   if (string[0].data_length == 0 || string[1].data_length == 0)
  601.     return 0.0;
  602.  
  603.   /* Set TOO_EXPENSIVE to be approximate square root of input size,
  604.      bounded below by 256.  */
  605.   too_expensive = 1;
  606.   for (i = string[0].data_length + string[1].data_length; i != 0; i >>= 2)
  607.     too_expensive <<= 1;
  608.   if (too_expensive < 256)
  609.     too_expensive = 256;
  610.  
  611.   /* Because fstrcmp is typically called multiple times, while scanning
  612.      symbol tables, etc, attempt to minimize the number of memory
  613.      allocations performed.  Thus, we use a static buffer for the
  614.      diagonal vectors, and never free them.  */
  615.   fdiag_len = string[0].data_length + string[1].data_length + 3;
  616.   if (fdiag_len > fdiag_max)
  617.     {
  618.       fdiag_max = fdiag_len;
  619.       fdiag_buf = xrealloc (fdiag_buf, fdiag_max * (2 * sizeof (int)));
  620.     }
  621.   fdiag = fdiag_buf + string[1].data_length + 1;
  622.   bdiag = fdiag + fdiag_len;
  623.  
  624.   /* Now do the main comparison algorithm */
  625.   string[0].edit_count = 0;
  626.   string[1].edit_count = 0;
  627.   compareseq (0, string[0].data_length, 0, string[1].data_length, 0);
  628.  
  629.   /* The result is
  630.     ((number of chars in common) / (average length of the strings)).
  631.      This is admittedly biased towards finding that the strings are
  632.      similar, however it does produce meaningful results.  */
  633.   return ((double) (string[0].data_length + string[1].data_length -
  634.     string[1].edit_count - string[0].edit_count) / (string[0].data_length
  635.     + string[1].data_length));
  636. }
  637.