home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD1.mdf / magazine / drdobbs / 1988 / 11 / letters.asc < prev    next >
Text File  |  1988-10-21  |  4KB  |  205 lines
  1. _LETTERS_
  2.  
  3.  
  4. [LISTING ONE]
  5.  
  6. #include <string.h>
  7.  
  8. int stcknum;
  9. char *ststr1l[26];
  10. char *ststr2l[26];
  11. char *ststr1r[26];
  12. char *ststr2r[26];
  13.  
  14. int simil (str1, str2)    /*`Pattern Matching by Gestalt' */
  15. char *str1, *str2;        /*by John W. Ratcliff           */
  16.                           /*Dr. Dobb's Journal #141.      */
  17. {                         /*July 1988                     */
  18.     int len1;
  19.     int len2;
  20.     int ncmp;
  21.     int score;
  22.     char *di;
  23.     char *si;
  24.     char *de;
  25.     char *se;
  26.     char *cl1
  27.     char *cl2;
  28.     char *cr1;
  29.     char *cr2;
  30.  
  31.     score = 0;
  32.     stcknum = 0;
  33.  
  34.     len1 = strlen(str1);
  35.     len2 = strlen(str2);
  36.     if (len1 == 0 || len2 == 0)
  37.        return (score);
  38.  
  39.     pushst (str1, str1+len1-1, str2, str2+len2-1);
  40.  
  41.     while (stcknum != 0)
  42.     {
  43.         popst (&si, &se, &di, &de);
  44.         cl1 = si;
  45.         cl2 = di;
  46.         cr1 = se;
  47.         cr2 = de;
  48.         if ((ncmp=compare (&si, &se, &di, &de)) !=0)
  49.         {
  50.             score += ncmp*2;
  51.             if (cl1 != si    && cl2 != di   &&
  52.                (cl1 != si-1  || c12 != di-1))
  53.                pushst (cl1, si-1, cl2, di-1);
  54.             if (se    != cr1 && de    != cr2 &&
  55.                (se+1  != cr1 || de+1  != cr2))
  56.                pushst   (se+1, cr1, de+1, cr2);
  57.          }
  58.      }
  59.      return  (100*score/(len1+len2));
  60. }
  61.  
  62. int compare (si, se, di, de)
  63. char **si;
  64. char **se;
  65. char **di;
  66. char **de;
  67. {
  68.   int maxchars;
  69.   int l;
  70.   int len1;
  71.   char *i;
  72.   char *j;
  73.   char *m;
  74.   char *n;
  75.   char *s2end;
  76.   char *cl1;
  77.   char *cl2;
  78.   char *cr1;
  79.   char *cr2;
  80.  
  81.   maxchars = 0
  82.   for (i=(*si); i <= *se-maxchars; i++)
  83.   {
  84.       len1 + *se - i;
  85.       for (j=(*di); j <= *de-maxchars; j++)
  86.       {
  87.          s2end = j + len1;
  88.          if (s2end > *de)
  89.              s2end = *de;
  90.          for (m=i,n=j,l=0;  *m==*n && n <=s2end; m++,n++)
  91.              l++;
  92.          if (1 > 0)
  93.          {
  94.             if (l <= maxchars)
  95.             {
  96.                 j += l-1;
  97.             }
  98.             else
  99.             {
  100.                 cl1 = i;
  101.                 cl2 = j;
  102.                 maxchars = 1;
  103.                 l--;
  104.                 j += l;
  105.                 cr2 = j;
  106.                 cr1 = i+l;
  107.              }
  108.          }
  109.       }
  110.   }
  111.   *si = cl1;
  112.   *se = cr1;
  113.   *di = cl2;
  114.   *de = cr2;
  115.   return (maxchars);
  116. }
  117.  
  118. pushst (si, se, di, de)
  119. char *si;
  120. char *se;
  121. char *di;
  122. char *de;
  123. {
  124.    ststr1l[stcknum] = si;
  125.    ststr1r[stcknum] = se;
  126.    ststr2l[stcknum] = di;
  127.    ststr2r[stcknum] = de;
  128.    stcknum++;
  129. }
  130.  
  131. popst (si, se, di, de)
  132. char **si;
  133. char **se;
  134. char **di;
  135. char **de;
  136. {
  137.     stcknum--;
  138.     *si = ststr1l[stcknum];
  139.     *se = ststr1r[stcknum];
  140.     *di = ststr2l[stcknum];
  141.     *de = ststr2r[stcknum];
  142. }
  143.  
  144.  
  145.  
  146.  
  147. [LISTING TWO] 
  148.  
  149. int simil (s1, s2)
  150. /* Ratcliff/Obershelp Pattern Matching */
  151. char *1, *2;
  152. {
  153.   short l1, l2;
  154.  
  155.   l1 = strlen(s1);
  156.   l2 = strlen(s2);
  157.  
  158.   if (l1 == 1)                 /* check for the easiest case */
  159.     if (l2 == 1)
  160.       if (*s1 == *s2)
  161.         return(100);
  162.  
  163.   return(200 * GCsubstr(s1, s1 + l1, s2, s2 + l2) / (l1 + l2));
  164. }
  165.  
  166. int GCsubstr(st1, end1, st2, end2)
  167. /* recursive greatest common sub-string */
  168. char *st1, *end1, *st2, *end2;
  169. {
  170.   register char *a1, *b1, *s1, *a2, *b2, *s2;
  171.   short max, i;
  172.  
  173.   if (end1 <= st1)              /* s1 empty */
  174.     return (0);
  175.   if (end2 <= st2)              /* s2 empty */
  176.     return (0);
  177.   if (end1 == st1 + 1)          /* s1 has one char, */
  178.     if (end2 == st2 + 1)        /* and s2 has one char. */
  179.       return(0);                /* They cannot be equal. */
  180.  
  181.   max = 0;
  182.   b1 = end1; b2 = end2;
  183.  
  184.   for (a1 = st1; a1 < b1; a1++)
  185.     for (a2 = st2; a2 < b2; a2++)
  186.       if (*a1 == *a2)
  187.         {               /* How long is the common sub-string? */
  188.         for (i = 1; a1[i] && (a1[i] == a2[i]); i++)
  189.           ;
  190.         if (i > max)
  191.           {
  192.           max = i; s1 = a1; s2 = a2;
  193.           b1 = end1 - max; b2 = end2 - max;
  194.           }
  195.         }
  196.   if (! max)
  197.     return (0);
  198.   
  199.   max += GCsubstr(s1 + max, end1, s2 + max, end2);        /* RHS */
  200.   max += GCsubstr(st1, s1, st2, s2);                      /* LHS */
  201.   
  202.   return(max);
  203. }
  204.  
  205.