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 }