home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1995 August / NEBULA.mdf / SourceCode / libcs / srchscore.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-12-11  |  3.7 KB  |  133 lines
  1. /*
  2.  * Copyright (c) 1990 Carnegie Mellon University
  3.  * All Rights Reserved.
  4.  * 
  5.  * Permission to use, copy, modify and distribute this software and its
  6.  * documentation is hereby granted, provided that both the copyright
  7.  * notice and this permission notice appear in all copies of the
  8.  * software, derivative works or modified versions, and any portions
  9.  * thereof, and that both notices appear in supporting documentation.
  10.  *
  11.  * THE SOFTWARE IS PROVIDED "AS IS" AND CARNEGIE MELLON UNIVERSITY
  12.  * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING ALL
  13.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.  IN NO EVENT
  14.  * SHALL CARNEGIE MELLON UNIVERSITY BE LIABLE FOR ANY SPECIAL, DIRECT,
  15.  * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER
  16.  * RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF
  17.  * CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
  18.  * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  19.  *
  20.  * Users of this software agree to return to Carnegie Mellon any
  21.  * improvements or extensions that they make and grant Carnegie the
  22.  * rights to redistribute these changes.
  23.  *
  24.  * Export of this software is permitted only after complying with the
  25.  * regulations of the U.S. Deptartment of Commerce relating to the
  26.  * Export of Technical Data.
  27.  */
  28. /*  srchscore --  perform approximate string matching
  29.  *
  30.  *  int srchscore (big,small);
  31.  *  tells how well "small" matches substrings of "big".
  32.  *  The score ranges from 0 to (strlen(small) ** 2).
  33.  *  The score is something like the sum, over the longest
  34.  *  matching contiguous substrings, of the square of the
  35.  *  length of the substring minus some penalty for
  36.  *  not-quite-exactly-matching substrings.  Case is not significant.
  37.  *
  38.  *  The value ranges from 0 to strlen(small)**2.
  39.  *
  40.  * HISTORY
  41.  * $Log:    srchscore.c,v $
  42.  * Revision 1.2  90/12/11  17:59:18  mja
  43.  *     Add copyright/disclaimer for distribution.
  44.  * 
  45.  * 06-Feb-81  Steven Shafer (sas) at Carnegie-Mellon University
  46.  *    Added limit before "return" so value is never negative.
  47.  *
  48.  * 23-Jan-80  Steven Shafer (sas) at Carnegie-Mellon University
  49.  *    Created.  The same as Dave McKeown's matching function from the
  50.  *    PDP-11; only the identifiers have been changed to protect somebody.
  51.  *
  52.  */
  53.  
  54. #define INSERTCOST 1    /* penalty to insert 1 char in small */
  55. #define DELETECOST 1    /* penalty to delete 1 char from small */
  56. #define CHANGECOST 3    /* penalty to change 1 char in small */
  57.  
  58. static char *newsmall;    /* next character to match in "small" */
  59.  
  60. static int smatch (big,small)
  61. char *big,*small;
  62. {
  63.     register char *b,*s;    /* current chars in big and small */
  64.     register int goon;    /* TRUE while still looping */
  65.     int nmatch, penalty;    /* match count; total penalty */
  66.  
  67.     nmatch = 0;
  68.     penalty = 0;
  69.     goon = 1;
  70.     b = big;
  71.     s = small;
  72.  
  73.     while (*b && *s && goon) {
  74.         if (*b == *s) {
  75.             /* just do stuff at end of loop */
  76.         }
  77.         else if (*(b+1) == *s) {
  78.             b++;
  79.             penalty += INSERTCOST;
  80.         }
  81.         else if (*b == *(s+1)) {
  82.             s++;
  83.             penalty += DELETECOST;
  84.         }
  85.         else if (*(b+1) == *(s+1)) {
  86.             b++; s++;
  87.             penalty += CHANGECOST;
  88.         }
  89.         else {
  90.             goon = 0;
  91.         }
  92.         if (goon) {    /* something matched */
  93.             b++; s++;
  94.             nmatch++;
  95.         }
  96.     }
  97.     newsmall = s;
  98.     return ((nmatch * nmatch) - penalty);
  99. }
  100.  
  101. int srchscore (big,small)
  102. char *big,*small;
  103. {
  104.     register int score,bestscore,total;
  105.     char *b,*s,*bestsmall;
  106.  
  107.     total = 0;
  108.  
  109.     if (*big) {
  110.         s = small;
  111.         while (*s) {
  112.             bestscore = -1;
  113.             for (b=big; *b; b++) {
  114.                 score = smatch (b,s);
  115.                 if (score > bestscore) {
  116.                     bestscore = score;
  117.                     bestsmall = newsmall;
  118.                 }
  119.             }
  120.             if (bestsmall > s) {
  121.                 total += bestscore;
  122.                 s = bestsmall;
  123.             }
  124.             else {
  125.                 if (total >= DELETECOST-1)  total -= DELETECOST;
  126.                 s++;
  127.             }
  128.         }
  129.     }
  130.     if (total < 0)  total = 0;
  131.     return (total);
  132. }
  133.