added latency tool
[tridge/junkcode.git] / wordfreq.c
1 /*****************************************************************************
2 A simple C program to detect cheating
3
4 Idea:
5
6 - create a list of words in the files
7 - foreach word create a bitmap of where they occurred 
8 - ignore words that occur in a large proportion of files
9 - produce a matrix of co-occurances
10 - output the pairs with the highest co-occurances
11
12
13 Enhancements:
14 - two thresholds, one for rating matches, one for display of matches
15 - ignore strings; allowing certain chars to be skipped in the input
16
17 Andrew Tridgell, May 1994
18
19 ******************************************************************************/
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include <string.h>
23 #include <math.h>
24
25 typedef enum {False=0,True=1} BOOL;
26
27 /* experimental ? */
28 BOOL beta = False;
29
30 /* should I be case sensitive? */
31 BOOL case_sensitive = False;
32
33 /* how big can a word get? */
34 #define MAX_WORD_LEN 500
35
36 /* how many files are we processing? */
37 int num_files = 0;
38
39 /* the names of the files we are processing - normally stolen from argv */
40 char **file_names = NULL;
41
42 /* how many words have we found? */
43 int num_words = 0;
44
45 /* a list of chars to ignore - can be interesting */
46 char ignore_chars[MAX_WORD_LEN] = "";
47
48 /* what debug level? */
49 int debug = 0;
50
51 /* 
52 a list of all the words found and where they occurred 
53 */
54 struct word
55 {
56   int count; /* how many files this word occurs in */
57   char *word; /* text of word */
58   int *occurred; /* count of occurrance in each file */
59 } *words = NULL;
60
61 int *file_totals=NULL;
62
63 /***************************************************************************** 
64 like realloc() but can start from scratch, and exits if there is an error
65 ******************************************************************************/
66 void *Realloc(void *ptr,int size)
67 {
68   if (!ptr)
69     ptr = malloc(size);
70   else
71     ptr = realloc(ptr,size);
72   if (!ptr)
73     {
74       printf("Can't allocate %d bytes\n",size);
75       exit(0);
76     }
77   return(ptr);
78 }
79
80 /*****************************************************************************
81 decide if two words are equal
82 ******************************************************************************/
83 BOOL wordequal(char *word1,char *word2)
84 {
85   if (case_sensitive)
86     return(strcmp(word1,word2) == 0);
87   else
88     return(strcasecmp(word1,word2) == 0);
89 }
90
91
92 /***************************************************************************** 
93 ask if a word has occurred before - return word index if it has 
94 return -1 if not
95 ******************************************************************************/
96 int find_word(char *word)
97 {
98   int i;
99   int ret;
100   
101   /* we can take advantage of the order of the words */
102   ret = insert_position(word);
103   if (ret >= num_words || !wordequal(word,words[ret].word))
104     return(-1);
105   return(ret);
106
107 }
108
109 /***************************************************************************** 
110 find an insertion position for a new word
111 ******************************************************************************/
112 int insert_position(char *word)
113 {
114   int high_i = num_words;
115   int low_i = 0;
116   int guess,ret;
117
118   /* do a bisection search - this assumes the list is kept ordered */
119   while (high_i > low_i)
120     {
121       guess = (high_i + low_i)/2;
122       if (case_sensitive)
123         ret = strcmp(word,words[guess].word);
124       else
125         ret = strcasecmp(word,words[guess].word);
126       if (ret == 0)
127         return(guess);
128       if (ret > 0)
129         low_i = guess+1;
130       if (ret < 0)
131         high_i = guess;
132     }
133   return(low_i);
134 }
135
136
137 /***************************************************************************** 
138 Insert a word into the list of words that have occurred.
139 If the word already exists then just set the occured bit for the filenum
140 ******************************************************************************/
141 void insert_word(char *word,int filenum)
142 {
143   int wordnum,i;
144   wordnum = find_word(word);
145   if (wordnum < 0)
146     {
147       if (debug > 0)
148         printf("new word %s from filenum %d\n",word,filenum);
149
150       wordnum = insert_position(word);
151       words = (struct word *)Realloc(words,sizeof(struct word)*(num_words+1));
152       num_words++;
153
154       for (i=num_words-2;i>=wordnum;i--)
155         words[i+1] = words[i];
156
157       words[wordnum].count=0;
158       words[wordnum].word = strdup(word);
159       words[wordnum].occurred = 
160         (int *)Realloc(NULL,sizeof(int)*num_files);
161         
162       for (i=0;i<num_files;i++) words[wordnum].occurred[i] = 0;
163     }
164
165   if (!words[wordnum].occurred[filenum]) words[wordnum].count++;
166   words[wordnum].occurred[filenum]++;
167 }
168
169 /*****************************************************************************
170 dump the word occurrance table
171 ******************************************************************************/
172 void dump_word_table(void)
173 {
174   int i,j;
175   for (i=0;i<num_files;i++)
176     printf("%s has %d words\n",file_names[i],file_totals[i]);
177   printf("\n");
178
179   for (i=0;i<num_words;i++)
180     {
181       printf("%-20.20s\t",words[i].word);
182       for (j=0;j<num_files;j++)
183         printf("%6.2f (%5d)   \t",
184                1000.0*100.0*words[i].occurred[j]/file_totals[j],
185                words[i].occurred[j]);
186       printf("\n");
187     }
188 }
189
190 /*****************************************************************************
191 read one character - skipping over the chars in ignore
192 ******************************************************************************/
193 int Read(FILE *f,char *ignore)
194 {
195   int ch = fgetc(f);
196   if (ch == EOF) return(EOF);
197   if (*ignore && (strchr(ignore,(char)ch) != NULL))
198     return(Read(f,ignore));
199   return(ch);
200 }
201
202 /*****************************************************************************
203 get a word from a stream. return the word. return NULL if no more words 
204 exist. possibly skip comments?
205 ******************************************************************************/
206 char *get_word(FILE *f)
207 {
208   static char word[MAX_WORD_LEN+1];
209   int word_len = 0;
210   char ch;
211
212   strcpy(word,"");
213
214   /* skip over non alphanum chars */
215   while ((ch = Read(f,ignore_chars)) != EOF)
216     {
217       if (isalnum(ch)) break;
218     }
219   if (ch == EOF) return(NULL);
220
221   word[word_len++] = ch;
222   
223   /* grab all the alphanums */
224   while (word_len < MAX_WORD_LEN && (isalnum(ch = Read(f,ignore_chars))))
225     word[word_len++] = ch;
226
227   word[word_len] = '\0';
228   return(word);
229 }
230
231
232 /* used for cheating matrix */
233 struct pair
234 {
235   int i,j;
236   int count;
237 } *mat = NULL;
238
239 /***************************************************************************** 
240    compare 2 pair structures - used for sorting 
241 ******************************************************************************/
242 int pair_compare(struct pair *t1,struct pair *t2)
243 {
244   return(t2->count - t1->count);
245 }
246
247 /***************************************************************************** 
248    compare 2 word structures - used for sorting 
249 ******************************************************************************/
250 int words_compare(struct word *t1,struct word *t2)
251 {
252   if (t2->count == t1->count)
253     return(strcmp(t1->word,t2->word));
254   return(t1->count - t2->count);
255 }
256
257
258 /*****************************************************************************
259 process the files by opening them and getting the words
260 ******************************************************************************/
261 void process_files(void)
262 {
263   int i;
264
265   file_totals = (int *)malloc(sizeof(int)*num_files);
266   bzero(file_totals,sizeof(int)*num_files);
267
268   for (i=0;i<num_files;i++)
269     {
270       FILE *f = fopen(file_names[i],"r");
271       char *word;
272       if (!f) 
273         {
274           printf("Can't open %s\n",file_names[i]);
275           continue;
276         }
277 #if 0
278       printf("processing file %s\n",file_names[i]);
279       printf(".");
280 #endif
281       fflush(stdout);
282       while ((word = get_word(f)) != NULL) {
283         insert_word(word,i);
284         file_totals[i]++;
285       }
286       fclose(f);
287     }
288   printf("\n");
289 }
290
291 /*****************************************************************************
292 provide extended help
293 ******************************************************************************/
294 void help(void)
295 {
296 #if 0
297   char *txt = 
298
299 This program tries to identify common words between a list of files,
300 in an attempt to find cases of plagiarism. It first builds a list of
301 all words in all the files, and a bitmap of which words occur in which
302 files. It then ignores very common words
303
304 #endif
305   printf("extended help is not written yet - are you volunteering?\n\n");
306   exit(0);
307 }
308
309 /*****************************************************************************
310 usage of the program
311 ******************************************************************************/
312 void usage(void)
313 {
314   printf("detect: find cheaters by looking at token similarities between files\n");
315   printf("\ndetect [options] <files..>\n");
316   printf("\t-c = be case sensitive\n");
317   printf("\t-t thresh = set threshold1\n");
318   printf("\t-T thresh = set threshold2\n");
319   printf("\t-I ignore_str = ignore these chars in the file\n");
320   printf("\n");
321   exit(0);
322 }
323
324
325 /*****************************************************************************
326 the main program 
327 ******************************************************************************/
328 int main(int argc,char **argv)
329 {
330   double threshold1 = 0.01;
331   double threshold2 = 0.1;
332
333   int opt;
334   extern char *optarg;
335   extern int optind;
336
337   /* get some options */
338   while ((opt = getopt (argc, argv, "ct:T:I:d:hb")) != EOF)
339     switch (opt)
340       {
341       case 'h':
342         help();
343         break;
344       case 'c':
345         case_sensitive = !case_sensitive;
346         break;
347       case 'b':
348         beta = !beta;
349         break;
350       case 't':
351         threshold1 = atof(optarg);
352         break;
353       case 'T':
354         threshold2 = atof(optarg);
355         break;
356       case 'I':
357         strcat(ignore_chars,optarg);
358         break;
359       case 'd':
360         debug = atoi(optarg);
361         break;
362       default:
363         usage();        
364       }
365
366   /* get the file names */
367   num_files = argc-optind;
368   file_names = &argv[optind];
369
370   if (num_files < 2)
371     usage();
372
373   /* process the files */
374   process_files();
375
376   dump_word_table();
377 }