src/relevance.c

   1 /* This file is part of Pazpar2.
   2    Copyright (C) 2006-2012 Index Data
   3
   4 Pazpar2 is free software; you can redistribute it and/or modify it under
   5 the terms of the GNU General Public License as published by the Free
   6 Software Foundation; either version 2, or (at your option) any later
   7 version.
   8
   9 Pazpar2 is distributed in the hope that it will be useful, but WITHOUT ANY
  10 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12 for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with this program; if not, write to the Free Software
  16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  17
  18 */
  19
  20 #if HAVE_CONFIG_H
  21 #include <config.h>
  22 #endif
  23
  24 #include <assert.h>
  25 #include <math.h>
  26 #include <stdlib.h>
  27
  28 #include "relevance.h"
  29 #include "session.h"
  30
  31 struct relevance
  32 {
  33     int *doc_frequency_vec;
  34     int vec_len;
  35     struct word_entry *entries;
  36     pp2_charset_token_t prt;
  37     NMEM nmem;
  38 };
  39
  40 struct word_entry {
  41     const char *norm_str;
  42     int termno;
  43     char *ccl_field;
  44     struct word_entry *next;
  45 };
  46
  47 int word_entry_match(struct word_entry *entries, const char *norm_str)
  48 {
  49     for (; entries; entries = entries->next)
  50     {
  51         if (!strcmp(norm_str, entries->norm_str))
  52             return entries->termno;
  53     }
  54     return 0;
  55 }
  56
  57 void relevance_countwords(struct relevance *r, struct record_cluster *cluster,
  58                           const char *words, int multiplier, const char *name)
  59 {
  60     int *mult = cluster->term_frequency_vec_tmp;
  61     const char *norm_str;
  62     int i, length = 0;
  63
  64     pp2_charset_token_first(r->prt, words, 0);
  65     for (i = 1; i < r->vec_len; i++)
  66         mult[i] = 0;
  67
  68     while ((norm_str = pp2_charset_token_next(r->prt)))
  69     {
  70         int res = word_entry_match(r->entries, norm_str);
  71         if (res)
  72         {
  73             assert(res < r->vec_len);
  74             mult[res] += multiplier;
  75         }
  76         length++;
  77     }
  78
  79     for (i = 1; i < r->vec_len; i++)
  80     {
  81         if (length > 0) /* only add if non-empty */
  82             cluster->term_frequency_vecf[i] += (double) mult[i] / length;
  83         cluster->term_frequency_vec[i] += mult[i];
  84     }
  85
  86     cluster->term_frequency_vec[0] += length;
  87 }
  88
  89 static void pull_terms(struct relevance *res, struct ccl_rpn_node *n)
  90 {
  91     char **words;
  92     int numwords;
  93     char *ccl_field;
  94     int i;
  95
  96     switch (n->kind)
  97     {
  98     case CCL_RPN_AND:
  99     case CCL_RPN_OR:
 100     case CCL_RPN_NOT:
 101     case CCL_RPN_PROX:
 102         pull_terms(res, n->u.p[0]);
 103         pull_terms(res, n->u.p[1]);
 104         break;
 105     case CCL_RPN_TERM:
 106         nmem_strsplit(res->nmem, " ", n->u.t.term, &words, &numwords);
 107         for (i = 0; i < numwords; i++)
 108         {
 109             const char *norm_str;
 110
 111             ccl_field = nmem_strdup_null(res->nmem, n->u.t.qual);
 112
 113             pp2_charset_token_first(res->prt, words[i], 0);
 114             while ((norm_str = pp2_charset_token_next(res->prt)))
 115             {
 116                 struct word_entry **e = &res->entries;
 117                 while (*e)
 118                     e = &(*e)->next;
 119                 *e = nmem_malloc(res->nmem, sizeof(**e));
 120                 (*e)->norm_str = nmem_strdup(res->nmem, norm_str);
 121                 (*e)->ccl_field = ccl_field;
 122                 (*e)->termno = res->vec_len++;
 123                 (*e)->next = 0;
 124             }
 125         }
 126         break;
 127     default:
 128         break;
 129     }
 130 }
 131
 132 struct relevance *relevance_create_ccl(pp2_charset_fact_t pft,
 133                                        NMEM nmem, struct ccl_rpn_node *query)
 134 {
 135     struct relevance *res = nmem_malloc(nmem, sizeof(*res));
 136     int i;
 137
 138     res->nmem = nmem;
 139     res->entries = 0;
 140     res->vec_len = 1;
 141     res->prt = pp2_charset_token_create(pft, "relevance");
 142
 143     pull_terms(res, query);
 144
 145     res->doc_frequency_vec = nmem_malloc(nmem, res->vec_len * sizeof(int));
 146     for (i = 0; i < res->vec_len; i++)
 147         res->doc_frequency_vec[i] = 0;
 148     return res;
 149 }
 150
 151 void relevance_destroy(struct relevance **rp)
 152 {
 153     if (*rp)
 154     {
 155         pp2_charset_token_destroy((*rp)->prt);
 156         *rp = 0;
 157     }
 158 }
 159
 160 void relevance_newrec(struct relevance *r, struct record_cluster *rec)
 161 {
 162     if (!rec->term_frequency_vec)
 163     {
 164         int i;
 165
 166         // term frequency [1,..] . [0] is total length of all fields
 167         rec->term_frequency_vec =
 168             nmem_malloc(r->nmem,
 169                         r->vec_len * sizeof(*rec->term_frequency_vec));
 170         for (i = 0; i < r->vec_len; i++)
 171             rec->term_frequency_vec[i] = 0;
 172
 173         // term frequency divided by length of field [1,...]
 174         rec->term_frequency_vecf =
 175             nmem_malloc(r->nmem,
 176                         r->vec_len * sizeof(*rec->term_frequency_vecf));
 177         for (i = 0; i < r->vec_len; i++)
 178             rec->term_frequency_vecf[i] = 0.0;
 179
 180         // for relevance_countwords (so we don't have to xmalloc/xfree)
 181         rec->term_frequency_vec_tmp =
 182             nmem_malloc(r->nmem,
 183                         r->vec_len * sizeof(*rec->term_frequency_vec_tmp));
 184     }
 185 }
 186
 187 void relevance_donerecord(struct relevance *r, struct record_cluster *cluster)
 188 {
 189     int i;
 190
 191     for (i = 1; i < r->vec_len; i++)
 192         if (cluster->term_frequency_vec[i] > 0)
 193             r->doc_frequency_vec[i]++;
 194
 195     r->doc_frequency_vec[0]++;
 196 }
 197
 198 // Prepare for a relevance-sorted read
 199 void relevance_prepare_read(struct relevance *rel, struct reclist *reclist)
 200 {
 201     int i;
 202     float *idfvec = xmalloc(rel->vec_len * sizeof(float));
 203
 204     reclist_enter(reclist);
 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         {
 212             // This conditional may be terribly wrong
 213             // It was there to address the situation where vec[0] == vec[i]
 214             // which leads to idfvec[i] == 0... not sure about this
 215             // Traditional TF-IDF may assume that a word that occurs in every
 216             // record is irrelevant, but this is actually something we will
 217             // see a lot
 218             if ((idfvec[i] = log((float) rel->doc_frequency_vec[0] /
 219                             rel->doc_frequency_vec[i])) < 0.0000001)
 220                 idfvec[i] = 1;
 221         }
 222     }
 223     // Calculate relevance for each document
 224     while (1)
 225     {
 226         int t;
 227         int relevance = 0;
 228         struct record_cluster *rec = reclist_read_record(reclist);
 229         if (!rec)
 230             break;
 231         for (t = 1; t < rel->vec_len; t++)
 232         {
 233             float termfreq = (float) rec->term_frequency_vecf[t];
 234             relevance += 100000 * (termfreq * idfvec[t] + 0.0000005);
 235         }
 236         rec->relevance_score = relevance;
 237     }
 238     reclist_leave(reclist);
 239     xfree(idfvec);
 240 }
 241
 242 /*
 243  * Local variables:
 244  * c-basic-offset: 4
 245  * c-file-style: "Stroustrup"
 246  * indent-tabs-mode: nil
 247  * End:
 248  * vim: shiftwidth=4 tabstop=8 expandtab
 249  */
 250