home *** CD-ROM | disk | FTP | other *** search
/ Education Sampler 1992 [NeXTSTEP] / Education_1992_Sampler.iso / Programming / Source / WAIS / ir / sighash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-02-02  |  14.8 KB  |  448 lines
  1. /* WIDE AREA INFORMATION SERVER SOFTWARE:
  2.    No guarantees or restrictions.  See the readme file for the full standard
  3.    disclaimer.
  4.  
  5.    Brewster@think.com
  6. */
  7.  
  8. /* The memory hashtables for building an index. */
  9. /* -brewster 5/90 */
  10.  
  11. /* main functions:
  12.  *   add_word
  13.  *   finished_add_word
  14.  *   look_up_word
  15.  *
  16.  * collect the number of occurances of each word.
  17.  *
  18.  */
  19.  
  20. /* To Do:
  21.  *  Improve the hashing functions.
  22.  */
  23.  
  24. #include <ctype.h>
  25. #include <string.h>     /* for strlen(), memset() */
  26.  
  27. #include "panic.h"
  28. #include "cutil.h"
  29. #include "irfiles.h"
  30. #include "sighash.h"
  31. #include "stoplist.h"
  32. #include "irext.h"
  33. #include "sigindex.h"
  34.  
  35. #ifdef UNIX
  36. #define PRINT_AS_INDEXING true /* also defined in irtfiles.c and irfiles.c */
  37. #else 
  38. #define PRINT_AS_INDEXING false
  39. #endif
  40.  
  41.  
  42. /*===========================*
  43.  *===  Hashing Functions  ===*
  44.  *===========================*/
  45.  
  46.  
  47. static long random_char_code _AP((long ch,long offset));
  48.   
  49. static long random_char_code(ch,offset)
  50. long ch;
  51. long offset;
  52. {
  53.   static long random_array_3[256] = 
  54.         {142L, 176L, 108L, 210L, 109L, 223L, 214L, 251L, 
  55.          102L, 86L, 91L, 9L, 247L, 139L, 115L, 71L, 
  56.          63L, 35L, 126L, 77L, 209L, 175L, 120L, 28L, 
  57.          44L, 198L, 21L, 125L, 245L, 250L, 10L, 119L, 
  58.          127L, 60L, 81L, 226L, 216L, 182L, 172L, 72L, 
  59.          151L, 178L, 116L, 224L, 244L, 41L, 212L, 73L, 
  60.          190L, 248L, 173L, 18L, 82L, 27L, 97L, 26L, 
  61.          79L, 169L, 74L, 170L, 83L, 189L, 101L, 141L, 
  62.          230L, 55L, 135L, 220L, 187L, 201L, 95L, 39L, 
  63.          186L, 131L, 105L, 36L, 255L, 203L, 155L, 84L, 
  64.          160L, 75L, 254L, 235L, 51L, 243L, 158L, 14L, 
  65.          148L, 167L, 149L, 96L, 68L, 161L, 45L, 233L, 
  66.          11L, 19L, 3L, 38L, 195L, 48L, 144L, 15L, 
  67.          171L, 94L, 180L, 29L, 252L, 181L, 80L, 4L, 
  68.          20L, 213L, 23L, 143L, 7L, 236L, 76L, 110L, 
  69.          22L, 58L, 17L, 253L, 66L, 246L, 40L, 112L, 
  70.          179L, 130L, 87L, 124L, 240L, 193L, 107L, 165L, 
  71.          202L, 31L, 106L, 43L, 93L, 99L, 147L, 199L, 
  72.          129L, 197L, 32L, 229L, 150L, 46L, 157L, 128L, 
  73.          136L, 153L, 121L, 113L, 237L, 194L, 218L, 104L, 
  74.          78L, 184L, 62L, 159L, 227L, 222L, 47L, 53L, 
  75.          1L, 24L, 118L, 177L, 49L, 185L, 98L, 90L, 
  76.          34L, 192L, 200L, 221L, 232L, 146L, 114L, 137L, 
  77.          67L, 225L, 154L, 241L, 50L, 56L, 145L, 5L, 
  78.          188L, 207L, 231L, 228L, 6L, 183L, 219L, 217L, 
  79.          156L, 30L, 174L, 205L, 103L, 37L, 133L, 152L, 
  80.          117L, 196L, 164L, 249L, 239L, 64L, 242L, 59L, 
  81.          168L, 2L, 162L, 13L, 92L, 85L, 70L, 0L, 
  82.          52L, 65L, 166L, 163L, 215L, 69L, 140L, 25L, 
  83.          33L, 100L, 42L, 54L, 88L, 206L, 122L, 57L, 
  84.          16L, 208L, 134L, 132L, 138L, 89L, 8L, 234L, 
  85.          12L, 238L, 111L, 204L, 61L, 211L, 191L, 123L};
  86.  
  87.  
  88.     return(random_array_3[ (offset + (ch & 0xFF)) % 256]);
  89. }
  90.  
  91. /* assumes the word has been downcased already */
  92.  
  93. static long hash_word(wd,below_n)
  94. char *wd;
  95. long below_n;
  96. {
  97.   static long random_array_2[256] = 
  98.         {818L, 789L, 854L, 862L, 704L, 1019L, 390L, 887L, 
  99.          93L, 204L, 269L, 59L, 743L, 219L, 191L, 769L, 
  100.          911L, 435L, 805L, 448L, 142L, 1000L, 149L, 264L, 
  101.          639L, 504L, 699L, 934L, 266L, 661L, 318L, 211L, 
  102.          117L, 549L, 90L, 536L, 378L, 944L, 400L, 599L, 
  103.          592L, 883L, 985L, 606L, 759L, 456L, 581L, 119L, 
  104.          106L, 310L, 412L, 931L, 233L, 561L, 973L, 870L, 
  105.          377L, 349L, 334L, 354L, 249L, 585L, 799L, 899L, 
  106.          545L, 553L, 848L, 625L, 438L, 890L, 791L, 1014L, 
  107.          337L, 374L, 489L, 146L, 123L, 907L, 977L, 22L, 
  108.          396L, 241L, 198L, 424L, 136L, 715L, 867L, 684L, 
  109.          560L, 244L, 293L, 1017L, 397L, 778L, 725L, 78L, 
  110.          184L, 656L, 389L, 635L, 982L, 158L, 203L, 878L, 
  111.          323L, 394L, 73L, 18L, 837L, 996L, 58L, 62L, 
  112.          161L, 451L, 534L, 746L, 485L, 222L, 25L, 666L, 
  113.          28L, 21L, 420L, 147L, 522L, 74L, 474L, 362L, 
  114.          253L, 172L, 195L, 622L, 559L, 790L, 288L, 455L, 
  115.          263L, 538L, 355L, 417L, 810L, 576L, 685L, 797L, 
  116.          641L, 315L, 347L, 786L, 487L, 966L, 579L, 181L, 
  117.          499L, 429L, 688L, 140L, 278L, 719L, 186L, 872L, 
  118.          997L, 319L, 173L, 882L, 1008L, 573L, 431L, 830L, 
  119.          774L, 654L, 235L, 121L, 925L, 529L, 593L, 92L, 
  120.          954L, 434L, 213L, 79L, 284L, 510L, 763L, 655L, 
  121.          300L, 447L, 4L, 461L, 506L, 88L, 99L, 459L, 
  122.          220L, 780L, 523L, 178L, 303L, 578L, 287L, 827L, 
  123.          419L, 521L, 114L, 703L, 664L, 892L, 304L, 876L, 
  124.          352L, 331L, 35L, 896L, 341L, 450L, 812L, 350L, 
  125.          316L, 705L, 815L, 935L, 15L, 572L, 503L, 467L, 
  126.          306L, 976L, 118L, 760L, 807L, 809L, 339L, 442L, 
  127.          758L, 546L, 327L, 527L, 537L, 383L, 82L, 531L, 
  128.          728L, 428L, 768L, 675L, 814L, 919L, 133L, 682L, 
  129.          906L, 163L, 716L, 692L, 174L, 464L, 708L, 922L};
  130.  
  131.     long i;
  132.     long answer = 0;
  133.     for (i = 0; i < strlen(wd); i++) {
  134.         answer = answer ^ (random_array_2[i % 256] +
  135.                    ((0 == (i & 1)) ? 
  136.                     random_char_code((long)wd[i], i)
  137.                     : (random_char_code((long)wd[i], i))
  138.                     << 8));            
  139.     }
  140.     return(answer % below_n);
  141. }
  142.  
  143. static long hash_word_2 _AP((char *wd));
  144. static long hash_word_2(wd)
  145. char *wd;
  146. {
  147.   long hash = hash_word(wd, ((1L << (8 * DICTIONARY_ENTRY_HASH_CODE_SIZE))
  148.                  - 2));
  149.   return(1 + hash);
  150.                               
  151. }
  152.  
  153.  
  154.  
  155. /* ===============================
  156.    ===  Word Memory Hashtable  ===
  157.    =============================== */
  158.  
  159. static long find_location _AP((char* word,word_memory_hashtable* 
  160.                    the_word_memory_hashtable));
  161.  
  162. static long 
  163. find_location(word,the_word_memory_hashtable)
  164. char* word;
  165. word_memory_hashtable* the_word_memory_hashtable;
  166. /* returns the location that the word should go (or is).  returns -1 if 
  167.  * the hashtable is full and the word is not there
  168.  */
  169. {
  170.   long hash_code = hash_word(word, the_word_memory_hashtable->size);
  171.   long i;
  172.   long hash_code_2 = hash_word_2(word);
  173.  
  174.   for(i = hash_code; i < (hash_code + the_word_memory_hashtable->size); 
  175.       i++){
  176.     long index = i % the_word_memory_hashtable->size; 
  177.     if(NULL == the_word_memory_hashtable->contents[index]){
  178.       /* found an open spot, return it */
  179.       return(index);
  180.     }
  181.     else 
  182.       if(hash_code_2 == the_word_memory_hashtable->contents[index]->hash_code
  183.      &&
  184.      strcmp(word, the_word_memory_hashtable->contents[index]->word) == 0){
  185.     /* we win, return it */
  186.     return(index);
  187.       }
  188.     /* keep looking */
  189.   }
  190.   return(-1);
  191. }
  192.  
  193. /* this pushes all word entries to the top of the word_memory_hashtable
  194.  * therefore messing up the hashing order, but allows for quick sorting
  195.  * just before dumping to disk.
  196.  */
  197. void collapse_word_memory_hashtable(the_word_memory_hashtable)
  198. word_memory_hashtable *the_word_memory_hashtable;
  199. {
  200.   long insert_index = 0;
  201.   long extract_index;
  202.   for(extract_index = 0; extract_index < the_word_memory_hashtable->size;
  203.       extract_index++){
  204.     word_entry *entry = the_word_memory_hashtable->contents[extract_index];
  205.     if(NULL != entry)
  206.       the_word_memory_hashtable->contents[insert_index++] = entry;
  207.   }
  208. }
  209.  
  210. static int word_entry_compare _AP((word_entry**i,word_entry** j));
  211.  
  212. static int word_entry_compare(i,j)
  213. word_entry **i;
  214. word_entry **j;
  215. {
  216.   return(strcmp((*i)->word, (*j)->word));
  217. }
  218.  
  219. /* assumes that the word_memory_hashtable has been compressed */
  220. void sort_word_memory_hashtable(the_word_memory_hashtable)
  221. word_memory_hashtable *the_word_memory_hashtable;
  222. {
  223.   qsort(the_word_memory_hashtable->contents,
  224.     the_word_memory_hashtable->number_of_entries,
  225.     (size_t)sizeof(char *),
  226.     word_entry_compare);
  227. }
  228.  
  229.       
  230. /* for     debugging */
  231. void print_word_memory_hashtable(the_word_memory_hashtable)
  232. word_memory_hashtable* the_word_memory_hashtable;
  233. {
  234.   if (NULL == the_word_memory_hashtable){
  235.     cprintf(PRINT_AS_INDEXING, "No Hashtable allocated\n");
  236.     return;
  237.   }
  238.   cprintf(PRINT_AS_INDEXING, "Number of entries possible: %ld\n", 
  239.       the_word_memory_hashtable->size);
  240.   cprintf(PRINT_AS_INDEXING, "Number of entries allocated: %ld\n",
  241.       the_word_memory_hashtable->number_of_entries);
  242.   if(NULL != the_word_memory_hashtable->contents){
  243.     long i;
  244.     /* print the entries */
  245.     printf("The entries are:\n");
  246.     for(i = 0; i < the_word_memory_hashtable->size; i++){
  247.       if(NULL != the_word_memory_hashtable->contents[i]){
  248.     printf(" Position: %ld word: \"%s\" %ld occurances\n", i, 
  249.            the_word_memory_hashtable->contents[i]->word,
  250.            the_word_memory_hashtable->contents[i]->number_of_occurances);    
  251.       }
  252.     }
  253.   }
  254. }
  255.  
  256. static word_entry* look_up_word _AP((char* word,word_memory_hashtable*
  257.                      the_word_memory_hashtable));
  258.   
  259. static word_entry* 
  260. look_up_word(word,the_word_memory_hashtable)
  261. char* word;
  262. word_memory_hashtable* the_word_memory_hashtable;
  263. {
  264.   /* looks up the word in the dictionary and returns
  265.    * a pointer to the word_entry.
  266.    * If is not present, then it mallocs a new word entry.
  267.    */
  268.   /* this is a pretty dumb hashing scheme XXX */
  269.   long index = find_location(word, the_word_memory_hashtable);
  270.   if(-1 == index){
  271.     panic("the hashtable is completely full.  It should have been grown\n");
  272.   }
  273.   if(NULL == the_word_memory_hashtable->contents[index]){
  274.     if (the_word_memory_hashtable->number_of_entries < 
  275.     the_word_memory_hashtable->word_entry_block_size) {
  276.       /* make a new entry */
  277.       word_entry *new_entry =    /* s_malloc(sizeof(word_entry)); */
  278.     &(the_word_memory_hashtable->word_entry_block
  279.       [the_word_memory_hashtable->number_of_entries++]);
  280.     }
  281.     else panic("Ran out of word hashtable entries\n");
  282.  
  283.     strncpy(new_entry->word, word, MAX_WORD_LENGTH);
  284.     new_entry->hash_code = hash_word_2(word);      
  285.     new_entry->number_of_occurances = 0;
  286.         
  287.     the_word_memory_hashtable->contents[index] = new_entry;
  288.     return(new_entry);
  289.   }
  290.   else{
  291.     return(the_word_memory_hashtable->contents[index]);
  292.   }
  293. }
  294.  
  295. /* adds a word to the word_memory_hashtable. Currently it
  296.  * ignores the character position XXX.  
  297.  * Returns the 0 if successful. See irext.h for more documentation.
  298.  */
  299. long add_word(word, char_pos, line_pos,
  300.           weight, doc_id, date, db)
  301.      char *word;    /* the word to be indexed, this could be a
  302.                word pair. If NULL there are no more words
  303.                to be indexed */
  304.      long char_pos;    /* the position of the start of the
  305.                word */
  306.      long line_pos;    /* this is passed for the best
  307.                section calculation */
  308.      long weight;    /* how important the word looks
  309.                syntactically (such as is it bold)
  310.                NOT used by signature system */
  311.      long doc_id;     /* current document, this will never be 0 */
  312.      time_t date; /* display day of this document, 0 if not known */
  313.      database* db; /* database to insert the document */
  314. {
  315.   /* look up the word in the word_memory_hashtable */
  316.   /* creates it if necessary */    
  317.   word_entry* wrd_entry;
  318.   word_memory_hashtable * the_word_memory_hashtable = db->the_word_memory_hashtable;
  319.   /* printf("Word: '%s' doc_id: %ld, pos: %ld, weight: %ld\n",
  320.      word, doc_id, char_pos, weight); */
  321.   
  322.   if(NULL == db->the_word_memory_hashtable){
  323.     panic("The memory word hashtable is not defined.");
  324.   }
  325.  
  326.   the_word_memory_hashtable->number_of_words_indexed ++;
  327.   wrd_entry = look_up_word(word, the_word_memory_hashtable);
  328.   wrd_entry->number_of_occurances ++;
  329.   sig_add_word(word, char_pos, line_pos, weight, doc_id, date, db);
  330.   return(0L);
  331. }
  332.  
  333. void add_stop_words(the_word_memory_hashtable)
  334. word_memory_hashtable *the_word_memory_hashtable;
  335.      /* add the stop words to the hashtable.  this must be done before
  336.     adding other words */
  337. {
  338.   init_stop_list();
  339.   while(true){
  340.     char *word = next_stop_word();
  341.     word_entry* wrd_entry;
  342.  
  343.     if(NULL == word)
  344.       break;
  345.     wrd_entry = look_up_word(word, the_word_memory_hashtable);
  346.     wrd_entry->number_of_occurances = STOP_WORD_FLAG;
  347.   }
  348. }
  349.  
  350. /* this clears the contents of the word_memory_hashtable */
  351. void clear_word_memory_hashtable(the_word_memory_hashtable)
  352. word_memory_hashtable *the_word_memory_hashtable;
  353. {
  354.   memset((char*)the_word_memory_hashtable->contents, 0,
  355.      ((long)the_word_memory_hashtable->size * 
  356.       sizeof(size_t)));
  357.   the_word_memory_hashtable->number_of_entries = 0;
  358.   the_word_memory_hashtable->number_of_words_indexed = 0;
  359. }
  360.  
  361.  
  362. /* Size is in the number of entries.  
  363.    flush_after_n_words sets the hashtable flush parameter.
  364.    Returns TRUE if it succeeds. */
  365. word_memory_hashtable * init_word_memory_hashtable(size,flush_after_n_words,the_word_memory_hashtable)
  366. long size;
  367. long flush_after_n_words;
  368. word_memory_hashtable* the_word_memory_hashtable;
  369. {
  370.   if(NULL != the_word_memory_hashtable){
  371.     /* then displose of the old one */
  372.     if(NULL != the_word_memory_hashtable->contents)
  373.       s_free(the_word_memory_hashtable->contents);
  374.       s_free(the_word_memory_hashtable->word_entry_block);
  375.   }
  376.   the_word_memory_hashtable = 
  377.     (word_memory_hashtable*)s_malloc((size_t)sizeof(word_memory_hashtable));
  378.  
  379.   the_word_memory_hashtable->size = size;
  380.   
  381.   the_word_memory_hashtable->word_entry_block_size = size;
  382.     
  383.   the_word_memory_hashtable->contents = 
  384.     (word_entry **)s_malloc((size_t)(the_word_memory_hashtable->size
  385.                      * sizeof(size_t)));
  386.   the_word_memory_hashtable->word_entry_block =
  387.     (word_entry *)s_malloc((size_t)(the_word_memory_hashtable->word_entry_block_size
  388.                     * sizeof(word_entry)));
  389.  
  390.   if(NULL == the_word_memory_hashtable->contents){
  391.     panic("Could not malloc for the word hashtable\n");
  392.     return(NULL);
  393.   }
  394.   /* clear the hashtable the slow by safe way
  395.   for(i = 0; i < the_word_memory_hashtable->size; i++){
  396.     the_word_memory_hashtable->contents[i] = (word_entry*)NULL;
  397.   }
  398.   */
  399.   clear_word_memory_hashtable(the_word_memory_hashtable);
  400.  
  401.   /* add the stopwords to the index */
  402.   add_stop_words(the_word_memory_hashtable);
  403.      
  404.   the_word_memory_hashtable->flush_after_n_words = 
  405.     flush_after_n_words;
  406.  
  407.   the_word_memory_hashtable->growth_factor = 2.0;
  408.   the_word_memory_hashtable->grow_when_this_full = .5;
  409.   
  410.   return(the_word_memory_hashtable);
  411. }
  412.  
  413. long finished_add_word(db)
  414. database *db;
  415. {
  416.   /* write out the dictioanry */
  417.   long i;
  418.  
  419.   db->number_of_words = db->the_word_memory_hashtable->number_of_entries;
  420.   init_dict_file_for_writing(db);
  421.   collapse_word_memory_hashtable(db->the_word_memory_hashtable);
  422.   sort_word_memory_hashtable(db->the_word_memory_hashtable);
  423.   for(i = 0; i < db->the_word_memory_hashtable->number_of_entries; i++){
  424.     word_entry * entry = db->the_word_memory_hashtable->contents[i];
  425.     if(0 == (STOP_WORD_FLAG & entry->number_of_occurances)){
  426.       /* write out the dictionary entry */
  427.       /* printf("Adding word: %s %ld entries\n", entry->word, entry->number_of_occurances); */
  428.       add_word_to_dictionary(entry->word, entry->number_of_occurances,
  429.                  entry->number_of_occurances, db);
  430.     }
  431.   }
  432.   return(sig_finished_add_word(db));
  433. }
  434.  
  435. long init_add_word(db, hashtable_size, flush_after_n_words)
  436.      database *db;
  437.      long hashtable_size;
  438.      long flush_after_n_words;
  439. {
  440.   db->the_word_memory_hashtable =
  441.     init_word_memory_hashtable(hashtable_size, 
  442.                    flush_after_n_words, 
  443.                    db->the_word_memory_hashtable);
  444.   sig_init_add_word(db, hashtable_size, flush_after_n_words);
  445.   return(0);
  446. }
  447.  
  448.