src/relevance.c

   1 /*
   2  * $Id: relevance.c,v 1.2 2006-12-20 22:18:33 adam 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 len, int *skipped)
  71 {
  72     int c = raw_char(tolower(*word));
  73
  74     if (!len)
  75         return 0;
  76
  77     word++; len--;
  78     (*skipped)++;
  79     if (!len || 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, len, 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 len, int multiplier)
 140 {
 141     while (len)
 142     {
 143         char c;
 144         int res;
 145         int skipped;
 146         while (len && (c = raw_char(tolower(*words))) < 0)
 147         {
 148             words++;
 149             len--;
 150         }
 151         if (!len)
 152             return;
 153         skipped = 0;
 154         if ((res = word_trie_match(r->wt, words, len, &skipped)))
 155         {
 156             words += skipped;
 157             len -= skipped;
 158             head->term_frequency_vec[res] += multiplier;
 159         }
 160         else
 161         {
 162             while (len && (c = raw_char(tolower(*words))) >= 0)
 163             {
 164                 words++;
 165                 len--;
 166             }
 167         }
 168         head->term_frequency_vec[0]++;
 169     }
 170 }
 171
 172 void relevance_donerecord(struct relevance *r, struct record *head)
 173 {
 174     int i;
 175
 176     for (i = 1; i < r->vec_len; i++)
 177         if (head->term_frequency_vec[i] > 0)
 178             r->doc_frequency_vec[i]++;
 179
 180     r->doc_frequency_vec[0]++;
 181 }
 182
 183 #ifdef FLOAT_REL
 184 static int comp(const void *p1, const void *p2)
 185 {
 186     float res;
 187     struct record **r1 = (struct record **) p1;
 188     struct record **r2 = (struct record **) p2;
 189     res = (*r2)->relevance - (*r1)->relevance;
 190     if (res > 0)
 191         return 1;
 192     else if (res < 0)
 193         return -1;
 194     else
 195         return 0;
 196 }
 197 #else
 198 static int comp(const void *p1, const void *p2)
 199 {
 200     struct record **r1 = (struct record **) p1;
 201     struct record **r2 = (struct record **) p2;
 202     return (*r2)->relevance - (*r1)->relevance;
 203 }
 204 #endif
 205
 206 // Prepare for a relevance-sorted read of up to num entries
 207 void relevance_prepare_read(struct relevance *rel, struct reclist *reclist)
 208 {
 209     int i;
 210     float *idfvec = xmalloc(rel->vec_len * sizeof(float));
 211
 212     // Calculate document frequency vector for each term.
 213     for (i = 1; i < rel->vec_len; i++)
 214     {
 215         if (!rel->doc_frequency_vec[i])
 216             idfvec[i] = 0;
 217         else
 218             idfvec[i] = log((float) rel->doc_frequency_vec[0] / rel->doc_frequency_vec[i]);
 219     }
 220     // Calculate relevance for each document
 221     for (i = 0; i < reclist->num_records; i++)
 222     {
 223         int t;
 224         struct record *rec = reclist->flatlist[i];
 225         float relevance;
 226         relevance = 0;
 227         for (t = 1; t < rel->vec_len; t++)
 228         {
 229             float termfreq;
 230             if (!rec->term_frequency_vec[0])
 231                 break;
 232             termfreq = (float) rec->term_frequency_vec[t] / rec->term_frequency_vec[0];
 233             relevance += termfreq * idfvec[t];
 234         }
 235         rec->relevance = (int) (relevance * 100000);
 236     }
 237     qsort(reclist->flatlist, reclist->num_records, sizeof(struct record*), comp);
 238     reclist->pointer = 0;
 239     xfree(idfvec);
 240 }
 241
 242 /*
 243  * Local variables:
 244  * c-basic-offset: 4
 245  * indent-tabs-mode: nil
 246  * End:
 247  * vim: shiftwidth=4 tabstop=8 expandtab
 248  */