books/tpop/markov.c

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <stdlib.h>
   4 #include <time.h>
   5
   6 enum {
   7         NPREF  = 2,     /* number of prefix words */
   8         NHASH  = 4093,  /* size of state hash table array */
   9         MAXGEN = 10000  /* maximum words generated */
  10 };
  11
  12 typedef struct State State;
  13 typedef struct Suffix Suffix;
  14
  15 struct State { /* prefix + suffix list */
  16         char *pref[NPREF]; /* prefix words */
  17         Suffix *suf;       /* list of suffixes */
  18         State *next;       /* next in hash table */
  19 };
  20
  21 struct Suffix { /* list of suffixes */
  22         char *word;   /* suffix */
  23         Suffix *next; /* next in list of suffixes */
  24 };
  25
  26 #define MULTIPLIER 31
  27 char NONWORD[] = "\n";
  28
  29 State *statetab[NHASH]; /* hash table of states */
  30
  31 /* xmalloc: dies if malloc() fails */
  32 void *xmalloc(size_t size)
  33 {
  34         void *p;
  35
  36         p = malloc(size);
  37         if (!p) {
  38                 perror("malloc()");
  39                 exit(1);
  40         }
  41         return p;
  42 }
  43
  44 /* xstrdup: dies if strdup() fails */
  45 char *xstrdup(const char *s)
  46 {
  47         char *p;
  48
  49         p = strdup(s);
  50         if (!p) {
  51                 perror("strdup()");
  52                 exit(1);
  53         }
  54         return p;
  55 }
  56
  57 /* hash: compute hash value for array of NPREF strings */
  58 unsigned int hash(char *s[NPREF])
  59 {
  60         unsigned int h;
  61         unsigned char *p;
  62         int i;
  63
  64         h = 0;
  65         for (i = 0; i < NPREF; i++)
  66                 for (p = (unsigned char *) s[i]; *p != '\0'; p++)
  67                         h = MULTIPLIER * h + *p;
  68         return h % NHASH;
  69 }
  70
  71 /* lookup: search for prefix; create if requested. */
  72 /* returns pointer if present or created; NULL if not. */
  73 /* creation doesn't strdup so strings mustn't change later */
  74 State *lookup(char *prefix[NPREF], int create)
  75 {
  76         int i, h;
  77         State *sp;
  78
  79         h = hash(prefix);
  80         for (sp = statetab[h]; sp != NULL; sp = sp->next) {
  81                 for (i = 0; i < NPREF; i++)
  82                         if (strcmp(prefix[i], sp->pref[i]) != 0)
  83                                 break;
  84                 if (i == NPREF)  /* found it */
  85                         return sp;
  86         }
  87
  88         if (create) {
  89                 sp = (State *) xmalloc(sizeof(State));
  90                 for (i = 0; i < NPREF; i++)
  91                         sp->pref[i] = prefix[i];
  92                 sp->suf = NULL;
  93                 sp->next = statetab[h];
  94                 statetab[h] = sp;
  95         }
  96
  97         return sp;
  98 }
  99
 100 /* addsuffix: add to state. suffix must not change later */
 101 void addsuffix(State *sp, char *suffix)
 102 {
 103         Suffix *suf;
 104
 105         suf = (Suffix *) xmalloc(sizeof(Suffix));
 106         suf->word = suffix;
 107         suf->next = sp->suf;
 108         sp->suf = suf;
 109 }
 110
 111 /* add: add word to suffix list, update prefix */
 112 void add(char *prefix[NPREF], char *suffix)
 113 {
 114         State *sp;
 115
 116         sp = lookup(prefix, 1); /* create if not found */
 117         addsuffix(sp, suffix);
 118         /* move the words down the prefix */
 119         memmove(prefix, prefix + 1, (NPREF - 1) * sizeof(prefix[0]));
 120         prefix[NPREF-1] = suffix;
 121 }
 122
 123 /* build: read input, build prefix table */
 124 void build(char *prefix[NPREF], FILE *f)
 125 {
 126         char buf[100], fmt[10];
 127
 128         /* create a format string; %s could overflow buf */
 129         sprintf(fmt, "%%%ds", sizeof(buf)-1);
 130         while (fscanf(f, fmt, buf) != EOF)
 131                 add(prefix, xstrdup(buf));
 132 }
 133
 134 /* generate: produce output, one word per line */
 135 void generate(int nwords)
 136 {
 137         State *sp;
 138         Suffix *suf;
 139         char *prefix[NPREF], *w;
 140         int i, nmatch;
 141
 142         for (i = 0; i < NPREF; i++) /* reset initial prefix */
 143                 prefix[i] = NONWORD;
 144
 145         for (i = 0; i < nwords; i++) {
 146                 sp = lookup(prefix, 0);
 147                 nmatch = 0;
 148                 for (suf = sp->suf; suf != NULL; suf = suf->next)
 149                         if (rand() % ++nmatch == 0) /* prob = 1/nmatch */
 150                                 w = suf->word;
 151                 if (strcmp(w, NONWORD) == 0)
 152                         break;
 153                 printf("%s\n", w);
 154                 memmove(prefix, prefix + 1, (NPREF-1) * sizeof(prefix[0]));
 155                 prefix[NPREF-1] = w;
 156         }
 157 }
 158
 159 int main(void)
 160 {
 161         int i, nwords;
 162         char *prefix[NPREF]; /* current input prefix */
 163
 164         nwords = MAXGEN;
 165
 166         for (i = 0; i < NPREF; i++) /* set up initial prefix */
 167                 prefix[i] = NONWORD;
 168
 169         build(prefix, stdin);
 170         add(prefix, NONWORD);
 171
 172         srand(time(NULL));
 173         generate(nwords);
 174         return 0;
 175 }