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