src/relevance.c

   1 /* $Id: relevance.c,v 1.9 2007-04-10 08:48:56 adam Exp $
   2    Copyright (c) 2006-2007, Index Data.
   3
   4 This file is part of Pazpar2.
   5
   6 Pazpar2 is free software; you can redistribute it and/or modify it under
   7 the terms of the GNU General Public License as published by the Free
   8 Software Foundation; either version 2, or (at your option) any later
   9 version.
  10
  11 Pazpar2 is distributed in the hope that it will be useful, but WITHOUT ANY
  12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14 for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with Pazpar2; see the file LICENSE.  If not, write to the
  18 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  19 02111-1307, USA.
  20  */
  21
  22 #include <ctype.h>
  23 #include <math.h>
  24 #include <stdlib.h>
  25
  26 #if HAVE_CONFIG_H
  27 #include <cconfig.h>
  28 #endif
  29
  30 #include "relevance.h"
  31 #include "pazpar2.h"
  32
  33 struct relevance
  34 {
  35     int *doc_frequency_vec;
  36     int vec_len;
  37     struct word_trie *wt;
  38     NMEM nmem;
  39 };
  40
  41 // We use this data structure to recognize terms in input records,
  42 // and map them to record term vectors for counting.
  43 struct word_trie
  44 {
  45     struct
  46     {
  47         struct word_trie *child;
  48         int termno;
  49     } list[26];
  50 };
  51
  52 static struct word_trie *create_word_trie_node(NMEM nmem)
  53 {
  54     struct word_trie *res = nmem_malloc(nmem, sizeof(struct word_trie));
  55     int i;
  56     for (i = 0; i < 26; i++)
  57     {
  58         res->list[i].child = 0;
  59         res->list[i].termno = -1;
  60     }
  61     return res;
  62 }
  63
  64 static void word_trie_addterm(NMEM nmem, struct word_trie *n, const char *term, int num)
  65 {
  66     while (*term) {
  67         int c = tolower(*term);
  68         if (c < 'a' || c > 'z')
  69             term++;
  70         else
  71         {
  72             c -= 'a';
  73             if (!*(++term))
  74                 n->list[c].termno = num;
  75             else
  76             {
  77                 if (!n->list[c].child)
  78                 {
  79                     struct word_trie *new = create_word_trie_node(nmem);
  80                     n->list[c].child = new;
  81                 }
  82                 word_trie_addterm(nmem, n->list[c].child, term, num);
  83             }
  84             break;
  85         }
  86     }
  87 }
  88
  89 #define raw_char(c) (((c) >= 'a' && (c) <= 'z') ? (c) - 'a' : -1)
  90
  91 static int word_trie_match(struct word_trie *t, const char *word, int *skipped)
  92 {
  93     int c = raw_char(tolower(*word));
  94
  95     if (!*word)
  96         return 0;
  97
  98     word++;
  99     (*skipped)++;
 100     if (!*word || raw_char(*word) < 0)
 101     {
 102         if (t->list[c].termno > 0)
 103             return t->list[c].termno;
 104         else
 105             return 0;
 106     }
 107     else
 108     {
 109         if (t->list[c].child)
 110         {
 111             return word_trie_match(t->list[c].child, word, skipped);
 112         }
 113         else
 114             return 0;
 115     }
 116
 117 }
 118
 119
 120 static struct word_trie *build_word_trie(NMEM nmem, const char **terms)
 121 {
 122     struct word_trie *res = create_word_trie_node(nmem);
 123     const char **p;
 124     int i;
 125
 126     for (i = 1, p = terms; *p; p++, i++)
 127         word_trie_addterm(nmem, res, *p, i);
 128     return res;
 129 }
 130
 131 struct relevance *relevance_create(NMEM nmem, const char **terms, int numrecs)
 132 {
 133     struct relevance *res = nmem_malloc(nmem, sizeof(struct relevance));
 134     const char **p;
 135     int i;
 136
 137     for (p = terms, i = 0; *p; p++, i++)
 138         ;
 139     res->vec_len = ++i;
 140     res->doc_frequency_vec = nmem_malloc(nmem, res->vec_len * sizeof(int));
 141     memset(res->doc_frequency_vec, 0, res->vec_len * sizeof(int));
 142     res->nmem = nmem;
 143     res->wt = build_word_trie(nmem, terms);
 144     return res;
 145 }
 146
 147 void relevance_newrec(struct relevance *r, struct record_cluster *rec)
 148 {
 149     if (!rec->term_frequency_vec)
 150     {
 151         rec->term_frequency_vec = nmem_malloc(r->nmem, r->vec_len * sizeof(int));
 152         memset(rec->term_frequency_vec, 0, r->vec_len * sizeof(int));
 153     }
 154 }
 155
 156
 157 // FIXME. The definition of a word is crude here.. should support
 158 // some form of localization mechanism?
 159 void relevance_countwords(struct relevance *r, struct record_cluster *cluster,
 160         const char *words, int multiplier)
 161 {
 162     while (*words)
 163     {
 164         char c;
 165         int res;
 166         int skipped;
 167         while (*words && (c = raw_char(tolower(*words))) < 0)
 168             words++;
 169         if (!*words)
 170             return;
 171         skipped = 0;
 172         if ((res = word_trie_match(r->wt, words, &skipped)))
 173         {
 174             words += skipped;
 175             cluster->term_frequency_vec[res] += multiplier;
 176         }
 177         else
 178         {
 179             while (*words && (c = raw_char(tolower(*words))) >= 0)
 180                 words++;
 181         }
 182         cluster->term_frequency_vec[0]++;
 183     }
 184 }
 185
 186 void relevance_donerecord(struct relevance *r, struct record_cluster *cluster)
 187 {
 188     int i;
 189
 190     for (i = 1; i < r->vec_len; i++)
 191         if (cluster->term_frequency_vec[i] > 0)
 192             r->doc_frequency_vec[i]++;
 193
 194     r->doc_frequency_vec[0]++;
 195 }
 196
 197 #ifdef GAGA
 198 #ifdef FLOAT_REL
 199 static int comp(const void *p1, const void *p2)
 200 {
 201     float res;
 202     struct record **r1 = (struct record **) p1;
 203     struct record **r2 = (struct record **) p2;
 204     res = (*r2)->relevance - (*r1)->relevance;
 205     if (res > 0)
 206         return 1;
 207     else if (res < 0)
 208         return -1;
 209     else
 210         return 0;
 211 }
 212 #else
 213 static int comp(const void *p1, const void *p2)
 214 {
 215     struct record_cluster **r1 = (struct record_cluster **) p1;
 216     struct record_cluster **r2 = (struct record_cluster **) p2;
 217     return (*r2)->relevance - (*r1)->relevance;
 218 }
 219 #endif
 220 #endif
 221
 222 // Prepare for a relevance-sorted read
 223 void relevance_prepare_read(struct relevance *rel, struct reclist *reclist)
 224 {
 225     int i;
 226     float *idfvec = xmalloc(rel->vec_len * sizeof(float));
 227
 228     // Calculate document frequency vector for each term.
 229     for (i = 1; i < rel->vec_len; i++)
 230     {
 231         if (!rel->doc_frequency_vec[i])
 232             idfvec[i] = 0;
 233         else
 234             idfvec[i] = log((float) rel->doc_frequency_vec[0] / rel->doc_frequency_vec[i]);
 235     }
 236     // Calculate relevance for each document
 237     for (i = 0; i < reclist->num_records; i++)
 238     {
 239         int t;
 240         struct record_cluster *rec = reclist->flatlist[i];
 241         float relevance;
 242         relevance = 0;
 243         for (t = 1; t < rel->vec_len; t++)
 244         {
 245             float termfreq;
 246             if (!rec->term_frequency_vec[0])
 247                 break;
 248             termfreq = (float) rec->term_frequency_vec[t] / rec->term_frequency_vec[0];
 249             relevance += termfreq * idfvec[t];
 250         }
 251         rec->relevance = (int) (relevance * 100000);
 252     }
 253 #ifdef GAGA
 254     qsort(reclist->flatlist, reclist->num_records, sizeof(struct record*), comp);
 255 #endif
 256     reclist->pointer = 0;
 257     xfree(idfvec);
 258 }
 259
 260 /*
 261  * Local variables:
 262  * c-basic-offset: 4
 263  * indent-tabs-mode: nil
 264  * End:
 265  * vim: shiftwidth=4 tabstop=8 expandtab
 266  */