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                                        struct ccl_rpn_node *query)
 134 {
 135     NMEM nmem = nmem_create();
 136     struct relevance *res = nmem_malloc(nmem, sizeof(*res));
 137     int i;
 138
 139     res->nmem = nmem;
 140     res->entries = 0;
 141     res->vec_len = 1;
 142     res->prt = pp2_charset_token_create(pft, "relevance");
 143
 144     pull_terms(res, query);
 145
 146     res->doc_frequency_vec = nmem_malloc(nmem, res->vec_len * sizeof(int));
 147     for (i = 0; i < res->vec_len; i++)
 148         res->doc_frequency_vec[i] = 0;
 149     return res;
 150 }
 151
 152 void relevance_destroy(struct relevance **rp)
 153 {
 154     if (*rp)
 155     {
 156         pp2_charset_token_destroy((*rp)->prt);
 157         nmem_destroy((*rp)->nmem);
 158         *rp = 0;
 159     }
 160 }
 161
 162 void relevance_newrec(struct relevance *r, struct record_cluster *rec)
 163 {
 164     if (!rec->term_frequency_vec)
 165     {
 166         int i;
 167
 168         // term frequency [1,..] . [0] is total length of all fields
 169         rec->term_frequency_vec =
 170             nmem_malloc(r->nmem,
 171                         r->vec_len * sizeof(*rec->term_frequency_vec));
 172         for (i = 0; i < r->vec_len; i++)
 173             rec->term_frequency_vec[i] = 0;
 174
 175         // term frequency divided by length of field [1,...]
 176         rec->term_frequency_vecf =
 177             nmem_malloc(r->nmem,
 178                         r->vec_len * sizeof(*rec->term_frequency_vecf));
 179         for (i = 0; i < r->vec_len; i++)
 180             rec->term_frequency_vecf[i] = 0.0;
 181
 182         // for relevance_countwords (so we don't have to xmalloc/xfree)
 183         rec->term_frequency_vec_tmp =
 184             nmem_malloc(r->nmem,
 185                         r->vec_len * sizeof(*rec->term_frequency_vec_tmp));
 186     }
 187 }
 188
 189 void relevance_donerecord(struct relevance *r, struct record_cluster *cluster)
 190 {
 191     int i;
 192
 193     for (i = 1; i < r->vec_len; i++)
 194         if (cluster->term_frequency_vec[i] > 0)
 195             r->doc_frequency_vec[i]++;
 196
 197     r->doc_frequency_vec[0]++;
 198 }
 199
 200 // Prepare for a relevance-sorted read
 201 void relevance_prepare_read(struct relevance *rel, struct reclist *reclist)
 202 {
 203     int i;
 204     float *idfvec = xmalloc(rel->vec_len * sizeof(float));
 205
 206     reclist_enter(reclist);
 207     // Calculate document frequency vector for each term.
 208     for (i = 1; i < rel->vec_len; i++)
 209     {
 210         if (!rel->doc_frequency_vec[i])
 211             idfvec[i] = 0;
 212         else
 213         {
 214             // This conditional may be terribly wrong
 215             // It was there to address the situation where vec[0] == vec[i]
 216             // which leads to idfvec[i] == 0... not sure about this
 217             // Traditional TF-IDF may assume that a word that occurs in every
 218             // record is irrelevant, but this is actually something we will
 219             // see a lot
 220             if ((idfvec[i] = log((float) rel->doc_frequency_vec[0] /
 221                             rel->doc_frequency_vec[i])) < 0.0000001)
 222                 idfvec[i] = 1;
 223         }
 224     }
 225     // Calculate relevance for each document
 226     while (1)
 227     {
 228         int t;
 229         int relevance = 0;
 230         struct record_cluster *rec = reclist_read_record(reclist);
 231         if (!rec)
 232             break;
 233         for (t = 1; t < rel->vec_len; t++)
 234         {
 235             float termfreq = (float) rec->term_frequency_vecf[t];
 236             relevance += 100000 * (termfreq * idfvec[t] + 0.0000005);
 237         }
 238         rec->relevance_score = relevance;
 239     }
 240     reclist_leave(reclist);
 241     xfree(idfvec);
 242 }
 243
 244 /*
 245  * Local variables:
 246  * c-basic-offset: 4
 247  * c-file-style: "Stroustrup"
 248  * indent-tabs-mode: nil
 249  * End:
 250  * vim: shiftwidth=4 tabstop=8 expandtab
 251  */
 252