home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume8 / sp / part02 / sp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-02-19  |  8.9 KB  |  410 lines
  1. /* vi: set tabstop=4 : */
  2.  
  3. /*
  4.  * Version 1.3 December 1986
  5.  *
  6.  * sp - spell word
  7.  *
  8.  * Usage:    sp [-f dictionary-list] [-eavc] [word ...]
  9.  *
  10.  * Compute the Soundex code for each word on the command line
  11.  * (or each word on the standard input) and compare against a
  12.  * dictionary
  13.  *
  14.  * The soundex dictionary list may be specified on the command line
  15.  * The environment variable SPPATH may be set to a list of colon
  16.  * separated pathnames of soundex dictionaries.
  17.  * If a command line dictionary-list (a colon separated list of pathnames) is
  18.  * given in addition to the SPPATH variable, all dictionaries are used.
  19.  *
  20.  * To reduce the size of the word list, certain heuristics are used:
  21.  * the -a option causes all words matched to be printed
  22.  * The output is alphabetically sorted and indicators are printed
  23.  * beside each word:
  24.  *    X   == exact match
  25.  *    !   == close match
  26.  *    *   == near match
  27.  * ' '  == matched
  28.  *
  29.  * Note that the maximum number of colliding words is MAXCOUNT due to the
  30.  * data structure used.
  31.  *
  32.  * Permission is given to copy or distribute this program provided you
  33.  * do not remove this header or make money off of the program.
  34.  *
  35.  * Please send comments and suggestions to:
  36.  *
  37.  * Barry Brachman
  38.  * Dept. of Computer Science
  39.  * Univ. of British Columbia
  40.  * Vancouver, B.C. V6T 1W5
  41.  *
  42.  * .. {ihnp4!alberta, uw-beaver}!ubc-vision!ubc-cs!brachman
  43.  * brachman@cs.ubc.cdn
  44.  * brachman%ubc.csnet@csnet-relay.arpa
  45.  * brachman@ubc.csnet
  46.  */
  47.  
  48. #include <sys/types.h>
  49. #include <sys/file.h>
  50. #include <ctype.h>
  51. #include <stdio.h>
  52.  
  53. #ifdef NEWDBM
  54. #include <ndbm.h>
  55. #else !NEWDBM
  56. #include <dbm.h>
  57. #endif NEWDBM
  58.  
  59. #include "sp.h"
  60.  
  61. #define streq(X, Y)    (!strcmp(X, Y))
  62. #define range(S)    ((strlen(S) + 4) / 5)
  63.  
  64. #define USAGE        "Usage: sp [-f dictionary-list] [-eavc] [word ...]"
  65.  
  66. char word[MAXWORDLEN + 2];
  67.  
  68. datum FETCH();
  69.  
  70. char *fileptr[MAXDICT + 1];    /* Up to MAXDICT dictionaries + sentinel */
  71. int dict_ptr = 0;
  72.  
  73. char *wordptr[MAXWORDS], *wordlistptr;
  74. char wordlist[WORDSPACE];
  75. int nmatched;
  76.  
  77. /*
  78.  * Soundex codes
  79.  * The program depends upon the numbers zero through six being used
  80.  * but this can easily be changed
  81.  */
  82. char soundex_code_map[26] = {
  83. /***     A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P    ***/ 
  84.          0, 1, 2, 3, 0, 1, 2, 0, 0, 2, 2, 4, 5, 5, 0, 1,
  85.  
  86. /***     Q  R  S  T  U  V  W  X  Y  Z            ***/
  87.          2, 6, 2, 3, 0, 1, 0, 2, 0, 2
  88. };
  89.  
  90. int aflag, cflag, eflag, vflag;
  91.  
  92. main(argc, argv)
  93. int argc;
  94. char **argv;
  95. {
  96.     register int fflag, i;
  97.     register char *p;
  98.     char *getenv();
  99.  
  100.     argc--; argv++;
  101.     fileptr[0] = (char *) NULL;
  102.     while (argc > 0 && argv[0][0] == '-') {
  103.         fflag = 0;        /* to break out of following loop... */
  104.         for (i = 1; argv[0][i] != '\0' && fflag == 0; i++) {
  105.             switch (argv[0][i]) {
  106.             case 'a':
  107.                 aflag = 1;
  108.                 break;
  109.             case 'c':
  110.                 cflag = 1;
  111.                 break;
  112.             case 'e':
  113.                 eflag = 1;
  114.                 break;
  115.             case 'f':
  116.                 if (argc == 1) {
  117.                     fprintf(stderr, "%s\n", USAGE);
  118.                     exit(1);
  119.                 }
  120.                 mkfilelist(argv[1]);
  121.                 argc--;
  122.                 argv++;
  123.                 fflag = 1;        /* break out of loop */
  124.                 break;
  125.             case 'v':
  126.                 vflag = 1;
  127.                 break;
  128.             default:
  129.                 fprintf(stderr, "%s\n", USAGE);
  130.                 exit(1);
  131.             }
  132.         }
  133.         argc--, argv++;
  134.     }
  135.  
  136.     if ((p = getenv("SPPATH")) != (char *) NULL)
  137.         mkfilelist(p);
  138.     if (fileptr[0] == (char *) NULL)
  139.         mkfilelist(DEFAULT_SPPATH);
  140.     if (vflag) {
  141.         printf("Using dictionaries:\n");
  142.         for (i = 0; fileptr[i] != (char *) NULL; i++)
  143.             if (strlen(fileptr[i]) > 0)
  144.                 printf("\t%s\n", fileptr[i]);
  145.     }
  146.     if (argc) {
  147.         for (i = 0; i < argc; i++) {
  148.             if (!eflag)
  149.                 printf("%s:\n", argv[i]);
  150.             apply(argv[i]);
  151.             if (!eflag)
  152.                 printf("\n");
  153.         }
  154.     }
  155.     else {
  156.         int ch, len;
  157.  
  158.         while (1) {
  159.             printf("Word? ");
  160.             if (fgets(word, sizeof(word), stdin) == (char *) NULL) {
  161.                 printf("\n");
  162.                 break;
  163.             }
  164.             len = strlen(word);
  165.             if (word[len - 1] != '\n') {
  166.                 fprintf(stderr, "sp: Word too long: %s", word);
  167.                 while ((ch = getchar()) != '\n')    /* flush rest of line */
  168.                     putc(ch, stderr);
  169.                 putc('\n', stderr);
  170.                 continue;
  171.             }
  172.             word[--len] = '\0';
  173.             if (len > MAXWORDLEN) {
  174.                 fprintf(stderr, "sp: Word too long: %s\n", word);
  175.                 continue;
  176.             }
  177.  
  178.             apply(word);
  179.             if (!eflag)
  180.                 printf("\n");
  181.         }
  182.     }
  183. }
  184.  
  185. /*
  186.  * Apply the Soundex search for a word to each dictionary in turn
  187.  * Note that 'DBMINIT' opens both the '.dir' and the '.pag' files
  188.  * and we must close them to avoid running out of file descriptors
  189.  *
  190.  * This routine gets called each time a word is looked up and therefore
  191.  * the dbm files may be repeatedly opened and closed.  Since the vast majority
  192.  * of the time this program is invoked for just a single word it doesn't seem
  193.  * worthwhile to do the right thing by saving file descriptors/DBM pointers.
  194.  * There probably won't be more than two dictionaries in use anyway.
  195.  */
  196. apply(word)
  197. char *word;
  198. {
  199.     register int code, i, nodicts;
  200.  
  201.     nmatched = 0;
  202.     wordlistptr = wordlist;
  203.     if ((code = soundex(word, 3)) == BAD_WORD)
  204.         return;
  205.     nodicts = 1;
  206.     for (i = 0; fileptr[i] != (char *) NULL; i++) {
  207.         if (strlen(fileptr[i]) == 0)
  208.             continue;
  209.         if (DBMINIT(fileptr[i], O_RDONLY) != -1) {
  210.             proc(code);
  211.             nodicts = 0;
  212.         }
  213.         DBMCLOSE();
  214.     }
  215.     if (nodicts) {
  216.         fprintf(stderr, "sp: Can't open any dictionaries\n");
  217.         exit(1);
  218.     }
  219.     if (vflag && !eflag && nmatched == 0)
  220.         printf("%s: no match\n", word);
  221.     else
  222.         choose(word);
  223. }
  224.  
  225. /*
  226.  * Look the word up in the current dictionary
  227.  * and save all the matches
  228.  * Note that only three digits are of the Soundex code are stored
  229.  * in a dictionary
  230.  */
  231. proc(soundex)
  232. int soundex;
  233. {
  234.     register int c, len;
  235.     datum dbm_key, dbm_content;
  236.     key_t *key, keyvec[KEYSIZE];
  237.     char *mk_word(), *p;
  238.  
  239.     key = keyvec;
  240.     dbm_key.dptr = (char *) key;
  241.     dbm_key.dsize = KEYSIZE;
  242.     c = 0;
  243.     while (1) {
  244.         mk_key(key, soundex, c);
  245.         dbm_content = FETCH(dbm_key);
  246.  
  247.         if (dbm_content.dptr == 0)
  248.             break;
  249.  
  250.         if (IS_DELETED(dbm_content)) {
  251.             if (++c > MAXCOUNT) {
  252.                 fprintf(stderr, "sp: entry count overflow\n");
  253.                 exit(1);
  254.             }
  255.             continue;
  256.         }
  257.  
  258.         if (nmatched == MAXWORDS) {
  259.             fprintf(stderr, "sp: Too many matches\n");
  260.             exit(1);
  261.         }
  262.  
  263.         p = mk_word(dbm_content.dptr, dbm_content.dsize, soundex);
  264.         len = strlen(p);
  265.         if (wordlistptr + len >= &wordlist[WORDSPACE]) {
  266.             fprintf(stderr, "sp: Out of space for words\n");
  267.             exit(1);
  268.         }
  269.         strncpy(wordlistptr, p, len);
  270.         wordlistptr[len] = '\0';
  271.         wordptr[nmatched++] = wordlistptr;
  272.         wordlistptr += len + 1;
  273.         if (++c > MAXCOUNT) {
  274.             fprintf(stderr, "sp: entry count overflow\n");
  275.             exit(1);
  276.         }
  277.     }
  278. }
  279.  
  280. /*
  281.  * Select and print those words which we consider
  282.  * to have matched 'word'
  283.  */
  284. choose(word)
  285. register char *word;
  286. {
  287.     register int c, code, i, len, mcount, wordlen;
  288.     register char *p;
  289.     int compar();
  290.  
  291.     code = soundex(word, 4);
  292.     qsort(wordptr, nmatched, sizeof(char *), compar);
  293.     c = range(word);
  294.     wordlen = strlen(word);
  295.     mcount = 0;
  296.     for (i = 0; i < nmatched; i++) {
  297.         p = wordptr[i];
  298.         if (strmatch(word, p) == 0) {
  299.             printf("X");
  300.             if (eflag) {
  301.                 printf(" %s\n", word);
  302.                 return;
  303.             }
  304.         }
  305.         else if (eflag)
  306.             continue;
  307.         else if (soundex(p, 4) == code)
  308.             printf("!");
  309.         else if (aflag &&
  310.             (wordlen < (len = strlen(p)) - c || len > wordlen + c))
  311.             printf(" ");
  312.         else if (!cflag)
  313.             printf("*");
  314.         else
  315.             continue;
  316.         printf("%3d. %s\n", mcount + 1, p);
  317.         mcount++;
  318.     }
  319.     if (vflag)
  320.         printf("(%d total matches)\n", nmatched);
  321. }
  322.  
  323. /*
  324.  * Compute an 'n' digit Soundex code for 'word' 
  325.  * See mksp.c
  326.  */
  327. soundex(word, n)
  328. register char *word;
  329. int n;
  330. {
  331.     register int c, digit_part, previous_code, soundex_length;
  332.     register char *p, *w;
  333.     char wcopy[MAXWORDLEN + 2];
  334.  
  335.     strcpy(wcopy, word);
  336.     p = w = wcopy;
  337.     while (*p != '\0') {
  338.         if (isupper(*p))
  339.             *p = tolower(*p);
  340.         p++;
  341.     }
  342.     if (!isalpha(*w)) {
  343.         fprintf(stderr, "sp: Improper word: %s\n", word);
  344.         return(BAD_WORD);
  345.     }
  346.     digit_part = 0;
  347.     soundex_length = 0;
  348.     previous_code = soundex_code_map[*w - 'a'];
  349.     for (p = w + 1; *p != '\0' && soundex_length < n; p++) {
  350.         if (!isalpha(*p))
  351.             continue;
  352.         c = soundex_code_map[*p - 'a'];
  353.         if (c == 0 || previous_code == c) {
  354.             previous_code = c;
  355.             continue;
  356.         }
  357.         digit_part = digit_part * 7 + c;
  358.         previous_code = c;
  359.         soundex_length++;
  360.     }
  361.     while (soundex_length++ < n)
  362.         digit_part *= 7;
  363.     return((digit_part << 5) + *w - 'a');
  364. }
  365.  
  366. /*
  367.  * Process a path string (environment variable SPPATH, DEFAULT_SPPATH, or an
  368.  * arg) by separating the pathnames into strings pointed to by elements
  369.  * of 'fileptr'
  370.  * End of list indicated by fileptr entry of NULL
  371.  *
  372.  * No attempt made to ignore duplicate pathnames
  373.  */
  374. mkfilelist(p)
  375. register char *p;
  376. {
  377.     register int len;
  378.     register char *path, *start;
  379.     char *malloc();
  380.  
  381.     while (*p != '\0' && dict_ptr < MAXDICT) {
  382.         start = p;
  383.         while (*p != ':' && *p != '\0')
  384.             p++;
  385.         if (start == p && *p == ':') {    /* colon with nothing else */
  386.             p++;
  387.             continue;
  388.         }
  389.         len = p - start;
  390.         path = (char *) malloc((unsigned) (len + 1));
  391.         if (path == (char *) NULL) {
  392.             fprintf(stderr, "sp: Out of dictionary space\n");
  393.             exit(1);
  394.         }
  395.         strncpy(path, start, len);
  396.         path[len] = '\0';
  397.         fileptr[dict_ptr++] = path;
  398.     }
  399.     fileptr[dict_ptr] = (char *) NULL;
  400. }
  401.  
  402. compar(p, q)
  403. char **p, **q;
  404. {
  405.  
  406.     return(strmatch(*p, *q));
  407. /*    return(strcmp(*p, *q)); */    /* use if you prefer case sensitive */
  408. }
  409.  
  410.