home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / Tools / glimpse-2.1 / compress / tbuild.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-16  |  9.3 KB  |  308 lines
  1. /* Copyright (c) 1994 Burra Gopal, Udi Manber.  All Rights Reserved. */
  2.  
  3. /*
  4.  * build.c:     Reads a file = list of indices and hashes frequently used
  5.  *        words into a hash-table for fast retrieval of a word's no.
  6.  *        Also maintains a string-table to get to the word from it no.
  7.  */
  8.  
  9. #include "defs.h"
  10. /* small tables are ok since computation is a 1-time job: plus we need the extra space if we put it in a library for glimpseindex */
  11. extern hash_entry *get_small_hash(), *insert_small_hash();
  12.  
  13. hash_entry *dict_hash_table[SMALL_HASH_TABLE_SIZE];
  14. hash_entry *freq_strings_table[MAX_WORD_LEN+2];
  15. int freq_strings_num[MAX_WORD_LEN+2];
  16. extern int MAX_WORDS;
  17. extern int RESERVED_CHARS;
  18.  
  19. /*
  20.  * Computes the dictionary for the compression routines: they need two things:
  21.  * 1. A hash-table which maps words to word numbers.
  22.  * 2. A string-table which maps word numbers to offsets where the word begins
  23.  *    in the input file to this program (default DEF_INDEX_FILE).
  24.  * They are o/p in two output files, hash_file and string_file (default).
  25.  *
  26.  * Algorithm: first build the hash table of atmost 65536 words. Then traverse
  27.  * the table and output the hash/string files in the above format.
  28.  */
  29. int
  30. compute_dictionary(THRESHOLD, FILEBLOCKSIZE, SPECIAL_WORDS, comp_dir)
  31.     int    THRESHOLD, FILEBLOCKSIZE;
  32.     char    comp_dir[];
  33. {
  34.     int    c;
  35.     unsigned char    curline[MAX_NAME_LEN];
  36.     int    curchar = 0;
  37.     unsigned char    curword[MAX_NAME_LEN];
  38.     int    curfreq;
  39.     int    curoffset = 0;
  40.     int    curlen;
  41.     int    wordindex = 0;
  42.     FILE    *fp, *freqfp, *tempfp, *awkfp;
  43.     int    pid = getpid();
  44.     int    i;
  45.     hash_entry *e, **t, *p;
  46.     int    dummy, offset, len;
  47.     unsigned char    s[MAX_LINE_LEN];
  48.     unsigned char    rands[MAX_LINE_LEN];
  49.     char    index_file[MAX_LINE_LEN], string_file[MAX_LINE_LEN], hash_file[MAX_LINE_LEN], freq_file[MAX_LINE_LEN];
  50.  
  51.         strcpy(hash_file, comp_dir);
  52.         strcat(hash_file, "/");
  53.         strcat(hash_file, DEF_HASH_FILE);
  54.         strcpy(freq_file, comp_dir);
  55.         strcat(freq_file, "/");
  56.         strcat(freq_file, DEF_FREQ_FILE);
  57.         strcpy(string_file, comp_dir);
  58.         strcat(string_file, "/");
  59.         strcat(string_file, DEF_STRING_FILE);
  60.         strcpy(index_file, comp_dir);
  61.         strcat(index_file, "/");
  62.         strcat(index_file, DEF_INDEX_FILE);
  63.  
  64.     memset(dict_hash_table, '\0', sizeof(hash_entry *) * SMALL_HASH_TABLE_SIZE);
  65.     memset(freq_strings_table, '\0', sizeof(hash_entry *) * (MAX_WORD_LEN+2));
  66.     memset(freq_strings_num, '\0', sizeof(int) * (MAX_WORD_LEN+2));
  67.     if (THRESHOLD < 0) THRESHOLD = DEF_THRESHOLD;
  68.     if (SPECIAL_WORDS < 0) SPECIAL_WORDS = DEF_SPECIAL_WORDS;
  69.     if (FILEBLOCKSIZE < 0) FILEBLOCKSIZE = DEF_BLOCKSIZE;
  70.  
  71.     if (THRESHOLD < MIN_WORD_LEN || THRESHOLD > MAX_THRESHOLD) {
  72.         fprintf(stderr, "threshold must be in [%d, %d]\n", MIN_WORD_LEN, MAX_THRESHOLD);
  73.         return -1;
  74.     }
  75.  
  76.     if ((SPECIAL_WORDS < 0) || (SPECIAL_WORDS > 256-MAX_SPECIAL_CHARS)) {
  77.         fprintf(stderr, "invalid special words %d: must be in [0, %d]\n", SPECIAL_WORDS, 256-MAX_SPECIAL_CHARS);
  78.         return -1;
  79.     }
  80.     RESERVED_CHARS = SPECIAL_WORDS + MAX_SPECIAL_CHARS;
  81.     MAX_WORDS = MAX_LSB*(256-RESERVED_CHARS);
  82.  
  83.     if ((fp = fopen(index_file, "r")) == NULL) {
  84.         fprintf(stderr, "cannot open for reading: %s\n", index_file);
  85.         return -1;
  86.     }
  87.  
  88.     sprintf(s, "/tmp/temp%d", pid);
  89.     if ((tempfp = fopen(s, "w")) == NULL) {
  90.         fprintf(stderr, "cannot open for writing: %s\n", s);
  91.         fclose(fp);
  92.         return -1;
  93.     }
  94.  
  95.     while((c = getc(fp)) != EOF) {
  96.         if (curchar >= MAX_NAME_LEN) {
  97.             curchar = 0;
  98.             while((c = getc(fp) != '\n') && (c != EOF));
  99.             if (c == EOF) break;
  100.             else continue;
  101.         }
  102.         curline[curchar++] = (unsigned char)c;
  103.         if (c == '\n') {    /* reached end of record */
  104.             int    i = 0;
  105.  
  106.             if (curline[0] == '%') {    /* initial lines */
  107.                 curchar = 0;
  108.                 continue;
  109.             }
  110.             curword[0] = '\0';
  111.             while ((i<curchar) && (curline[i] != WORD_END_MARK)) {
  112.                 curword[i] = curline[i]; i++;
  113.             }
  114.             curword[i++] = '\0';    /* skip over WORD_END_MARK */
  115.             curlen = strlen((char *)curword);
  116.  
  117.             curfreq = 0;
  118.             while(i<curchar) {
  119.                 unsigned char tempbuf[MAX_NAME_LEN];
  120.                 int j = 0;
  121.  
  122.                 while(isdigit(curline[i])) tempbuf[j++] = curline[i++];
  123.                 tempbuf[j] = '\0';
  124.                 curfreq += atoi(tempbuf);
  125.                 i ++;    /* skip over current ' ' or '\n' */
  126.             }
  127. #if    0
  128.             printf("curlen=%d curfreq=%d\n", curlen, curfreq);
  129. #endif    /*0*/
  130.  
  131.             if ((curlen >= MIN_WORD_LEN) && (curlen*curfreq >= THRESHOLD)) {
  132.                 fprintf(tempfp, "%d %d %s\n", curlen*curfreq, curoffset, curword);
  133.                 wordindex ++;
  134.             }
  135.             curoffset += curchar;    /* offset cannot begin at 0: .index_list starts with %% and some junk */
  136.             curchar = 0;
  137. #if    0
  138.             printf("word=%s freq=%d\n", curword, curfreq);
  139. #endif    /*0*/
  140.         }
  141.     }
  142.     fclose(fp);
  143.  
  144.     /*
  145.      * Now chose MAX_WORDS words with highest frequency.
  146.      */
  147.     fflush(tempfp);
  148.     fclose(tempfp);
  149.     if (wordindex <= SPECIAL_WORDS) {
  150.         fprintf(stderr, "Warning: very small dictionary with only %d words!\n", wordindex);
  151.     }
  152.     sprintf(s, "sort -n -r /tmp/temp%d > /tmp/sort%d\n", pid, pid);
  153.     system(s);
  154.     sprintf(s, "rm /tmp/temp%d\n", pid);
  155.     system(s);
  156.     sprintf(s, "head -%d /tmp/sort%d > /tmp/temp%d\n", MAX_WORDS, pid, pid);
  157.     system(s);
  158.  
  159.     /*
  160.      * The first ultra-frequent 32 words are stored in a separate table sorted by
  161.      * lengths and within that according to alphabetical order (=canonical order).
  162.      */
  163.     sprintf(s, "/tmp/temp%d", pid);
  164.     if ((tempfp = fopen(s, "r")) == NULL) {
  165.         fprintf(stderr, "cannot open for reading: %s\n", s);
  166.         return -1;
  167.     }
  168.     for (i=0; i<SPECIAL_WORDS; i++) {
  169.         if (3 != fscanf(tempfp, "%d %d %s\n", &dummy, &offset, s))
  170.             break;
  171.         len = strlen((char *)s);
  172.         e = (hash_entry *)malloc(sizeof(hash_entry));
  173.         e->word = (char *)malloc(len + 2);
  174.         e->next = NULL;
  175.         strcpy(e->word, (char *)s);
  176.         /* I'm not worried about the offsets now */
  177.         t = &freq_strings_table[len];
  178.         while(*t != NULL) {
  179.             if (strcmp((char *)s, (*t)->word) < 0) {
  180.                 e->next = *t;
  181.                 break;
  182.             }
  183.             t = &(*t)->next;
  184.         }
  185.         *t = e;    /* valid in both cases */
  186.         freq_strings_num[len]++;
  187.     }
  188.  
  189.     /*
  190.      * Put all the other words in the hash/string tables
  191.      */
  192.     for (; i<MAX_WORDS; i++) {
  193.         if (3 != fscanf(tempfp, "%d %d %s", &dummy, &offset, s)) break;
  194.         insert_small_hash(dict_hash_table, s, strlen((char *)s), -1, offset);    /* dummy doesn't matter now: its is just a computed-value for sort */
  195.     }
  196.     fclose(tempfp);
  197.  
  198.     /*
  199.      * At this point, the hash-table and freq-words-table have been computed properly: dump them
  200.      */
  201.     if ((freqfp = fopen(freq_file, "w")) == NULL) {
  202.         fprintf(stderr, "cannot open for writing: %s\n", freq_file);
  203.         return -1;
  204.     }
  205.     /* random number signature for this set of dictionaries will be in the freq-file (.glimpse_quick) */
  206.     srand(getpid());
  207.     rands[0] = '\0';
  208.     while (strlen((char*)rands) < SIGNATURE_LEN - 1) {
  209.         sprintf(s, "%x", rand());
  210.         strcat((char *)rands, (char *)s);
  211.     }
  212.     fwrite(rands, 1, SIGNATURE_LEN - 1, freqfp);
  213.     fputc('\n', freqfp);
  214.     fprintf(freqfp, "%d\n", SPECIAL_WORDS);
  215.     for (i=0; i<=MAX_WORD_LEN; i++) {
  216.         if (freq_strings_num[i] <= 0) continue;
  217.         fprintf(freqfp, "%d %d\n", i, freq_strings_num[i]);
  218.         e = freq_strings_table[i];
  219.         while (e!=NULL) {
  220.             fprintf(freqfp, "%s\n", e->word);
  221.             p = e;
  222.             e = e->next;
  223.             free(p->word);
  224.             free(p);
  225.         }
  226.     }
  227.     fflush(freqfp);
  228.     fclose(freqfp);
  229.     if (!dump_small_hash(dict_hash_table, hash_file)) return -1;
  230.  
  231.     /*
  232.      * Now sort chosen ones case-insensitively according to the name so that
  233.      * those words all fall into the same page offset in the hash/string tables.
  234.      */
  235.  
  236.     /* Alter order of words in .hash_table */
  237.     sprintf(s, "/tmp/sort%d.a", pid);
  238.     if ((awkfp = fopen(s, "w")) == NULL) {
  239.         fprintf(stderr, "cannot open for writing: %s\n", s);
  240.         return -1;
  241.     }
  242.     sprintf(s, "BEGIN {}\n{print $3 \" \" $2 \" \" $1}\nEND {}\n");
  243.     fwrite(s, 1, strlen((char *)s), awkfp);
  244.     fflush(awkfp);
  245.     fclose(awkfp);
  246. #if    0
  247.     sprintf(s, "cat /tmp/sort%d.a\n", pid);
  248.     system(s);
  249. #endif    /*0*/
  250. #if    0
  251.     printf("stage1:");
  252.     getchar();
  253. #endif    /*0*/
  254.     sprintf(s, "awk -f /tmp/sort%d.a < %s > /tmp/sort%d\n", pid, hash_file, pid);
  255.     system(s);
  256.     sprintf(s, "sort -d -f /tmp/sort%d > /tmp/temp%d\n", pid, pid);
  257.     system(s);
  258.  
  259.     sprintf(s, "/tmp/sort%d.a", pid);
  260.     if ((awkfp = fopen(s, "w")) == NULL) {
  261.         fprintf(stderr, "cannot open for writing: %s\n", s);
  262.         return -1;
  263.     }
  264.     sprintf(s, "%s", "BEGIN {}\n{print $3 \" \" NR-1 \" \" $1}\nEND {}\n");
  265.     fwrite(s, 1, strlen((char *)s), awkfp);
  266.     fflush(awkfp);
  267.     fclose(awkfp);
  268.  
  269.     sprintf(s, "awk -f /tmp/sort%d.a < /tmp/temp%d > %s\n", pid, pid, hash_file);    /* reorder and put in new word numbers */
  270.     system(s);
  271.  
  272. #if    0
  273.     printf("stage2:");
  274.     getchar();
  275. #endif    /*0*/
  276.     /* Now extract string-table, which is the set of 2nd components of the hash-table */
  277.     sprintf(s, "/tmp/sort%d.a", pid);
  278.     if ((awkfp = fopen(s, "w")) == NULL) {
  279.         fprintf(stderr, "cannot open for writing: %s\n", s);
  280.         return -1;
  281.     }
  282.     sprintf(s, "%s", "BEGIN {}\n{print $3}\nEND {}\n");
  283.     fwrite(s, 1, strlen((char *)s), awkfp);
  284.     fflush(awkfp);
  285.     fclose(awkfp);
  286. #if    0
  287.     sprintf(s, "cat /tmp/sort%d.a\n", pid);
  288.     system(s);
  289. #endif    /*0*/
  290.     sprintf(s, "awk -f /tmp/sort%d.a < %s > %s\n", pid, hash_file, string_file);
  291.     system(s);
  292.  
  293. #if    0
  294.     printf("stage3:"); getchar();
  295. #endif    /*0*/
  296.     /*
  297.      * Now pad the hash-file and string files and store indices to words at
  298.      * page boundary so that search() on compressed files can be made fast
  299.      * -- it need not load the whole hash-table: just the page where the
  300.      * word occurs. The index files are very small (< 1K) so read is fast.
  301.      * The padded files are in binary -- this is what tcompress/tuncompress
  302.      * read-in. This is done to save space.
  303.      */
  304.     pad_hash_file(hash_file, FILEBLOCKSIZE);
  305.     pad_string_file(string_file, FILEBLOCKSIZE);
  306.     return 0;
  307. }
  308.