home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 October / usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso / games / volume2 / autopun / autopun.c < prev    next >
C/C++ Source or Header  |  1987-11-25  |  14KB  |  597 lines
  1. /*
  2.  * autopun - Phrase reparser.
  3.  *
  4.  * Usage:
  5.  *    autopun [-e English_dict] [-p Phone_dict]
  6.  * or
  7.  *    autopun [-e English_dict] -c -p Phone_dict
  8.  *
  9.  * Given an English phrase (as stdin), autopun prints (to stdout) a table
  10.  * that can be used to create phonemically-similar phrases.  E.g.,
  11.  *  "Happy Birthday" can be recast as "Hub pip Earth tee".
  12.  */
  13.  
  14. #include <stdio.h>
  15. #include "phoneme.h"
  16. #define TRUE 1
  17. #define FALSE 0
  18.  
  19. char *cmd;                /* name of this program        */
  20. int phread = FALSE;            /* "read the phone dict"    */
  21. int phcreate = FALSE;            /* "create the phone dict"    */
  22. char *engldict = "/usr/dict/words";    /* English dictionary file    */
  23. char *phonedict;            /* phonemic dictionary file    */
  24. char *indictname;            /* name of the dict being read    */
  25. FILE *indict;                /* the open dict being read    */
  26. FILE *outdict;                /* the open dict being written    */
  27.                     /* ...name == phonedict        */
  28.  
  29. /*
  30.  * struct amatch - representation of the phonemic match of a word with
  31.  * some part of the phrase.
  32.  */
  33.  
  34. struct amatch {
  35.     struct amatch *next;    /* next word matching at this position    */
  36.     char *text;            /* English text of the matching word    */
  37.     short nextpos;        /* position of phoneme after this word    */
  38. };
  39.  
  40. /*
  41.  * struct posinfo - information about one phonemic position in the phrase.
  42.  */
  43.  
  44. struct posinfo {
  45.     struct amatch *wlist;    /* list of words that match at this point */
  46.     unsigned num_parents;    /* # of words leading directly to this point */
  47. };
  48.  
  49. /*
  50.  * posinfo[] - indexed by phoneme position in the phrase,
  51.  */
  52.  
  53. #define MAX_PHONES    300    /* Max # of phonemes in a phrase    */
  54. struct posinfo posinfo[MAX_PHONES];
  55.  
  56. short target[MAX_PHONES];    /* phonemes of the phrase to reparse    */
  57. int targlen;            /* # of phonemes in target[] (less P_end) */
  58.  
  59. /*
  60.  * phmap[] - phoneme map.  Maps a set of similar-sounding phonemes into one.
  61.  *  Used in preprocessing strings before comparison.
  62.  */
  63.  
  64. short phmap[P_NUM] = {
  65.     P_end,    /* P_end */
  66.     P_IY,    /* P_IY */
  67.     P_IY,    /* P_IH */
  68.     P_EY,    /* P_EY */
  69.     P_EY,    /* P_EH */
  70.     P_AE,    /* P_AE */
  71.     P_AE,    /* P_AA */
  72.     P_AE,    /* P_AO */
  73.     P_AE,    /* P_OW */
  74.     P_AE,    /* P_UH */
  75.     P_UW,    /* P_UW */
  76.     P_UW,    /* P_ER */
  77.     P_AE,    /* P_AX */
  78.     P_AE,    /* P_AH */
  79.     P_AY,    /* P_AY */
  80.     P_AE,    /* P_AW */
  81.     P_OY,    /* P_OY */
  82.     P_p,    /* P_p */
  83.     P_p,    /* P_b */
  84.     P_t,    /* P_t */
  85.     P_t,    /* P_d */
  86.     P_k,    /* P_k */
  87.     P_g,    /* P_g */
  88.     P_f,    /* P_f */
  89.     P_f,    /* P_v */
  90.     P_TH,    /* P_TH */
  91.     P_f,    /* P_DH */
  92.     P_s,    /* P_s */
  93.     P_s,    /* P_z */
  94.     P_s,    /* P_SH */
  95.     P_s,    /* P_ZH */
  96.     P_HH,    /* P_HH */
  97.     P_m,    /* P_m */
  98.     P_n,    /* P_n */
  99.     P_n,    /* P_NG */
  100.     P_l,    /* P_l */
  101.     P_l,    /* P_w */
  102.     P_y,    /* P_y */
  103.     P_r,    /* P_r */
  104.     P_CH,    /* P_CH */
  105.     P_CH,    /* P_j */
  106.     P_WH,    /* P_WH */
  107.     P_end    /* P_PAS */
  108. };
  109.  
  110. main(argc, argv)
  111. int argc;
  112. char **argv;
  113. {
  114.     char *cp;
  115.     char line[300];
  116.     char *strrchr();
  117.  
  118.     /*
  119.      * get the basename of the command name,
  120.      * for use in error messages.
  121.      */
  122.  
  123.     if ((cmd = strrchr(argv[0], '/'))) {
  124.     ++cmd;
  125.     } else {
  126.     cmd = argv[0];
  127.     }
  128.  
  129.     while (++argv, --argc > 0) {
  130.     cp = *argv;
  131.     if (*cp == '-' && *(cp + 1) != '\0') {
  132.         switch(*++cp) {
  133.         case 'c':    /* "create the phonemic dictionary */
  134.             /* (requires -p flag)           */
  135.         phcreate = TRUE;
  136.         break;
  137.         case 'p':    /* "filename of phonemic dictionary" */
  138.         if (++argv, --argc <= 0 ||
  139.           (**argv == '-' && *(*argv + 1) != '\0')) {
  140.             bomb("missing -p filename");
  141.         }
  142.         phonedict = *argv;
  143.         break;
  144.         case 'e':    /* "filename of English dictionary" */
  145.         if (++argv, --argc <= 0) {
  146.             bomb("missing -e filename");
  147.         }
  148.         engldict = *argv;
  149.         break;
  150.         default:
  151.         bomb("unknown switch `%c'", *cp);
  152.         }
  153.     } else {
  154.         bomb("extra filename `%s'", *argv);
  155.     }
  156.     }
  157.     if (phcreate && !phonedict) {
  158.     bomb("missing -p flag");
  159.     }
  160.     phread = (phonedict && !phcreate);
  161.  
  162.     /*
  163.      * open up the necessary files:
  164.      * Input is either an English or phonemic dictionary;
  165.      * Output is a phonemic dictionary (if requested).
  166.      */
  167.  
  168.     if (phread) {
  169.     indictname = phonedict;
  170.     } else {
  171.     indictname = engldict;
  172.     }
  173.     if (!(indict = fopen(indictname, "r"))) {
  174.     fprintf(stderr, "%s: can't open \"%s\" -- ", cmd, indictname);
  175.     perror("");
  176.     exit(1);
  177.     }
  178.  
  179.     if (phcreate) {
  180.     if (strcmp(indictname, phonedict) == 0) {
  181.         bomb("can't overwrite `%s'", phonedict);
  182.     }
  183.     if (!(outdict = fopen(phonedict, "w"))) {
  184.         fprintf(stderr, "%s: can't create \"%s\" -- ", cmd, phonedict);
  185.         perror("");
  186.         exit(1);
  187.     }
  188.     }
  189.  
  190.     /*
  191.      * Grab a phrase and process it.
  192.      */
  193.  
  194.     if (isatty(fileno(stdin))) {
  195.     fputs("Enter English text: ", stderr);
  196.     fflush(stderr);
  197.     }
  198.     if (fgets(line, 300, stdin)) {
  199.     line[strlen(line) - 1] = '\0';  /* removes the terminating \n */
  200.     reparse(line);
  201.     }
  202.  
  203.     /*
  204.      * Close up shop, making sure that any I/O errors are reported
  205.      */
  206.  
  207.     if (ferror(indict)) {
  208.     fprintf(stderr, "%s: problem reading \"%s\" -- ", cmd, indictname);
  209.     perror("");
  210.     exit(1);
  211.     }
  212.     (void) fclose(indict);
  213.     if (phcreate) {
  214.     if (fclose(outdict) != 0) {
  215.         fprintf(stderr, "%s: problem writing \"%s\" -- ", cmd, phonedict);
  216.         perror("");
  217.         exit(1);
  218.     }
  219.     }
  220.     exit(0);
  221. }
  222.  
  223. /*
  224.  * reparse() - given a line of English text, 
  225.  * Find and print the info necessary to reparse that line's phonemes
  226.  * into other English phrases.
  227.  */
  228.  
  229. reparse(text)
  230. char *text;
  231. {
  232.     char dictword[MAX_PHONES];    /* an English word from the dictionary          */
  233.     char *textcopy;        /* dynamic copy of the text              */
  234.     short phrase[MAX_PHONES];    /* the mapped, phonemic version of the phrase */
  235.     short testword[MAX_PHONES];    /* ditto for a word from the dictionary    */
  236.     int twordlen;        /* # of phonemes in testword[] (less P_end)   */
  237.     register short *sp, *dp;    /* temp source and dest phoneme pointers      */
  238.     int idx;            /* index where a match started              */
  239.     short *xlate_line();
  240.     short *mapphrase();
  241.     char *strsave();
  242.  
  243.     /*
  244.      * Translate the input phrase and copy it to a safe place.
  245.      */
  246.  
  247.     sp = xlate_line(text);
  248.     (void) mapphrase(sp);
  249.  
  250.     dp = target;
  251.     while (*sp != P_end) {
  252.     *dp++ = *sp++;
  253.     }
  254.     *dp = P_end;
  255.     targlen = dp - &target[0];
  256.  
  257.     /*
  258.      * For each word in the dictionary,
  259.      *   Convert that word into phonemic codes;
  260.      *   Write the converted codes to the phonemic dictionary (if necessary);
  261.      *   Record where that word would fit into the input phrase.
  262.      */
  263.  
  264.     while (fgets(dictword, MAX_PHONES, indict)) {
  265.     dictword[strlen(dictword) - 1] = '\0';
  266.  
  267.     if (phread) {
  268.         twordlen = encphones(dictword, testword);
  269.     } else {
  270.         sp = xlate_line(dictword);
  271.         twordlen = mapphrase(sp) - sp;
  272.         if (twordlen == 0) {
  273.         continue;            /* (loop leap) */
  274.         }
  275.         dp = testword;
  276.         while (*sp != P_end) {
  277.         *dp++ = *sp++;
  278.         }
  279.         *dp = P_end;
  280.  
  281.         if (phcreate) {
  282.         writephones(dictword, testword);
  283.         }
  284.     }
  285.  
  286.     /*
  287.      * Search for and record matches until
  288.      * one can't possibly exist (too few phonemes left).
  289.      */
  290.  
  291.     sp = target;
  292.     dp = &target[targlen];
  293.     textcopy = (char *) 0;
  294.     while (dp - sp >= twordlen &&
  295.       (idx = wordidx(sp, testword)) != -1) {
  296.         sp += idx + 1;
  297.         if (!textcopy) {
  298.         textcopy = strsave(dictword);
  299.         }
  300.         recmatch((sp - 1) - target, twordlen, textcopy);
  301.     }
  302.     }
  303.  
  304.     prune();
  305.     saymatches(text);
  306. }
  307.  
  308. /*
  309.  * prune() - prune away useless matches:
  310.  * remove potential matches that lead to unmatchable parts of the phrase;
  311.  * remove unreachable match lists.
  312.  */
  313.  
  314. prune()
  315. {
  316.     int pos;
  317.     struct amatch *prevm;
  318.     struct amatch *curm;
  319.  
  320.     /*
  321.      * note and remove all the matches that lead to an unmatchable point.
  322.      */
  323.  
  324.     for (pos = 0; pos < MAX_PHONES; ++pos) {
  325.     posinfo[pos].num_parents = 0;
  326.     }
  327.     for (pos = MAX_PHONES - 1; pos >= 0; --pos) {
  328.     prevm = (struct amatch *) 0;
  329.     curm = posinfo[pos].wlist;
  330.     while (curm) {
  331.  
  332.         /*
  333.          * If this word leads us to the end, everything is o.k.
  334.          * If this word leads us to a matchable point,
  335.          * note that we can reach that point.
  336.          * Otherwise, this word is a dead-end -- remove it.
  337.          */
  338.  
  339.         if (curm->nextpos >= targlen) {
  340.         prevm = curm;
  341.         } else if (posinfo[curm->nextpos].wlist) {
  342.         ++posinfo[curm->nextpos].num_parents;
  343.         prevm = curm;
  344.         } else {
  345.         if (!prevm) {
  346.             posinfo[pos].wlist = curm->next;
  347.         } else {
  348.             prevm->next = curm->next;
  349.         }
  350.         /* (we should free curm here if we are reclaiming space) */
  351.         }
  352.         curm = curm->next;
  353.     }
  354.     }
  355.  
  356.     /*
  357.      * Find and remove each unreachable point in the phrase
  358.      * (except the first one).
  359.      * This traversal cascades forward.
  360.      */
  361.  
  362.     for (pos = 1; pos < MAX_PHONES; ++pos) {
  363.     if (posinfo[pos].num_parents > 0) continue;
  364.     for (curm = posinfo[pos].wlist; curm; curm = curm->next) {
  365.         if (curm->nextpos >= targlen) continue;
  366.  
  367.         --posinfo[curm->nextpos].num_parents;
  368.     }
  369.     posinfo[pos].wlist = (struct amatch *) 0;
  370.     /* (if we were reclaiming space, here's where we'd do it */
  371.     }
  372. }
  373.  
  374. /*
  375.  * saymatches() - print the phrase match information table.
  376.  */
  377.  
  378. saymatches(text)
  379. char *text;        /* the original text    */
  380. {
  381.     int pos;
  382.     int curcol;
  383.     int addcols;
  384.     struct amatch *curm;
  385.  
  386.     printf("%s\n", text);
  387.     for (pos = 0; pos < MAX_PHONES; ++pos) {
  388.     if (!posinfo[pos].wlist) continue;
  389.     printf("%02d:\n", pos);
  390.     curcol = 0;
  391.     for (curm = posinfo[pos].wlist; curm; curm = curm->next) {
  392.         addcols = 1 + strlen(curm->text) + 1 + 2;
  393.         if (curcol + addcols >= 70) {
  394.         printf("\n");
  395.         curcol = 0;
  396.         }
  397.         if (curcol == 0) {
  398.         printf(" ");
  399.         curcol += 1;
  400.         }
  401.         printf(" %s:", curm->text);
  402.         if (curm->nextpos >= targlen) {
  403.         printf("$ ");
  404.         } else {
  405.         printf("%02d", curm->nextpos);
  406.         }
  407.         curcol += addcols;
  408.     }
  409.     printf("\n");
  410.     }
  411. }
  412.  
  413. /*
  414.  * mapphrase() - given a phonetic word or phrase, map it in place via phmap[],
  415.  * returning a pointer to the new end.
  416.  */
  417.  
  418. short *
  419. mapphrase(pp)
  420. short *pp;    /* a P_end-terminated word/phrase to map    */
  421. {
  422.     short *dp;    /* points to where to put the next phoneme    */
  423.  
  424.     dp = pp;
  425.     while (*pp != P_end) {
  426.     *dp = phmap[*pp];
  427.     if (*dp != P_end) ++dp;
  428.     ++pp;
  429.     }
  430.     *dp = P_end;
  431.     return(dp);
  432. }
  433.  
  434. /*
  435.  * wordidx() - given a phrase and a comparison word,
  436.  * return the index in the phrase where the word was found (-1 if not found).
  437.  *
  438.  * Wordidx() assumes both the phrase and the word have been mapped by phmap[].
  439.  */
  440.  
  441. int
  442. wordidx(phrase, word)
  443. short *phrase;        /* a P_end-terminated list of phonemes    */
  444. short *word;        /* ditto                */
  445. {
  446.     short *start;    /* the starting phoneme being compared        */
  447.     register short *pp;    /* the current phrase phoneme being compared    */
  448.     register short *wp;    /* the current word phoneme being compared    */
  449.  
  450.     for (start = phrase; *start != P_end; ++start) {
  451.     wp = word;
  452.     pp = start;
  453.     while (*wp != P_end) {
  454.         if (*pp != *wp) break;
  455.         ++pp, ++wp;
  456.     }
  457.     if (*wp == P_end) {
  458.         return(start - phrase);
  459.     }
  460.     }
  461.     return(-1);
  462. }
  463.  
  464. /*
  465.  * recmatch() - record a match.
  466.  */
  467.  
  468. recmatch(pos, phlen, text)
  469. int pos;        /* position of the match within the phrase    */
  470. int phlen;        /* # of phonemes matched            */
  471. char *text;        /* text that matched                */
  472. {
  473.     struct amatch *prevm;
  474.     struct amatch *newm;
  475.     struct amatch *nextm;
  476.     struct amatch *matchalloc();
  477.  
  478.     newm = matchalloc();
  479.     newm->text = text;
  480.     newm->nextpos = pos + phlen;
  481.  
  482.     prevm = (struct amatch *) 0;
  483.     for (nextm = posinfo[pos].wlist; nextm && newm->nextpos < nextm->nextpos;
  484.       prevm = nextm, nextm = nextm->next) {
  485.     /* (empty body) */
  486.     }
  487.  
  488.     if (!prevm) {
  489.     newm->next = posinfo[pos].wlist;
  490.     posinfo[pos].wlist = newm;
  491.     } else {
  492.     newm->next = prevm->next;
  493.     prevm->next = newm;
  494.     }
  495. }
  496.  
  497. /*
  498.  * writephones() - write a list of phonemes to a file.
  499.  */
  500.  
  501. writephones(ep, sp)
  502. char *ep;        /* english text         */
  503. short *sp;        /* corresponding phonemes    */
  504. {
  505.     fputs(ep, outdict);
  506.     putc(' ', outdict);
  507.     while (*sp != P_end) {
  508.     putc((int) *sp + (int) '!', outdict);
  509.     ++sp;
  510.     }
  511.     putc('\n', outdict);
  512.     if (ferror(outdict)) {
  513.     fprintf(stderr, "Error: problem writing \"%s\" -- ", phonedict);
  514.     perror("");
  515.     exit(1);
  516.     }
  517. }
  518.  
  519. /*
  520.  * encphones() - encode ascii from a phoneme file into phonetic codes.
  521.  */
  522.  
  523. int        /* returns # of phonemes in word[]        */
  524. encphones(text, word)
  525. register char *text;    /* encoded phonemes (less the newline) */
  526. short *word;        /* where to put the phonemes        */
  527. {
  528.     register short *sp;
  529.     char *strchr();
  530.  
  531.     /*
  532.      * separate the English text from its encoded form
  533.      */
  534.  
  535.     text = strchr(text, ' ');
  536.     *text++ = '\0';
  537.  
  538.     sp = word;
  539.     while (*text) {
  540.     *sp = (short) (*text - '!');
  541.     ++text, ++sp;
  542.     }
  543.     *sp = P_end;
  544.     return(sp - word);
  545. }
  546.  
  547. /*
  548.  * matchalloc() - allocate a new match element.
  549.  */
  550.  
  551. struct amatch *
  552. matchalloc()
  553. {
  554. #define MAX_MATCHES 1000    /* max # of matches in a phrase        */
  555.     static struct amatch matchpool[MAX_MATCHES];
  556.     static struct amatch *nextpool = matchpool;
  557.  
  558.     if (nextpool >= &matchpool[MAX_MATCHES]) {
  559.     fprintf(stderr, "Error: too many matches (over %d)\n", MAX_MATCHES);
  560.     exit(1);
  561.     }
  562.     return (nextpool++);
  563. }
  564.  
  565. /*
  566.  * strsave() - copy the given string to a malloc'ed area,
  567.  *  returning the resultant pointer.
  568.  */
  569.  
  570. char *
  571. strsave(s)
  572. char *s;
  573. {
  574.     char *ret;
  575.     char *malloc();
  576.  
  577.     if (!(ret = malloc(strlen(s) + 1))) {
  578.     fprintf(stderr, "Error: out of memory saving \"%s\"\n", s);
  579.     exit(1);
  580.     }
  581.     (void) strcpy(ret, s);
  582.     return(ret);
  583. }
  584.  
  585. /* VARARGS 1 */
  586. bomb(str, a1, a2, a3)
  587. char *str;
  588. int a1, a2, a3;
  589. {
  590.     fprintf(stderr, "%s: ", cmd);
  591.     fprintf(stderr, str, a1, a2, a3);
  592.     fprintf(stderr, "\n");
  593.     fprintf(stderr, "Usage:\n %s [-c] [-e English_dict] [-p Phone_dict]\n",
  594.       cmd);
  595.     exit(1);
  596. }
  597.