![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to typo.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [MW Coherent from dump] / coherent / d / bin|
Return to typo.c CVS log | Up to [MW Coherent from dump] / coherent / d / bin |
1.1 root 1: /*
2: * Detect typographical errors.
3: */
4:
5: #include <stdio.h>
6: #include <ctype.h>
7: #include <sys/stat.h>
8:
9: #define oc(c) ((c)+'`')
10: #define NSBRK 512 /* Amount to sbrk at once in bytes */
11: #define BADSBRK ((char *)-1) /* fail from sbrk() */
12: #define NWORD 200 /* Longest word (ridiculously big) */
13: #define NHASH 64 /* Number of hash buckets (power of 2) */
14:
15: char dictfile[] = "/usr/dict/dict";
16: char digfile[] = "/usr/dict/digrams";
17: char trifile[] = "/usr/dict/trigrams";
18: char tmp[] = "/tmp/typoXXXXXX";
19: char sort[] = "sort";
20: char *tmpfile;
21: char notrimem[] = "Out of memory for trigrams";
22: char nosort[] = "Cannot locate sort";
23: char word[NWORD];
24: FILE *ifp;
25: FILE *pfp;
26:
27: char ibuf[BUFSIZ];
28: char obuf[BUFSIZ];
29: char xbuf[BUFSIZ];
30:
31: unsigned hashval;
32:
33: int rflag; /* Raw (no removal of nroff things) input */
34: int nflag; /* No pre-defined statistics or exceptions */
35: int sflag; /* Write out statistics */
36:
37: typedef struct EXCEPT {
38: unsigned e_hval;
39: struct EXCEPT *e_next;
40: char e_word[];
41: } EXCEPT;
42: EXCEPT *except[NHASH];
43:
44: /*
45: * Table of digrams, indexed by first
46: * and then second character. [1-26]
47: * represent [a-z] inclusive and 0
48: * represents the beginning or ending of word.
49: */
50: unsigned digrams[27][27];
51:
52: /*
53: * Table of trigrams, indexed by first and
54: * second letter and allocated on the third letter.
55: * After all of the input data has been
56: * sampled, the t_freq entry changes from
57: * frequency to an index of peculiarity.
58: */
59: typedef struct TRIGRAMS {
60: struct TRIGRAMS *t_next;
61: char t_char;
62: unsigned char t_freq;
63: } TRIGRAMS;
64: TRIGRAMS *trigrams[27][27];
65:
66: /*
67: * Table of logarithms scaled by 1000.
68: * Table from 0-99 inclusive.
69: */
70: int log1[] = {
71: 0000, 0693, 1099, 1386, 1609, 1792, 1946, 2080, 2197, /* 1-9 */
72: 2303, 2398, 2485, 2565, 2639, 2708, 2772, 2833, 2890, /* 10-18 */
73: 2944, 2996, 3045, 3091, 3136, 3178, 3219, 3258, 3296, /* 19-27 */
74: 3332, 3367, 3401, 3434, 3466, 3497, 3526, 3555, 3584, /* 28-36 */
75: 3611, 3638, 3664, 3689, 3714, 3738, 3761, 3784, 3807, /* 37-45 */
76: 3829, 3850, 3871, 3892, 3912, 3932, 3951, 3970, 3989, /* 46-54 */
77: 4007, 4025, 4043, 4060, 4078, 4094, 4111, 4127, 4143, /* 55-63 */
78: 4159, 4174, 4190, 4205, 4220, 4234, 4249, 4263, 4277, /* 64-72 */
79: 4291, 4304, 4318, 4331, 4344, 4357, 4369, 4382, 4394, /* 73-81 */
80: 4407, 4419, 4431, 4443, 4454, 4466, 4477, 4489, 4500, /* 82-90 */
81: 4511, 4521, 4533, 4543, 4554, 4564, 4575, 4585, 4595, /* 91-99 */
82: };
83:
84: /*
85: * Table of logarithms for each multiple
86: * of ten from 100 - 990 inclusive
87: * (scaled as above).
88: */
89: int log2[] = {
90: 4605, 4701, 4788, 4868, 4942, 5011, 4075, 5136, 5193, /* 100-180 */
91: 5247, 5298, 5347, 5394, 5438, 5481, 5522, 5561, 5598, /* 190-270 */
92: 5635, 5670, 5704, 5737, 5768, 5799, 5829, 5858, 5886, /* 280-360 */
93: 5914, 5940, 5966, 5992, 6016, 6040, 6064, 6087, 6109, /* 370-450 */
94: 6131, 6153, 6174, 6194, 6215, 6234, 6254, 6273, 6292, /* 460-540 */
95: 6310, 6328, 6346, 6663, 6380, 6397, 6414, 6430, 6446, /* 550-630 */
96: 6462, 6477, 6492, 6507, 6522, 6537, 6551, 6565, 6579, /* 640-720 */
97: 6593, 6607, 6620, 6633, 6646, 6659, 6672, 6684, 6697, /* 730-810 */
98: 6709, 6721, 6733, 6745, 6757, 6769, 6780, 6791, 6802, /* 820-900 */
99: 6813, 6824, 6835, 6846, 6857, 6867, 6877, 6888, 6898, /* 910-990 */
100: };
101:
102: /*
103: * Table of logarithms of multiples
104: * of 100 from 1000-9900 inclusive
105: * (scaled as before).
106: */
107: int log3[] = {
108: 6908, 7003, 7090, 7170, 7244, 7313, 7378, 7438, 7496, /* 1000-1800 */
109: 7550, 7601, 7650, 7696, 7741, 7783, 7824, 7863, 7901, /* 1900-2700 */
110: 7937, 7973, 8006, 8039, 8071, 8102, 8132, 8161, 8189, /* 2800-3600 */
111: 8216, 8243, 8269, 8294, 8319, 8343, 8366, 8389, 8412, /* 3700-4500 */
112: 8434, 8455, 8476, 8497, 8517, 8537, 8556, 8576, 8594, /* 4600-5400 */
113: 8613, 8631, 8648, 8666, 8683, 8700, 8716, 8732, 8748, /* 5500-6300 */
114: 8764, 8780, 8795, 8810, 8825, 8839, 8854, 8868, 8882, /* 6400-7200 */
115: 8896, 8909, 8923, 8936, 8949, 8962, 8975, 8987, 9000, /* 7300-8100 */
116: 9012, 9024, 9036, 9048, 9060, 9071, 9083, 9094, 9105, /* 8200-9000 */
117: 9116, 9127, 9138, 9149, 9159, 9170, 9180, 9190, 9200, /* 9100-9900 */
118: };
119:
120: char *malloc();
121: char *mktemp();
122: char *sbrk();
123: char *getword();
124: EXCEPT *lookup();
125: FILE *pinit();
126:
127: main(argc, argv)
128: char *argv[];
129: {
130: register char *ap;
131: register int i;
132: FILE *fp;
133:
134: /*
135: * Because we have our own allocator.
136: */
137: setbuf(stdout, obuf);
138: setbuf(stderr, NULL);
139: while (argc>1 && *argv[1]=='-') {
140: for (ap = &argv[1][1]; *ap != '\0'; ap++)
141: switch (*ap) {
142: case 'n':
143: nflag = 1;
144: break;
145:
146: case 'r':
147: rflag = 1;
148: break;
149:
150: case 's':
151: sflag = 1;
152: break;
153:
154: default:
155: usage();
156: }
157: argc--;
158: argv++;
159: }
160: if (sflag == 0) {
161: readdicts();
162: pfp = pinit();
163: }
164: if (argc > 1)
165: for (i=1; i<argc; i++) {
166: if ((fp = fopen(argv[i], "r")) == NULL)
167: tyerr("Cannot open input `%s'", argv[i]);
168: typo(fp);
169: }
170: else
171: typo(stdin);
172: if (!sflag) {
173: pterm(pfp);
174: precompute();
175: /*
176: * Re-read the sorted word
177: * list.
178: */
179: reread();
180: } else
181: outstats();
182: rmexit(0);
183: }
184:
185: /*
186: * Called for each input word
187: * to set up file pointer, read
188: * of individual words and enter
189: * frequency statistics into the
190: * tables.
191: */
192: typo(fp)
193: register FILE *fp;
194: {
195: ifp = fp;
196: setbuf(fp, ibuf);
197: while (getword() != NULL) {
198: stats(word);
199: if (!sflag && lookup(word)==NULL)
200: fprintf(pfp, "%s\n", word);
201: }
202: if (fp != stdin)
203: fclose(fp);
204: }
205:
206: /*
207: * Initialise the trigram and digram
208: * tables if the user requests help.
209: * Read in the exception dictionary.
210: * Put each word in a hash table.
211: */
212: readdicts()
213: {
214: FILE *fp;
215:
216: if (nflag)
217: return;
218: if ((fp = fopen(dictfile, "r")) != NULL) {
219: register int l;
220: register char *cp;
221: register EXCEPT *ep;
222:
223: setbuf(fp, xbuf);
224: while (fgets(cp = word, sizeof word, fp) != NULL) {
225: l = strlen(cp);
226: cp[l-1] = '\0';
227: if ((ep = (EXCEPT *)malloc(l + sizeof *ep)) == NULL)
228: tyerr("Out of memory for dictionary");
229: hashval = 0;
230: while (*cp)
231: hashval += *cp++;
232: l = hashval%NHASH;
233: ep->e_next = except[l];
234: except[l] = ep;
235: ep->e_hval = hashval;
236: strcpy(ep->e_word, word);
237: }
238: fclose(fp);
239: }
240: if ((fp = fopen(digfile, "r")) != NULL) {
241: register int t1, t2;
242:
243: setbuf(fp, xbuf);
244: while (fgets(word, NWORD, fp) != NULL) {
245: t1 = cton(word[0]);
246: t2 = cton(word[1]);
247: digrams[t1][t2] = atoi(&word[2]);
248: }
249: fclose(fp);
250: }
251: if ((fp = fopen(trifile, "r")) != NULL) {
252: register TRIGRAMS *tp;
253: register int t1, t2, t3;
254:
255: setbuf(fp, xbuf);
256: while (fgets(word, NWORD, fp) != NULL) {
257: t1 = cton(word[0]);
258: t2 = cton(word[1]);
259: t3 = cton(word[2]);
260: for (tp = trigrams[t1][t2]; tp!=NULL; tp = tp->t_next) {
261: if (tp->t_char == t3) {
262: tp->t_freq += atoi(&word[3]);
263: break;
264: }
265: }
266: if (tp == NULL) {
267: if ((tp = (TRIGRAMS *)malloc(sizeof *tp))==NULL)
268: tyerr(notrimem);
269: tp->t_freq = atoi(&word[3]);
270: tp->t_char = t3;
271: tp->t_next = trigrams[t1][t2];
272: trigrams[t1][t2] = tp;
273: }
274: }
275: fclose(fp);
276: }
277: }
278:
279: /*
280: * Get a character from a digram or
281: * trigram file and check it.
282: * Convert character to index number
283: * for tables.
284: */
285: cton(c)
286: register unsigned c;
287: {
288: if ((c -= '`') >= 27)
289: tyerr("Invalid digram/trigram file format");
290: return (c);
291: }
292:
293: /*
294: * Get the next word from the input.
295: */
296: char *
297: getword()
298: {
299: register char *cp;
300: register int c;
301:
302: while (!isalpha(c = tgetc()))
303: if (c == EOF)
304: return (NULL);
305: cp = word;
306: for (;;) {
307: if (isupper(c))
308: c = tolower(c);
309: *cp++ = c;
310: if (!isalpha(c = tgetc()))
311: break;
312: }
313: *cp = '\0';
314: return (word);
315: }
316:
317: /*
318: * Get a character. This also checks
319: * for roff stuff (if -r is not specified)
320: * and hyphenated words.
321: */
322: tgetc()
323: {
324: static int nlflag = 1;
325: register int c;
326:
327: while (nlflag) {
328: if ((c = getc(ifp)) == '.')
329: while ((c = getc(ifp))!='\n' && c!=EOF)
330: ;
331: else {
332: ungetc(c, ifp);
333: nlflag = 0;
334: break;
335: }
336: }
337: again:
338: if ((c = getc(ifp)) == '\n')
339: nlflag = 1;
340: else if (c == '-') {
341: if ((c = getc(ifp)) == '\n')
342: goto again;
343: } else if (c == '\'')
344: goto again;
345: else if (c == '\\') { /* Fonts and sizes */
346: switch (c = getc(ifp)) {
347: case 'f':
348: c = getc(ifp);
349: goto again;
350:
351: case 's':
352: while ((c = getc(ifp))>='0' && c<='9')
353: ;
354: }
355: }
356: return (c);
357: }
358:
359: /*
360: * Lookup an input word
361: * in the exception list.
362: */
363: EXCEPT *
364: lookup(wp)
365: char *wp;
366: {
367: register char *cp = wp;
368: register EXCEPT *ep;
369:
370: hashval = 0;
371: while (*cp != '\0')
372: hashval += *cp++;
373: for (ep = except[hashval%NHASH]; ep != NULL; ep = ep->e_next)
374: if (ep->e_hval==hashval && strcmp(ep->e_word, word)==0)
375: return (ep);
376: return (NULL);
377: }
378:
379: /*
380: * Compute the trigram and digram statistics
381: * on this word.
382: */
383: stats(wp)
384: register char *wp;
385: {
386: register int t1, t2, t3;
387: register TRIGRAMS *tp;
388:
389: t1 = 0;
390: while (*wp != '\0') {
391: t2 = *wp++;
392: t3 = *wp;
393: if (t2>='a' && t2<='z')
394: t2 -= 'a'-1;
395: if (t3>='a' && t3<='z')
396: t3 -= 'a'-1;
397: digrams[t1][t2]++;
398: for (tp = trigrams[t1][t2]; tp != NULL; tp = tp->t_next)
399: if (tp->t_char == t3) {
400: tp->t_freq++;
401: break;
402: }
403: if (tp == NULL) {
404: if ((tp = (TRIGRAMS *)malloc(sizeof *tp)) != NULL) {
405: tp->t_freq = 1;
406: tp->t_char = t3;
407: tp->t_next = trigrams[t1][t2];
408: trigrams[t1][t2] = tp;
409: }
410: }
411: t1 = t2;
412: }
413: digrams[t2][t3]++;
414: }
415:
416: /*
417: * Output the digram and trigram statistics
418: * onto file `digram' and `trigram'.
419: */
420: outstats()
421: {
422: char x1buf[BUFSIZ];
423: register TRIGRAMS *tp;
424: register int t1, t2;
425: register int freq;
426: FILE *dfp, *tfp;
427:
428: if ((dfp = fopen("digrams", "w")) == NULL)
429: tyerr("Cannot create digrams file");
430: if ((tfp = fopen("trigrams", "w")) == NULL)
431: tyerr("Cannot create trigrams file");
432: setbuf(dfp, xbuf);
433: setbuf(tfp, x1buf);
434: for (t1 = 0; t1 < 27; t1++)
435: for (t2 = 0; t2 < 27; t2++) {
436: if ((freq = digrams[t1][t2]) != 0)
437: fprintf(dfp, "%c%c%d\n", oc(t1), oc(t2), freq);
438: for (tp = trigrams[t1][t2]; tp!=NULL; tp = tp->t_next)
439: fprintf(tfp, "%c%c%c%d\n", oc(t1), oc(t2),
440: oc(tp->t_char), tp->t_freq);
441: }
442: fclose(dfp);
443: fclose(tfp);
444: }
445:
446: /*
447: * Compute index of peculiarity on a
448: * word. This is the RMS mean of the
449: * index for each trigram (say XYZ).
450: * This index is 1/2(log (xy) + log(yz)) - log(xyz)
451: * If there is only one trigram, the RMS
452: * mean is taken to be the one sample.
453: */
454: pindex(wp)
455: register char *wp;
456: {
457: register int t1, t2, t3;
458: register TRIGRAMS *tp;
459: register long sumsq;
460: register long sum;
461: register unsigned count;
462: register int ntri;
463:
464: ntri = 0;
465: t1 = 0;
466: sum = sumsq = 0;
467: while (*wp != '\0') {
468: t2 = *wp++;
469: t3 = *wp;
470: if (t2>='a' && t2<='z')
471: t2 -= 'a'-1;
472: if (t3>='a' && t3<='z')
473: t3 -= 'a'-1;
474: for (tp = trigrams[t1][t2]; tp != NULL; tp = tp->t_next)
475: if (tp->t_char == t3) {
476: count = tp->t_freq;
477: break;
478: }
479: if (tp == NULL)
480: tyerr("Missing trigram");
481: sum += count;
482: sumsq += (long)count*count;
483: ntri++;
484: t1 = t2;
485: }
486: if (ntri > 1) {
487: sum *= sum;
488: sum /= ntri;
489: sum = sumsq-sum;
490: }
491: count = (qsqrt((int)sum) + 5) / 10;
492: return (count);
493: }
494:
495: /*
496: * Pre-compute the trigram statistics.
497: * This essentially transforms the
498: * trigram tables from a table
499: * of frequencies to a table of
500: * indices of peculiarity for that
501: * particular trigram.
502: */
503: precompute()
504: {
505: register int i, j;
506: register TRIGRAMS *tp;
507: register int logij;
508:
509: for (i=0; i<27; i++)
510: for (j=0; j<27; j++) {
511: logij = qlog(digrams[i][j]-1);
512: for (tp = trigrams[i][j]; tp != NULL; tp = tp->t_next) {
513: tp->t_freq = ((logij
514: + qlog(digrams[j][tp->t_char]-1))/2
515: - qlog(tp->t_freq-1)) / 100;
516: }
517: }
518: }
519:
520: /*
521: * Evaluate a natural logarithm
522: * quickly by table lookup.
523: * The resulting logarithm
524: * is multiplied by 1000.
525: * By definition, the log of 0 (or less) is
526: * -10.
527: */
528: qlog(n)
529: register unsigned n;
530: {
531: if (n <= 0)
532: return (-10*1000);
533: if (n < 100)
534: return (log1[n-1]);
535: if (n < 1000)
536: return (log2[(n-95)/10]);
537: if (n < 10000)
538: return (log3[(n-950)/100]);
539: return (10*1000);
540: }
541:
542: /*
543: * Quick version of sqare root.
544: * Uses Newton's method.
545: */
546: qsqrt(x)
547: register unsigned x;
548: {
549: register int maxterm = 50;
550: register unsigned old, new;
551:
552: if ((old = x/10) == 0) {
553: old = 1;
554: if (x == 0)
555: return (0);
556: }
557: do {
558: new = (x/old+old)/2;
559: if (old == new)
560: break;
561: old = new;
562: } while (--maxterm);
563: return (new);
564: }
565:
566: /*
567: * Build pipe to a sort routine.
568: */
569: FILE *
570: pinit()
571: {
572: int pfd[2];
573: register int pid;
574: register int fd;
575: FILE *fp;
576:
577: tmpfile = mktemp(tmp);
578: if (pipe(pfd) < 0)
579: tyerr("Cannot pipe to sort");
580: if ((pid = fork()) < 0)
581: tyerr("Cannot fork for sort");
582: if (pid) {
583: close(pfd[0]);
584: if ((fp = fdopen(pfd[1], "w")) != NULL)
585: setbuf(fp, xbuf);
586: return (fp);
587: } else {
588: dup2(pfd[0], 0);
589: close(pfd[0]);
590: close(pfd[1]);
591: if ((fd = creat(tmp, 0666)) < 0)
592: tyerr("Cannot create temporary file");
593: dup2(fd, 1);
594: close(fd);
595: execlp(sort, sort, "-u", NULL);
596: tyerr(nosort);
597: }
598: }
599:
600: /*
601: * Close off the pipe and wait
602: * for the sort command to
603: * complete.
604: */
605: pterm(fp)
606: FILE *fp;
607: {
608: int status;
609:
610: fclose(fp);
611: while (wait(&status) >= 0)
612: if (status)
613: tyerr("Sort failed");
614: }
615:
616: /*
617: * Re-read the sorted word-list
618: * from the temp file. Because
619: * sort -u is not implemented,
620: * we have to guarantee uniqueness
621: * ourselves.
622: * The output is piped into a
623: * `sort -nr' command.
624: */
625: reread()
626: {
627: FILE *fp;
628: register int ind;
629: int pid, status;
630: int pfd[2];
631:
632: if ((fp = fopen(tmpfile, "r")) == NULL)
633: tyerr("Cannot re-open temp-file");
634: setbuf(fp, xbuf);
635: if (pipe(pfd) < 0)
636: tyerr("Cannot create pipe to sort output");
637: if ((pid = fork()) < 0)
638: fprintf(stderr, "Cannot fork -- output is not sorted\n");
639: else if (pid) {
640: dup2(pfd[1], 1);
641: close(pfd[0]);
642: close(pfd[1]);
643: } else {
644: dup2(pfd[0], 0);
645: close(pfd[0]);
646: close(pfd[1]);
647: execlp(sort, sort, "-nr", NULL);
648: tyerr(nosort);
649: }
650: while (fgets(word, NWORD, fp) != NULL) {
651: word[strlen(word)-1] = '\0';
652: ind = pindex(word);
653: printf("%2d %s\n", ind, word);
654: }
655: fclose(fp);
656: fclose(stdout);
657: while (wait(&status) >= 0)
658: ;
659: }
660:
661: /*
662: * A simple malloc for which there
663: * is no free. It just uses sbrk and
664: * returns a value.
665: * `size' is in bytes.
666: */
667: char *
668: malloc(size)
669: register unsigned size;
670: {
671: static int *rp, *ep;
672: register int *cp;
673:
674: if ((size = (size+sizeof(int)-1)/sizeof(int)) == 0)
675: return (NULL);
676: if (rp==NULL || rp+size>=ep) {
677: if ((ep = (int *)sbrk(NSBRK)) == BADSBRK)
678: return (NULL);
679: if (rp == NULL)
680: rp = ep;
681: ep += NSBRK/sizeof(int);
682: }
683: cp = rp;
684: rp += size;
685: return (cp);
686: }
687:
688: /*
689: * Dummy free.
690: */
691: free(p)
692: char *p;
693: {
694: tyerr("Free not allowed");
695: }
696:
697: /*
698: * Dummy realloc
699: */
700: char *
701: realloc(p)
702: char *p;
703: {
704: tyerr("realloc not allowed");
705: }
706:
707: /*
708: * Exit, removing the temp-file
709: * if it is found.
710: */
711: rmexit(s)
712: {
713: if (tmpfile != NULL)
714: unlink(tmpfile);
715: exit(s);
716: }
717:
718: /*
719: * Error and usage messages
720: */
721: /* VARARGS */
722: tyerr(x)
723: {
724: fprintf(stderr, "typo: %r", &x);
725: putc('\n', stderr);
726: rmexit(1);
727: }
728:
729: usage()
730: {
731: fprintf(stderr, "Usage: typo [-nrs] file\n");
732: rmexit(1);
733: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.