1 d1f529f4 2005-10-29 devnull #include <u.h>
  2 d1f529f4 2005-10-29 devnull #include <libc.h>
  3 d1f529f4 2005-10-29 devnull #include <bio.h>
  4 d1f529f4 2005-10-29 devnull #include <regexp.h>
  5 d1f529f4 2005-10-29 devnull #include "hash.h"
  6 d1f529f4 2005-10-29 devnull 
  7 d1f529f4 2005-10-29 devnull enum
  8 d1f529f4 2005-10-29 devnull {
  9 d1f529f4 2005-10-29 devnull 	MAXTAB = 256,
 10 cbeb0b26 2006-04-01 devnull 	MAXBEST = 32
 11 d1f529f4 2005-10-29 devnull };
 12 d1f529f4 2005-10-29 devnull 
 13 d1f529f4 2005-10-29 devnull typedef struct Table Table;
 14 d1f529f4 2005-10-29 devnull struct Table
 15 d1f529f4 2005-10-29 devnull {
 16 d1f529f4 2005-10-29 devnull 	char *file;
 17 d1f529f4 2005-10-29 devnull 	Hash *hash;
 18 d1f529f4 2005-10-29 devnull 	int nmsg;
 19 d1f529f4 2005-10-29 devnull };
 20 d1f529f4 2005-10-29 devnull 
 21 d1f529f4 2005-10-29 devnull typedef struct Word Word;
 22 d1f529f4 2005-10-29 devnull struct Word
 23 d1f529f4 2005-10-29 devnull {
 24 d1f529f4 2005-10-29 devnull 	Stringtab *s;	/* from hmsg */
 25 d1f529f4 2005-10-29 devnull 	int count[MAXTAB];	/* counts from each table */
 26 d1f529f4 2005-10-29 devnull 	double p[MAXTAB];	/* probabilities from each table */
 27 d1f529f4 2005-10-29 devnull 	double mp;	/* max probability */
 28 d1f529f4 2005-10-29 devnull 	int mi;		/* w.p[w.mi] = w.mp */
 29 d1f529f4 2005-10-29 devnull };
 30 d1f529f4 2005-10-29 devnull 
 31 d1f529f4 2005-10-29 devnull Table tab[MAXTAB];
 32 d1f529f4 2005-10-29 devnull int ntab;
 33 d1f529f4 2005-10-29 devnull 
 34 d1f529f4 2005-10-29 devnull Word best[MAXBEST];
 35 d1f529f4 2005-10-29 devnull int mbest;
 36 d1f529f4 2005-10-29 devnull int nbest;
 37 d1f529f4 2005-10-29 devnull 
 38 d1f529f4 2005-10-29 devnull int debug;
 39 d1f529f4 2005-10-29 devnull 
 40 d1f529f4 2005-10-29 devnull void
 41 d1f529f4 2005-10-29 devnull usage(void)
 42 d1f529f4 2005-10-29 devnull {
 43 d1f529f4 2005-10-29 devnull 	fprint(2, "usage: bayes [-D] [-m maxword] boxhash ... ~ msghash ...\n");
 44 d1f529f4 2005-10-29 devnull 	exits("usage");
 45 d1f529f4 2005-10-29 devnull }
 46 d1f529f4 2005-10-29 devnull 
 47 d1f529f4 2005-10-29 devnull void*
 48 d1f529f4 2005-10-29 devnull emalloc(int n)
 49 d1f529f4 2005-10-29 devnull {
 50 d1f529f4 2005-10-29 devnull 	void *v;
 51 d1f529f4 2005-10-29 devnull 
 52 d1f529f4 2005-10-29 devnull 	v = mallocz(n, 1);
 53 d1f529f4 2005-10-29 devnull 	if(v == nil)
 54 d1f529f4 2005-10-29 devnull 		sysfatal("out of memory");
 55 d1f529f4 2005-10-29 devnull 	return v;
 56 d1f529f4 2005-10-29 devnull }
 57 d1f529f4 2005-10-29 devnull 
 58 d1f529f4 2005-10-29 devnull void
 59 d1f529f4 2005-10-29 devnull noteword(Word *w)
 60 d1f529f4 2005-10-29 devnull {
 61 d1f529f4 2005-10-29 devnull 	int i;
 62 d1f529f4 2005-10-29 devnull 
 63 d1f529f4 2005-10-29 devnull 	for(i=nbest-1; i>=0; i--)
 64 d1f529f4 2005-10-29 devnull 		if(w->mp < best[i].mp)
 65 d1f529f4 2005-10-29 devnull 			break;
 66 d1f529f4 2005-10-29 devnull 	i++;
 67 d1f529f4 2005-10-29 devnull 
 68 d1f529f4 2005-10-29 devnull 	if(i >= mbest)
 69 d1f529f4 2005-10-29 devnull 		return;
 70 d1f529f4 2005-10-29 devnull 	if(nbest == mbest)
 71 d1f529f4 2005-10-29 devnull 		nbest--;
 72 d1f529f4 2005-10-29 devnull 	if(i < nbest)
 73 d1f529f4 2005-10-29 devnull 		memmove(&best[i+1], &best[i], (nbest-i)*sizeof(best[0]));
 74 d1f529f4 2005-10-29 devnull 	best[i] = *w;
 75 d1f529f4 2005-10-29 devnull 	nbest++;
 76 d1f529f4 2005-10-29 devnull }
 77 d1f529f4 2005-10-29 devnull 
 78 d1f529f4 2005-10-29 devnull Hash*
 79 d1f529f4 2005-10-29 devnull hread(char *s)
 80 d1f529f4 2005-10-29 devnull {
 81 d1f529f4 2005-10-29 devnull 	Hash *h;
 82 d1f529f4 2005-10-29 devnull 	Biobuf *b;
 83 d1f529f4 2005-10-29 devnull 
 84 d1f529f4 2005-10-29 devnull 	if((b = Bopenlock(s, OREAD)) == nil)
 85 d1f529f4 2005-10-29 devnull 		sysfatal("open %s: %r", s);
 86 d1f529f4 2005-10-29 devnull 
 87 d1f529f4 2005-10-29 devnull 	h = emalloc(sizeof(Hash));
 88 d1f529f4 2005-10-29 devnull 	Breadhash(b, h, 1);
 89 d1f529f4 2005-10-29 devnull 	Bterm(b);
 90 d1f529f4 2005-10-29 devnull 	return h;
 91 d1f529f4 2005-10-29 devnull }
 92 d1f529f4 2005-10-29 devnull 
 93 d1f529f4 2005-10-29 devnull void
 94 d1f529f4 2005-10-29 devnull main(int argc, char **argv)
 95 d1f529f4 2005-10-29 devnull {
 96 d1f529f4 2005-10-29 devnull 	int i, j, a, mi, oi, tot, keywords;
 97 d1f529f4 2005-10-29 devnull 	double totp, p, xp[MAXTAB];
 98 d1f529f4 2005-10-29 devnull 	Hash *hmsg;
 99 d1f529f4 2005-10-29 devnull 	Word w;
100 d1f529f4 2005-10-29 devnull 	Stringtab *s, *t;
101 d1f529f4 2005-10-29 devnull 	Biobuf bout;
102 d1f529f4 2005-10-29 devnull 
103 d1f529f4 2005-10-29 devnull 	mbest = 15;
104 d1f529f4 2005-10-29 devnull 	keywords = 0;
105 d1f529f4 2005-10-29 devnull 	ARGBEGIN{
106 d1f529f4 2005-10-29 devnull 	case 'D':
107 d1f529f4 2005-10-29 devnull 		debug = 1;
108 d1f529f4 2005-10-29 devnull 		break;
109 d1f529f4 2005-10-29 devnull 	case 'k':
110 d1f529f4 2005-10-29 devnull 		keywords = 1;
111 d1f529f4 2005-10-29 devnull 		break;
112 d1f529f4 2005-10-29 devnull 	case 'm':
113 d1f529f4 2005-10-29 devnull 		mbest = atoi(EARGF(usage()));
114 d1f529f4 2005-10-29 devnull 		if(mbest > MAXBEST)
115 d1f529f4 2005-10-29 devnull 			sysfatal("cannot keep more than %d words", MAXBEST);
116 d1f529f4 2005-10-29 devnull 		break;
117 d1f529f4 2005-10-29 devnull 	default:
118 d1f529f4 2005-10-29 devnull 		usage();
119 d1f529f4 2005-10-29 devnull 	}ARGEND
120 d1f529f4 2005-10-29 devnull 
121 d1f529f4 2005-10-29 devnull 	for(i=0; i<argc; i++)
122 d1f529f4 2005-10-29 devnull 		if(strcmp(argv[i], "~") == 0)
123 d1f529f4 2005-10-29 devnull 			break;
124 d1f529f4 2005-10-29 devnull 
125 d1f529f4 2005-10-29 devnull 	if(i > MAXTAB)
126 d1f529f4 2005-10-29 devnull 		sysfatal("cannot handle more than %d tables", MAXTAB);
127 d1f529f4 2005-10-29 devnull 
128 d1f529f4 2005-10-29 devnull 	if(i+1 >= argc)
129 d1f529f4 2005-10-29 devnull 		usage();
130 d1f529f4 2005-10-29 devnull 
131 d1f529f4 2005-10-29 devnull 	for(i=0; i<argc; i++){
132 d1f529f4 2005-10-29 devnull 		if(strcmp(argv[i], "~") == 0)
133 d1f529f4 2005-10-29 devnull 			break;
134 d1f529f4 2005-10-29 devnull 		tab[ntab].file = argv[i];
135 d1f529f4 2005-10-29 devnull 		tab[ntab].hash = hread(argv[i]);
136 d1f529f4 2005-10-29 devnull 		s = findstab(tab[ntab].hash, "*nmsg*", 6, 1);
137 d1f529f4 2005-10-29 devnull 		if(s == nil || s->count == 0)
138 d1f529f4 2005-10-29 devnull 			tab[ntab].nmsg = 1;
139 d1f529f4 2005-10-29 devnull 		else
140 d1f529f4 2005-10-29 devnull 			tab[ntab].nmsg = s->count;
141 d1f529f4 2005-10-29 devnull 		ntab++;
142 d1f529f4 2005-10-29 devnull 	}
143 d1f529f4 2005-10-29 devnull 
144 d1f529f4 2005-10-29 devnull 	Binit(&bout, 1, OWRITE);
145 d1f529f4 2005-10-29 devnull 
146 d1f529f4 2005-10-29 devnull 	oi = ++i;
147 d1f529f4 2005-10-29 devnull 	for(a=i; a<argc; a++){
148 d1f529f4 2005-10-29 devnull 		hmsg = hread(argv[a]);
149 d1f529f4 2005-10-29 devnull 		nbest = 0;
150 d1f529f4 2005-10-29 devnull 		for(s=hmsg->all; s; s=s->link){
151 d1f529f4 2005-10-29 devnull 			w.s = s;
152 d1f529f4 2005-10-29 devnull 			tot = 0;
153 d1f529f4 2005-10-29 devnull 			totp = 0.0;
154 d1f529f4 2005-10-29 devnull 			for(i=0; i<ntab; i++){
155 d1f529f4 2005-10-29 devnull 				t = findstab(tab[i].hash, s->str, s->n, 0);
156 d1f529f4 2005-10-29 devnull 				if(t == nil)
157 d1f529f4 2005-10-29 devnull 					w.count[i] = 0;
158 d1f529f4 2005-10-29 devnull 				else
159 d1f529f4 2005-10-29 devnull 					w.count[i] = t->count;
160 d1f529f4 2005-10-29 devnull 				tot += w.count[i];
161 d1f529f4 2005-10-29 devnull 				p = w.count[i]/(double)tab[i].nmsg;
162 d1f529f4 2005-10-29 devnull 				if(p >= 1.0)
163 d1f529f4 2005-10-29 devnull 					p = 1.0;
164 d1f529f4 2005-10-29 devnull 				w.p[i] = p;
165 d1f529f4 2005-10-29 devnull 				totp += p;
166 d1f529f4 2005-10-29 devnull 			}
167 d1f529f4 2005-10-29 devnull 
168 d1f529f4 2005-10-29 devnull 			if(tot < 5){		/* word does not appear enough; give to box 0 */
169 d1f529f4 2005-10-29 devnull 				w.p[0] = 0.5;
170 d1f529f4 2005-10-29 devnull 				for(i=1; i<ntab; i++)
171 d1f529f4 2005-10-29 devnull 					w.p[i] = 0.1;
172 d1f529f4 2005-10-29 devnull 				w.mp = 0.5;
173 d1f529f4 2005-10-29 devnull 				w.mi = 0;
174 d1f529f4 2005-10-29 devnull 				noteword(&w);
175 d1f529f4 2005-10-29 devnull 				continue;
176 d1f529f4 2005-10-29 devnull 			}
177 d1f529f4 2005-10-29 devnull 
178 d1f529f4 2005-10-29 devnull 			w.mp = 0.0;
179 d1f529f4 2005-10-29 devnull 			for(i=0; i<ntab; i++){
180 d1f529f4 2005-10-29 devnull 				p = w.p[i];
181 d1f529f4 2005-10-29 devnull 				p /= totp;
182 d1f529f4 2005-10-29 devnull 				if(p < 0.01)
183 d1f529f4 2005-10-29 devnull 					p = 0.01;
184 d1f529f4 2005-10-29 devnull 				else if(p > 0.99)
185 d1f529f4 2005-10-29 devnull 					p = 0.99;
186 d1f529f4 2005-10-29 devnull 				if(p > w.mp){
187 d1f529f4 2005-10-29 devnull 					w.mp = p;
188 d1f529f4 2005-10-29 devnull 					w.mi = i;
189 d1f529f4 2005-10-29 devnull 				}
190 d1f529f4 2005-10-29 devnull 				w.p[i] = p;
191 d1f529f4 2005-10-29 devnull 			}
192 d1f529f4 2005-10-29 devnull 			noteword(&w);
193 d1f529f4 2005-10-29 devnull 		}
194 d1f529f4 2005-10-29 devnull 
195 d1f529f4 2005-10-29 devnull 		totp = 0.0;
196 d1f529f4 2005-10-29 devnull 		for(i=0; i<ntab; i++){
197 d1f529f4 2005-10-29 devnull 			p = 1.0;
198 d1f529f4 2005-10-29 devnull 			for(j=0; j<nbest; j++)
199 d1f529f4 2005-10-29 devnull 				p *= best[j].p[i];
200 d1f529f4 2005-10-29 devnull 			xp[i] = p;
201 d1f529f4 2005-10-29 devnull 			totp += p;
202 d1f529f4 2005-10-29 devnull 		}
203 d1f529f4 2005-10-29 devnull 		for(i=0; i<ntab; i++)
204 d1f529f4 2005-10-29 devnull 			xp[i] /= totp;
205 d1f529f4 2005-10-29 devnull 		mi = 0;
206 d1f529f4 2005-10-29 devnull 		for(i=1; i<ntab; i++)
207 d1f529f4 2005-10-29 devnull 			if(xp[i] > xp[mi])
208 d1f529f4 2005-10-29 devnull 				mi = i;
209 d1f529f4 2005-10-29 devnull 		if(oi != argc-1)
210 d1f529f4 2005-10-29 devnull 			Bprint(&bout, "%s: ", argv[a]);
211 d1f529f4 2005-10-29 devnull 		Bprint(&bout, "%s %f", tab[mi].file, xp[mi]);
212 d1f529f4 2005-10-29 devnull 		if(keywords){
213 d1f529f4 2005-10-29 devnull 			for(i=0; i<nbest; i++){
214 d1f529f4 2005-10-29 devnull 				Bprint(&bout, " ");
215 d1f529f4 2005-10-29 devnull 				Bwrite(&bout, best[i].s->str, best[i].s->n);
216 d1f529f4 2005-10-29 devnull 				Bprint(&bout, " %f", best[i].p[mi]);
217 d1f529f4 2005-10-29 devnull 			}
218 d1f529f4 2005-10-29 devnull 		}
219 d1f529f4 2005-10-29 devnull 		freehash(hmsg);
220 d1f529f4 2005-10-29 devnull 		Bprint(&bout, "\n");
221 d1f529f4 2005-10-29 devnull 		if(debug){
222 d1f529f4 2005-10-29 devnull 			for(i=0; i<nbest; i++){
223 d1f529f4 2005-10-29 devnull 				Bwrite(&bout, best[i].s->str, best[i].s->n);
224 d1f529f4 2005-10-29 devnull 				Bprint(&bout, " %f", best[i].p[mi]);
225 d1f529f4 2005-10-29 devnull 				if(best[i].p[mi] < best[i].mp)
226 d1f529f4 2005-10-29 devnull 					Bprint(&bout, " (%f %s)", best[i].mp, tab[best[i].mi].file);
227 d1f529f4 2005-10-29 devnull 				Bprint(&bout, "\n");
228 d1f529f4 2005-10-29 devnull 			}
229 d1f529f4 2005-10-29 devnull 		}
230 d1f529f4 2005-10-29 devnull 	}
231 d1f529f4 2005-10-29 devnull 	Bterm(&bout);
232 d1f529f4 2005-10-29 devnull }