parrot.c

   1 /*
   2  *      Parrot Picking Fortune Cookies aka Simple Text Associator
   3  *
   4  *      (c) 2001 Martin Mares <mj@ucw.cz>
   5  */
   6
   7 #include <stdio.h>
   8 #include <ctype.h>
   9 #include <stdlib.h>
  10 #include <string.h>
  11
  12 #define TEXTLEN 1024
  13 #define WORDLEN 64
  14 #define HASHSIZE 32768
  15 #define MAXFUZZ 3
  16 #define SKIP_PTS -10
  17 #define MATCH_PTS_LOW 20
  18 #define MATCH_PTS_HIGH 1000
  19
  20 struct wd {
  21   struct wd *next;
  22   int cnt;
  23   int ref;
  24   char w[1];
  25 };
  26 static struct wd *hash[HASHSIZE];
  27 static int wcnt;
  28
  29 static int n;
  30 static struct wd *input[TEXTLEN];
  31 static int next[TEXTLEN];
  32
  33 static struct wd *
  34 findword(char *x)
  35 {
  36   struct wd *w;
  37   unsigned h=0;
  38   char *y;
  39
  40   for (y=x; *y; y++)
  41     h = h*13 + *y;
  42   h %= HASHSIZE;
  43   for (w=hash[h]; w; w=w->next)
  44     if (!strcmp(w->w, x))
  45       return w;
  46   w = malloc(sizeof(struct wd) + strlen(x));
  47   w->next = hash[h];
  48   hash[h] = w;
  49   w->cnt = 0;
  50   w->ref = -1;
  51   strcpy(w->w, x);
  52   wcnt++;
  53   return w;
  54 }
  55
  56 static int
  57 getword(FILE *f, char *buf)
  58 {
  59   int c, l;
  60
  61   do
  62     {
  63       c = fgetc(f);
  64       if (c == '\n' &&
  65           (c = fgetc(f)) == '%' &&
  66           (c = fgetc(f)) == '\n')
  67         {
  68           *buf = 0;
  69           return -1;
  70         }
  71     }
  72   while (c != EOF && !isalnum(c));
  73   if (c == EOF)
  74     return 0;
  75   l = WORDLEN-1;
  76   do
  77     {
  78       *buf++ = tolower(c);
  79       c = fgetc(f);
  80     }
  81   while (c != EOF && isalnum(c) && --l);
  82   if (c != EOF)
  83     ungetc(c, f);
  84   *buf = 0;
  85   return 1;
  86 }
  87
  88 static void
  89 voc_build(FILE *f)
  90 {
  91   char buf[WORDLEN];
  92
  93   while (getword(f, buf))
  94     if (buf[0])
  95       {
  96         struct wd *w = findword(buf);
  97         w->cnt++;
  98       }
  99   printf("Found %d words.\n", wcnt);
 100 }
 101
 102 static void
 103 scan_in(FILE *f)
 104 {
 105   char buf[WORDLEN];
 106
 107   while (getword(f, buf))
 108     if (buf[0])
 109       {
 110         struct wd *w = findword(buf);
 111         input[n] = w;
 112         if (w->ref < 0)
 113           w->ref = n;
 114         else
 115           {
 116             int i = w->ref;
 117             while (next[i] >= 0)
 118               i = next[i];
 119             next[i] = n;
 120           }
 121         next[n] = -1;
 122         n++;
 123         if (n >= TEXTLEN)
 124           {
 125             fprintf(stderr, "Input too long!\n");
 126             exit(1);
 127           }
 128       }
 129   printf("Scanned input of %d words.\n", n);
 130 }
 131
 132 static void
 133 associate(FILE *f)
 134 {
 135   off_t start = 0, best_start = 0;
 136   char buf[WORDLEN];
 137   int cost[TEXTLEN];
 138   int pos[TEXTLEN];
 139   int pts, xpos, p, pp, i, j;
 140   int best_pts = 0;
 141
 142  newfort:
 143   if (start)
 144     {
 145       pp = 0;
 146       for (i=0; i<n; i++)
 147         if (cost[i] > pp)
 148           pp = cost[i];
 149       // printf("%d pts\n", pp);
 150       if (pp > best_pts)
 151         {
 152           best_pts = pp;
 153           best_start = start;
 154         }
 155     }
 156   start = ftell(f);
 157   bzero(cost, n*sizeof(int));
 158   memset(pos, -1, n*sizeof(int));
 159   pts = 0;
 160   xpos = 0;
 161
 162   while (getword(f, buf))
 163     if (!buf[0])
 164       goto newfort;
 165     else
 166       {
 167         struct wd *w = findword(buf);
 168         for (i=w->ref; i >= 0; i=next[i])
 169           {
 170             j = i - MAXFUZZ;
 171             if (j < 0)
 172               j = 0;
 173             pp = cost[i];
 174             if (pp < w->cnt)
 175               pp = w->cnt;
 176             while (j < i)
 177               {
 178                 if (pos[j] >= 0)
 179                   {
 180                     p = xpos - pos[j];
 181                     if (p < i-j)
 182                       p = i-j;
 183                     p = SKIP_PTS*p + cost[j] + w->cnt;
 184                     if (p > pp)
 185                       pp = p;
 186                   }
 187                 j++;
 188               }
 189             if (pp > cost[i])
 190               {
 191                 cost[i] = pp;
 192                 pos[i] = xpos;
 193               }
 194           }
 195         xpos++;
 196       }
 197
 198   printf("Best: %d points at %d\n", best_pts, best_start);
 199   puts("---");
 200   fseek(f, best_start, SEEK_SET);
 201   while (getword(f, buf) > 0)
 202     {
 203       struct wd *w = findword(buf);
 204       if (w->ref >= 0)
 205         printf("<%s> ", buf);
 206       else
 207         printf("%s ", buf);
 208     }
 209   puts("\n---");
 210   i = ftell(f) - best_start;
 211   fseek(f, best_start, SEEK_SET);
 212   while (i--)
 213     putchar(fgetc(f));
 214 }
 215
 216 static int
 217 cmp(const void *a, const void *b)
 218 {
 219   struct wd *x = *(struct wd **)a;
 220   struct wd *y = *(struct wd **)b;
 221   return (x->cnt < y->cnt) - (x->cnt > y->cnt);
 222 }
 223
 224 static void
 225 voc_val(void)
 226 {
 227   int i, j;
 228   struct wd *w, *wa[wcnt];
 229
 230   j = 0;
 231   for (i=0; i<HASHSIZE; i++)
 232     for (w=hash[i]; w; w=w->next)
 233       wa[j++] = w;
 234   qsort(wa, wcnt, sizeof(struct wd *), cmp);
 235 #if 0
 236   for (i=0; i<wcnt; i++)
 237     {
 238       w = wa[i];
 239       printf("%5d %s\n", w->cnt, w->w);
 240     }
 241 #endif
 242   for (i=0; i<wcnt/600; i++)
 243     wa[i]->cnt = MATCH_PTS_LOW;
 244   for (; i<wcnt; i++)
 245     wa[i]->cnt = MATCH_PTS_HIGH;
 246 }
 247
 248 int
 249 main(int argc, char **argv)
 250 {
 251   FILE *fort;
 252
 253   if (argc != 2)
 254     {
 255       fprintf(stderr, "Usage: parrot <fortune-file>\n");
 256       return 1;
 257     }
 258   fort = fopen(argv[1], "r");
 259   if (!fort)
 260     {
 261       fprintf(stderr, "%s: %m\n", argv[1]);
 262       return 1;
 263     }
 264
 265   voc_build(fort);
 266   voc_val();
 267   scan_in(stdin);
 268   rewind(fort);
 269   associate(fort);
 270 }