home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume8 / sp / part01 / mksp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1987-02-19  |  12.5 KB  |  549 lines
  1. /* vi: set tabstop=4 : */
  2.  
  3. /*
  4.  * mksp - make soundex dictionary
  5.  * Version 1.3,  December 1986
  6.  *
  7.  * If <soundexfile.{dir, pag}> do not exist, try to create them
  8.  * If they do exist and are not empty, then words will be added
  9.  * from the standard input
  10.  * Only when words are being added to an existing database are duplicate words
  11.  * ignored
  12.  * Valid words (words beginning with an alphabetic) are stored as given but
  13.  * comparisons for duplicates is case independent.
  14.  * Non-alphabetic characters are ignored in computing the soundex
  15.  *
  16.  * Permission is given to copy or distribute this program provided you
  17.  * do not remove this header or make money off of the program.
  18.  *
  19.  * Please send comments and suggestions to:
  20.  * Barry Brachman
  21.  * Dept. of Computer Science
  22.  * Univ. of British Columbia
  23.  * Vancouver, B.C. V6T 1W5
  24.  *
  25.  * .. {ihnp4!alberta, uw-beaver}!ubc-vision!ubc-cs!brachman
  26.  * brachman@cs.ubc.cdn
  27.  * brachman%ubc.csnet@csnet-relay.arpa
  28.  * brachman@ubc.csnet
  29.  */
  30.  
  31. #include <ctype.h>
  32. #include <errno.h>
  33. #include <sys/types.h>
  34. #include <sys/file.h>
  35. #include <sys/stat.h>
  36. #include <stdio.h>
  37.  
  38. #ifdef NEWDBM
  39. #include <ndbm.h>
  40. #include <sys/file.h>
  41. #else !NEWDBM
  42. #include <dbm.h>
  43. #endif NEWDBM
  44.  
  45. #include "sp.h"
  46.  
  47. #define NEW_DICT            0
  48. #define OLD_DICT            1
  49.  
  50. #define VFREQ                1000    /* frequency for verbose messages */
  51.  
  52. #define streq(X, Y)            (!strcmp(X, Y))
  53. #define strneq(X, Y, N)        (!strncmp(X, Y, N))
  54.  
  55. #define USAGE                "Usage: mksp -tad [-v[#]] <soundexfile>"
  56.  
  57. int map[26][667];
  58.  
  59. datum FETCH(), FIRSTKEY(), NEXTKEY();
  60.  
  61. key_t keyvec[KEYSIZE];
  62. key_t *key = keyvec;
  63.  
  64. /*
  65.  * Soundex codes
  66.  * The program depends upon the numbers zero through six being used
  67.  * but this can easily be changed
  68.  */
  69. char soundex_code_map[26] = {
  70. /***     A  B  C  D  E  F  G  H  I  J  K  L  M  N  O  P    ***/ 
  71.          0, 1, 2, 3, 0, 1, 2, 0, 0, 2, 2, 4, 5, 5, 0, 1,
  72.  
  73. /***     Q  R  S  T  U  V  W  X  Y  Z            ***/
  74.          2, 6, 2, 3, 0, 1, 0, 2, 0, 2
  75. };
  76.  
  77. int digit_part;
  78.  
  79. int aflag, dflag, tflag, vflag;
  80.  
  81. char *mk_word();
  82.  
  83. main(argc, argv)
  84. int argc;
  85. char **argv;
  86. {
  87.     register int i;
  88.     char *file;
  89.  
  90.     if (argc != 3 && argc != 4) {
  91.         fprintf(stderr, "%s\n", USAGE);
  92.         exit(1);
  93.     }
  94.     aflag = dflag = tflag = vflag = 0;
  95.     file = (char *) NULL;
  96.  
  97.     for (i = 1; i < argc; i++) {
  98.         if (streq(argv[i], "-a"))
  99.             aflag = 1;
  100.         else if (streq(argv[i], "-d"))
  101.             dflag = 1;
  102.         else if (streq(argv[i], "-t"))
  103.             tflag = 1;
  104.         else if (strneq(argv[i], "-v", 2)) {
  105.             if (isdigit(argv[i][2]))
  106.                 vflag = atoi(&argv[i][2]);
  107.             else
  108.                 vflag = 1;
  109.         }
  110.         else if (file == (char *) NULL)
  111.             file = argv[i];
  112.         else {
  113.             fprintf(stderr, "%s\n", USAGE);
  114.             exit(1);
  115.         }
  116.     }
  117.  
  118.     if (file == (char *) NULL || (tflag + aflag + dflag) != 1) {
  119.         fprintf(stderr, "%s\n", USAGE);
  120.         exit(1);
  121.     }
  122.  
  123.     if (aflag) {
  124.         addwords(file);
  125.         if (vflag > 1) {
  126.             register int j, total;
  127.             int m, max;
  128.  
  129.             fprintf(stderr, "Counters:\n");
  130.             for (i = 0; i < 26; i++) {
  131.                 total = max = map[i][0];
  132.                 for (j = 1; j < 667; j++) {
  133.                     total += (m = map[i][j]);
  134.                     if (m > max)
  135.                         max = m;
  136.                 }
  137.                 if (max > 0)
  138.                     fprintf(stderr, "%c: max %d total %d\n", 'a'+i, max, total);
  139.             }
  140.         }
  141.     }
  142.     else if (dflag)
  143.         deletewords(file);
  144.     else if (tflag)
  145.         prcontents(file);
  146.     exit(0);
  147. }
  148.  
  149. /*
  150.  * Add words read from stdin to the database
  151.  * The key is the 3 digit soundex code for the word plus a disambiguating
  152.  * counter.  Different counter values are used for words with the same soundex
  153.  * code.  The maximum counter value is MAXCOUNT.  If the counter overflows then
  154.  * we lose, but given at least 8 bits this seems unlikely.
  155.  */
  156. addwords(name)
  157. char *name;
  158. {
  159.     register int c, count, delete, duplicate, i, len;
  160.     register int *p;
  161.     int ch, s, status;
  162.     char wcopy[MAXWORDLEN + 2], word[MAXWORDLEN + 2];
  163.     datum dbm_key, dbm_content;
  164.  
  165.     status = setup(name);
  166.     if (DBMINIT(name, O_RDWR) == -1) {
  167.         fprintf(stderr, "mksp: Can't initialize\n");
  168.         exit(1);
  169.     }
  170.  
  171.     for (i = 0; i < 26; i++)
  172.         for (c = 0; c < 667; c++)
  173.             map[i][c] = 0;
  174.  
  175.     dbm_key.dptr = (char *) key;
  176.     dbm_key.dsize = KEYSIZE;
  177.  
  178.     count = 0;
  179.  
  180.     while (fgets(word, sizeof(word), stdin) != (char *) NULL) {
  181.         len = strlen(word);
  182.         if (word[len - 1] != '\n') {
  183.             fprintf(stderr, "mksp: Word too long: %s", word);
  184.             while ((ch = getchar()) != '\n')    /* flush rest of line */
  185.                 putc(ch, stderr);
  186.             putc('\n', stderr);
  187.             continue;
  188.         }
  189.         word[--len] = '\0';
  190.         if (len > MAXWORDLEN) {
  191.             fprintf(stderr, "mksp: Word too long: %s\n", word);
  192.             continue;
  193.         }
  194.  
  195.         if ((s = soundex(word, 3)) == BAD_WORD) {
  196.             if (vflag)
  197.                 fprintf(stderr, "Ignoring bad word: %s\n", word);
  198.             continue;
  199.         }
  200.         ch = (isupper(word[0]) ? tolower(word[0]) : word[0]) - 'a';
  201.         p = &(map[ch][digit_part]);
  202.  
  203.         /*
  204.          * If words are being added to an old dictionary,
  205.          * check for duplication and watch for a deleted entry
  206.          * The reason for only checking for duplicates in old dictionaries is
  207.          * that usually when you're creating a new dictionary the words are
  208.          * already sorted and unique and the creation of a large dictionary is
  209.          * slow enough already.
  210.          */
  211.         duplicate = 0;
  212.         delete = -1;            /* an 'impossible' counter */
  213.         if (status == OLD_DICT) {
  214.             c = 0;
  215.             while (1) {
  216.                 mk_key(key, s, c);
  217.                 dbm_content = FETCH(dbm_key);
  218.                 if (dbm_content.dptr == 0)
  219.                     break;
  220.  
  221.                 if (!IS_DELETED(dbm_content)) {
  222.                     char *str;
  223.  
  224.                     str = mk_word(dbm_content.dptr, dbm_content.dsize, s);
  225.                     if (strmatch(word, str) == 0) {
  226.                         duplicate = 1;
  227.                         if (vflag)
  228.                             fprintf(stderr, "duplicate: %s\n", word);
  229.                         break;
  230.                     }
  231.                 }
  232.                 else if (delete < 0)    /* choose delete nearest front */
  233.                     delete = c;
  234.  
  235.                 if (++c > MAXCOUNT) {
  236.                     fprintf(stderr, "mksp: Counter overflow\n");
  237.                     fprintf(stderr, "soundex: %c%d\n", ch+'a', b10(digit_part));
  238.                     exit(1);
  239.                 }
  240.             }
  241.             if (duplicate)
  242.                 continue;
  243.             *p = c;
  244.         }
  245.         if (*p > MAXCOUNT) {
  246.             fprintf(stderr, "mksp: Counter overflow\n");
  247.             fprintf(stderr, "soundex: %c%d\n", ch+'a', b10(digit_part));
  248.             exit(1);
  249.         }
  250.         mk_key(key, s, *p);
  251.         *p = *p + 1;
  252.         strcpy(wcopy, word);
  253.         if (len == 1) {
  254.             if (isupper(wcopy[0]))
  255.                 wcopy[0] |= UPPER_CHAR;
  256.             wcopy[0] |= SINGLE_CHAR;
  257.             dbm_content.dptr = wcopy;
  258.         }
  259.         else {
  260.             if (isupper(wcopy[1]))
  261.                 wcopy[1] = wcopy[1] - 'A' + 26;
  262.             else if (islower(wcopy[1]))
  263.                 wcopy[1] = wcopy[1] - 'a';
  264.             else if ((wcopy[1] = tospchar(wcopy[1])) == '\0') {
  265.                 fprintf(stderr, "Bogus second char: can't happen!\n");
  266.                 exit(1);
  267.             }
  268.             if (isupper(wcopy[0]))
  269.                 wcopy[1] = wcopy[1] | UPPER_CHAR;
  270.             dbm_content.dptr = wcopy + 1;
  271.             len--;
  272.         }
  273.         dbm_content.dsize = len;                    /* null not stored */
  274.         if (delete < 0) {
  275.             if (STORE(dbm_key, dbm_content) == -1) {
  276.                 fprintf(stderr, "mksp: Can't store\n");
  277.                 exit(1);
  278.             }
  279.         }
  280.         else {
  281.             if (vflag)
  282.                 fprintf(stderr, "reusing: %s\n", word);
  283.             mk_key(key, s, delete);
  284.             if (REPLACE(dbm_key, dbm_content) == -1) {
  285.                 fprintf(stderr, "mksp: Can't replace\n");
  286.                 exit(1);
  287.             }
  288.         }
  289.         count++;
  290.         if (vflag > 1)
  291.             fprintf(stderr, "%5d: %s(%d)\n", count, word, ex_count(key));
  292.         if (vflag && (count % VFREQ) == 0)
  293.             fprintf(stderr, "%5d: %s\n", count, word);
  294.     }
  295.     if (vflag)
  296.         fprintf(stderr, "%d words\n", count);
  297.     DBMCLOSE();
  298. }
  299.  
  300. /*
  301.  * Print out everything
  302.  */
  303. prcontents(name)
  304. char *name;
  305. {
  306.     register int s;
  307.     datum dbm_key, dbm_content;
  308.  
  309.     if (DBMINIT(name, O_RDONLY) == -1)
  310.         exit(1);
  311.  
  312.     dbm_key = FIRSTKEY();
  313.     while (dbm_key.dptr != NULL) {
  314.         dbm_content = FETCH(dbm_key);
  315.         if (dbm_content.dptr == 0)
  316.             break;                        /* ??? */
  317.  
  318.         if (vflag)
  319.             printf("%3d. ", ex_count((key_t *) dbm_key.dptr));
  320.         if (IS_DELETED(dbm_content)) {
  321.             if (vflag)
  322.                 printf("(deleted)\n");
  323.         }
  324.         else {
  325.             s = ex_soundex((key_t *) dbm_key.dptr);
  326.             printf("%s\n", mk_word(dbm_content.dptr, dbm_content.dsize, s));
  327.         }
  328.         dbm_key = NEXTKEY(dbm_key);
  329.     }
  330.     DBMCLOSE();
  331. }
  332.  
  333. /*
  334.  * When words are deleted they must be marked as such rather than deleted
  335.  * using DELETE().  This is because the sequence of counters must remain
  336.  * continuous.  If DELETE() is used then any entries with the same soundex
  337.  * but with a larger counter value would not be accessible.  This approach
  338.  * does cost some extra space but if an addition is made to the chain then
  339.  * a deleted counter slot will be reused.  Also, the storage used by the word
  340.  * should be made available to dbm.  This could be improved somewhat
  341.  * by actually using DELETE() on the last entry of the chain.
  342.  */
  343. deletewords(name)
  344. char *name;
  345. {
  346.     register int c, ch, len, s;
  347.     register char *p;
  348.     char word[MAXWORDLEN + 2];
  349.     datum dbm_key, dbm_content;
  350.  
  351.     if (DBMINIT(name, O_RDWR) == -1)
  352.         exit(1);
  353.  
  354.     while (fgets(word, sizeof(word), stdin) != (char *) NULL) {
  355.         len = strlen(word);
  356.         if (word[len - 1] != '\n') {
  357.             fprintf(stderr, "mksp: Word too long: %s", word);
  358.             while ((ch = getchar()) != '\n')    /* flush rest of line */
  359.                 putc(ch, stderr);
  360.             putc('\n', stderr);
  361.             continue;
  362.         }
  363.         word[--len] = '\0';
  364.         if (len > MAXWORDLEN) {
  365.             fprintf(stderr, "mksp: Word too long: %s\n", word);
  366.             continue;
  367.         }
  368.  
  369.         if ((s = soundex(word, 3)) == BAD_WORD) {
  370.             if (vflag)
  371.                 fprintf(stderr, "Bad word: %s\n", word);
  372.             continue;
  373.         }
  374.  
  375.         c = 0;
  376.         while (1) {
  377.             dbm_key.dptr = (char *) key;
  378.             dbm_key.dsize = KEYSIZE;
  379.             mk_key(key, s, c);
  380.             dbm_content = FETCH(dbm_key);
  381.             if (dbm_content.dptr == NULL) {
  382.                 if (vflag)
  383.                     fprintf(stderr, "Not found: %s\n", word);
  384.                 break;
  385.             }
  386.  
  387.             if (!IS_DELETED(dbm_content)) {
  388.                 p = mk_word(dbm_content.dptr, dbm_content.dsize, s);
  389.                 if (strmatch(word, p) == 0) {
  390.                     /*
  391.                      * Aside:
  392.                      * Since dptr points to static storage it must be reset
  393.                      * if we want to retain the old content (content.dptr=word)
  394.                      * This took a while to determine...
  395.                      * Anyhow, since there is no need to store the old word
  396.                      * we free up the space
  397.                      */
  398.                     dbm_content.dptr = "";
  399.                     dbm_content.dsize = 0;
  400.                     if (REPLACE(dbm_key, dbm_content) == -1)
  401.                         fprintf(stderr, "mksp: delete of '%s' failed\n", word);
  402.                     else if (vflag) {
  403.                         if (vflag > 1)
  404.                             fprintf(stderr, "%d. %s ", c, p);
  405.                         fprintf(stderr, "deleted\n");
  406.                     }
  407.                     break;
  408.                 }
  409.                 else if (vflag > 1)
  410.                     fprintf(stderr, "%d. %s\n", c, p);
  411.             }
  412.             else if (vflag > 1)
  413.                 fprintf(stderr, "%d. (deleted)\n", c);
  414.  
  415.             if (++c > MAXCOUNT) {
  416.                 ch = isupper(word[0]) ? tolower(word[0]) : word[0];
  417.                 fprintf(stderr, "mksp: Counter overflow\n");
  418.                 fprintf(stderr, "soundex: %c%d\n", ch, b10(digit_part));
  419.                 exit(1);
  420.             }
  421.         }
  422.     }
  423.     DBMCLOSE();
  424. }
  425.  
  426. /*
  427.  * Setup the dictionary files if necessary
  428.  */
  429. setup(name)
  430. char *name;
  431. {
  432.     register int s1, s2;
  433.  
  434.     s1 = check_dict(name, ".dir");
  435.     s2 = check_dict(name, ".pag");
  436.     if (s1 == NEW_DICT && s2 == NEW_DICT)
  437.         return(NEW_DICT);
  438.     return(OLD_DICT);
  439. }
  440.  
  441. /*
  442.  * Check if a dictionary file exists:
  443.  *    - if not, try to create it
  444.  *    - if so, see if it is empty
  445.  * Return NEW_DICT if an empty file exists,
  446.  * OLD_DICT if a non-empty file exists
  447.  * Default mode for new files is 0666
  448.  */
  449. check_dict(name, ext)
  450. char *name, *ext;
  451. {
  452.     register int len, s;
  453.     char *filename;
  454.     struct stat statbuf;
  455.     char *malloc();
  456.     extern int errno;
  457.  
  458.     len = strlen(name) + strlen(ext) + 1;
  459.     filename = (char *) malloc((unsigned) len);
  460.     if (filename == (char *) NULL) {
  461.         fprintf(stderr, "mksp: Can't malloc '%s.%s'\n", name, ext);
  462.         exit(1);
  463.     }
  464.     sprintf(filename, "%s%s", name, ext);
  465.     if (stat(filename, &statbuf) == -1) {
  466.         if (errno != ENOENT) {
  467.             perror("mksp");
  468.             exit(1);
  469.         }
  470.         if (creat(filename, 0666) == -1) {
  471.             perror("mksp");
  472.             exit(1);
  473.         }
  474.         s = NEW_DICT;
  475.     }
  476.     else {
  477.         if (statbuf.st_size == 0)
  478.             s = NEW_DICT;
  479.         else
  480.             s = OLD_DICT;
  481.     }
  482.     return(s);
  483. }
  484.  
  485. /*
  486.  * Compute an 'n' digit Soundex code for 'word' 
  487.  * As a side effect, leave the digit part of the soundex in digit_part
  488.  *
  489.  * Since the soundex can be considered a base 7 number, if 'n' is:
  490.  *    3    require  9 (10 if base 10) bits for digits
  491.  *    4    require 12 (13) bits
  492.  *    5    require 15 (17) bits
  493.  *    6    require 17 (20) bits
  494.  *
  495.  * The three slightly different versions of this routine should be coalesced.
  496.  */
  497. soundex(word, n)
  498. register char *word;
  499. int n;
  500. {
  501.     register int c, soundex_length, previous_code;
  502.     register char *p, *w;
  503.     char wcopy[MAXWORDLEN + 2];
  504.  
  505.     if (!IS_VALID(word))
  506.         return(-1);
  507.  
  508.     strcpy(wcopy, word);
  509.     p = w = wcopy;
  510.  
  511.     while (*p != '\0') {
  512.         if (isupper(*p))
  513.             *p = tolower(*p);
  514.         p++;
  515.     }
  516.  
  517.     digit_part = 0;
  518.     soundex_length = 0;
  519.     previous_code = soundex_code_map[*w - 'a'];
  520.     for (p = w + 1; *p != '\0' && soundex_length < n; p++) {
  521.         if (!isalpha(*p))
  522.             continue;
  523.         c = soundex_code_map[*p - 'a'];
  524.         if (c == 0 || previous_code == c) {
  525.             previous_code = c;
  526.             continue;
  527.         }
  528.         digit_part = digit_part * 7 + c;
  529.         previous_code = c;
  530.         soundex_length++;
  531.     }
  532.     while (soundex_length++ < n)
  533.         digit_part *= 7;
  534.     return((digit_part << 5) + *w - 'a');
  535. }
  536.  
  537. b10(n)
  538. int n;
  539. {
  540.     register int b10, s;
  541.  
  542.     for (b10 = 0, s = 1; n != 0; n /= 7) {
  543.         b10 += (n % 7) * s;
  544.         s *= 10;
  545.     }
  546.     return(b10);
  547. }
  548.  
  549.