src/relevance.c

   1 /*
   2  * $Id: relevance.c,v 1.3 2007-01-03 06:23:44 quinn Exp $
   3  */
   4
   5 #include <ctype.h>
   6 #include <math.h>
   7 #include <stdlib.h>
   8
   9 #include "relevance.h"
  10 #include "pazpar2.h"
  11
  12 struct relevance
  13 {
  14     int *doc_frequency_vec;
  15     int vec_len;
  16     struct word_trie *wt;
  17     NMEM nmem;
  18 };
  19
  20 // We use this data structure to recognize terms in input records,
  21 // and map them to record term vectors for counting.
  22 struct word_trie
  23 {
  24     struct
  25     {
  26         struct word_trie *child;
  27         int termno;
  28     } list[26];
  29 };
  30
  31 static struct word_trie *create_word_trie_node(NMEM nmem)
  32 {
  33     struct word_trie *res = nmem_malloc(nmem, sizeof(struct word_trie));
  34     int i;
  35     for (i = 0; i < 26; i++)
  36     {
  37         res->list[i].child = 0;
  38         res->list[i].termno = -1;
  39     }
  40     return res;
  41 }
  42
  43 static void word_trie_addterm(NMEM nmem, struct word_trie *n, const char *term, int num)
  44 {
  45     while (*term) {
  46         int c = tolower(*term);
  47         if (c < 'a' || c > 'z')
  48             term++;
  49         else
  50         {
  51             c -= 'a';
  52             if (!*(++term))
  53                 n->list[c].termno = num;
  54             else
  55             {
  56                 if (!n->list[c].child)
  57                 {
  58                     struct word_trie *new = create_word_trie_node(nmem);
  59                     n->list[c].child = new;
  60                 }
  61                 word_trie_addterm(nmem, n->list[c].child, term, num);
  62             }
  63             break;
  64         }
  65     }
  66 }
  67
  68 #define raw_char(c) (((c) >= 'a' && (c) <= 'z') ? (c) - 'a' : -1)
  69
  70 static int word_trie_match(struct word_trie *t, const char *word, int *skipped)
  71 {
  72     int c = raw_char(tolower(*word));
  73
  74     if (!*word)
  75         return 0;
  76
  77     word++;
  78     (*skipped)++;
  79     if (!*word || raw_char(*word) < 0)
  80     {
  81         if (t->list[c].termno > 0)
  82             return t->list[c].termno;
  83         else
  84             return 0;
  85     }
  86     else
  87     {
  88         if (t->list[c].child)
  89         {
  90             return word_trie_match(t->list[c].child, word, skipped);
  91         }
  92         else
  93             return 0;
  94     }
  95
  96 }
  97
  98
  99 static struct word_trie *build_word_trie(NMEM nmem, const char **terms)
 100 {
 101     struct word_trie *res = create_word_trie_node(nmem);
 102     const char **p;
 103     int i;
 104
 105     for (i = 1, p = terms; *p; p++, i++)
 106         word_trie_addterm(nmem, res, *p, i);
 107     return res;
 108 }
 109
 110 struct relevance *relevance_create(NMEM nmem, const char **terms, int numrecs)
 111 {
 112     struct relevance *res = nmem_malloc(nmem, sizeof(struct relevance));
 113     const char **p;
 114     int i;
 115
 116     for (p = terms, i = 0; *p; p++, i++)
 117         ;
 118     res->vec_len = ++i;
 119     res->doc_frequency_vec = nmem_malloc(nmem, res->vec_len * sizeof(int));
 120     bzero(res->doc_frequency_vec, res->vec_len * sizeof(int));
 121     res->nmem = nmem;
 122     res->wt = build_word_trie(nmem, terms);
 123     return res;
 124 }
 125
 126 void relevance_newrec(struct relevance *r, struct record *rec)
 127 {
 128     if (!rec->term_frequency_vec)
 129     {
 130         rec->term_frequency_vec = nmem_malloc(r->nmem, r->vec_len * sizeof(int));
 131         bzero(rec->term_frequency_vec, r->vec_len * sizeof(int));
 132     }
 133 }
 134
 135
 136 // FIXME. The definition of a word is crude here.. should support
 137 // some form of localization mechanism?
 138 void relevance_countwords(struct relevance *r, struct record *head,
 139         const char *words, int multiplier)
 140 {
 141     while (*words)
 142     {
 143         char c;
 144         int res;
 145         int skipped;
 146         while (*words && (c = raw_char(tolower(*words))) < 0)
 147             words++;
 148         if (!*words)
 149             return;
 150         skipped = 0;
 151         if ((res = word_trie_match(r->wt, words, &skipped)))
 152         {
 153             words += skipped;
 154             head->term_frequency_vec[res] += multiplier;
 155         }
 156         else
 157         {
 158             while (*words && (c = raw_char(tolower(*words))) >= 0)
 159                 words++;
 160         }
 161         head->term_frequency_vec[0]++;
 162     }
 163 }
 164
 165 void relevance_donerecord(struct relevance *r, struct record *head)
 166 {
 167     int i;
 168
 169     for (i = 1; i < r->vec_len; i++)
 170         if (head->term_frequency_vec[i] > 0)
 171             r->doc_frequency_vec[i]++;
 172
 173     r->doc_frequency_vec[0]++;
 174 }
 175
 176 #ifdef FLOAT_REL
 177 static int comp(const void *p1, const void *p2)
 178 {
 179     float res;
 180     struct record **r1 = (struct record **) p1;
 181     struct record **r2 = (struct record **) p2;
 182     res = (*r2)->relevance - (*r1)->relevance;
 183     if (res > 0)
 184         return 1;
 185     else if (res < 0)
 186         return -1;
 187     else
 188         return 0;
 189 }
 190 #else
 191 static int comp(const void *p1, const void *p2)
 192 {
 193     struct record **r1 = (struct record **) p1;
 194     struct record **r2 = (struct record **) p2;
 195     return (*r2)->relevance - (*r1)->relevance;
 196 }
 197 #endif
 198
 199 // Prepare for a relevance-sorted read of up to num entries
 200 void relevance_prepare_read(struct relevance *rel, struct reclist *reclist)
 201 {
 202     int i;
 203     float *idfvec = xmalloc(rel->vec_len * sizeof(float));
 204
 205     // Calculate document frequency vector for each term.
 206     for (i = 1; i < rel->vec_len; i++)
 207     {
 208         if (!rel->doc_frequency_vec[i])
 209             idfvec[i] = 0;
 210         else
 211             idfvec[i] = log((float) rel->doc_frequency_vec[0] / rel->doc_frequency_vec[i]);
 212     }
 213     // Calculate relevance for each document
 214     for (i = 0; i < reclist->num_records; i++)
 215     {
 216         int t;
 217         struct record *rec = reclist->flatlist[i];
 218         float relevance;
 219         relevance = 0;
 220         for (t = 1; t < rel->vec_len; t++)
 221         {
 222             float termfreq;
 223             if (!rec->term_frequency_vec[0])
 224                 break;
 225             termfreq = (float) rec->term_frequency_vec[t] / rec->term_frequency_vec[0];
 226             relevance += termfreq * idfvec[t];
 227         }
 228         rec->relevance = (int) (relevance * 100000);
 229     }
 230     qsort(reclist->flatlist, reclist->num_records, sizeof(struct record*), comp);
 231     reclist->pointer = 0;
 232     xfree(idfvec);
 233 }
 234
 235 /*
 236  * Local variables:
 237  * c-basic-offset: 4
 238  * indent-tabs-mode: nil
 239  * End:
 240  * vim: shiftwidth=4 tabstop=8 expandtab
 241  */