src/relevance.c

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