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 static int word_entry_match(struct word_entry *entries, const char *norm_str,
  48                             const char *rank, int *mult)
  49 {
  50     for (; entries; entries = entries->next)
  51     {
  52         if (!strcmp(norm_str, entries->norm_str))
  53         {
  54             const char *cp = 0;
  55             int no_read = 0;
  56             sscanf(rank, "%d%n", mult, &no_read);
  57             rank += no_read;
  58             while (*rank == ' ')
  59                 rank++;
  60             if (no_read > 0 && (cp = strchr(rank, ' ')))
  61             {
  62                 if ((cp - rank) == strlen(entries->ccl_field) &&
  63                     memcmp(entries->ccl_field, rank, cp - rank) == 0)
  64                     *mult = atoi(cp + 1);
  65             }
  66             return entries->termno;
  67         }
  68     }
  69     return 0;
  70 }
  71
  72 void relevance_countwords(struct relevance *r, struct record_cluster *cluster,
  73                           const char *words, const char *rank,
  74                           const char *name)
  75 {
  76     int *mult = cluster->term_frequency_vec_tmp;
  77     const char *norm_str;
  78     int i, length = 0;
  79     pp2_charset_token_first(r->prt, words, 0);
  80     for (i = 1; i < r->vec_len; i++)
  81         mult[i] = 0;
  82
  83     assert(rank);
  84     while ((norm_str = pp2_charset_token_next(r->prt)))
  85     {
  86         int local_mult = 0;
  87         int res = word_entry_match(r->entries, norm_str, rank, &local_mult);
  88         if (res)
  89         {
  90             assert(res < r->vec_len);
  91             mult[res] += local_mult;
  92         }
  93         length++;
  94     }
  95
  96     for (i = 1; i < r->vec_len; i++)
  97     {
  98         if (length > 0) /* only add if non-empty */
  99             cluster->term_frequency_vecf[i] += (double) mult[i] / length;
 100         cluster->term_frequency_vec[i] += mult[i];
 101     }
 102
 103     cluster->term_frequency_vec[0] += length;
 104 }
 105
 106 static void pull_terms(struct relevance *res, struct ccl_rpn_node *n)
 107 {
 108     char **words;
 109     int numwords;
 110     char *ccl_field;
 111     int i;
 112
 113     switch (n->kind)
 114     {
 115     case CCL_RPN_AND:
 116     case CCL_RPN_OR:
 117     case CCL_RPN_NOT:
 118     case CCL_RPN_PROX:
 119         pull_terms(res, n->u.p[0]);
 120         pull_terms(res, n->u.p[1]);
 121         break;
 122     case CCL_RPN_TERM:
 123         nmem_strsplit(res->nmem, " ", n->u.t.term, &words, &numwords);
 124         for (i = 0; i < numwords; i++)
 125         {
 126             const char *norm_str;
 127
 128             ccl_field = nmem_strdup_null(res->nmem, n->u.t.qual);
 129
 130             pp2_charset_token_first(res->prt, words[i], 0);
 131             while ((norm_str = pp2_charset_token_next(res->prt)))
 132             {
 133                 struct word_entry **e = &res->entries;
 134                 while (*e)
 135                     e = &(*e)->next;
 136                 *e = nmem_malloc(res->nmem, sizeof(**e));
 137                 (*e)->norm_str = nmem_strdup(res->nmem, norm_str);
 138                 (*e)->ccl_field = ccl_field;
 139                 (*e)->termno = res->vec_len++;
 140                 (*e)->next = 0;
 141             }
 142         }
 143         break;
 144     default:
 145         break;
 146     }
 147 }
 148
 149 struct relevance *relevance_create_ccl(pp2_charset_fact_t pft,
 150                                        struct ccl_rpn_node *query)
 151 {
 152     NMEM nmem = nmem_create();
 153     struct relevance *res = nmem_malloc(nmem, sizeof(*res));
 154     int i;
 155
 156     res->nmem = nmem;
 157     res->entries = 0;
 158     res->vec_len = 1;
 159     res->prt = pp2_charset_token_create(pft, "relevance");
 160
 161     pull_terms(res, query);
 162
 163     res->doc_frequency_vec = nmem_malloc(nmem, res->vec_len * sizeof(int));
 164     for (i = 0; i < res->vec_len; i++)
 165         res->doc_frequency_vec[i] = 0;
 166     return res;
 167 }
 168
 169 void relevance_destroy(struct relevance **rp)
 170 {
 171     if (*rp)
 172     {
 173         pp2_charset_token_destroy((*rp)->prt);
 174         nmem_destroy((*rp)->nmem);
 175         *rp = 0;
 176     }
 177 }
 178
 179 void relevance_newrec(struct relevance *r, struct record_cluster *rec)
 180 {
 181     if (!rec->term_frequency_vec)
 182     {
 183         int i;
 184
 185         // term frequency [1,..] . [0] is total length of all fields
 186         rec->term_frequency_vec =
 187             nmem_malloc(r->nmem,
 188                         r->vec_len * sizeof(*rec->term_frequency_vec));
 189         for (i = 0; i < r->vec_len; i++)
 190             rec->term_frequency_vec[i] = 0;
 191
 192         // term frequency divided by length of field [1,...]
 193         rec->term_frequency_vecf =
 194             nmem_malloc(r->nmem,
 195                         r->vec_len * sizeof(*rec->term_frequency_vecf));
 196         for (i = 0; i < r->vec_len; i++)
 197             rec->term_frequency_vecf[i] = 0.0;
 198
 199         // for relevance_countwords (so we don't have to xmalloc/xfree)
 200         rec->term_frequency_vec_tmp =
 201             nmem_malloc(r->nmem,
 202                         r->vec_len * sizeof(*rec->term_frequency_vec_tmp));
 203     }
 204 }
 205
 206 void relevance_donerecord(struct relevance *r, struct record_cluster *cluster)
 207 {
 208     int i;
 209
 210     for (i = 1; i < r->vec_len; i++)
 211         if (cluster->term_frequency_vec[i] > 0)
 212             r->doc_frequency_vec[i]++;
 213
 214     r->doc_frequency_vec[0]++;
 215 }
 216
 217 // Prepare for a relevance-sorted read
 218 void relevance_prepare_read(struct relevance *rel, struct reclist *reclist)
 219 {
 220     int i;
 221     float *idfvec = xmalloc(rel->vec_len * sizeof(float));
 222
 223     reclist_enter(reclist);
 224     // Calculate document frequency vector for each term.
 225     for (i = 1; i < rel->vec_len; i++)
 226     {
 227         if (!rel->doc_frequency_vec[i])
 228             idfvec[i] = 0;
 229         else
 230         {
 231             // This conditional may be terribly wrong
 232             // It was there to address the situation where vec[0] == vec[i]
 233             // which leads to idfvec[i] == 0... not sure about this
 234             // Traditional TF-IDF may assume that a word that occurs in every
 235             // record is irrelevant, but this is actually something we will
 236             // see a lot
 237             if ((idfvec[i] = log((float) rel->doc_frequency_vec[0] /
 238                             rel->doc_frequency_vec[i])) < 0.0000001)
 239                 idfvec[i] = 1;
 240         }
 241     }
 242     // Calculate relevance for each document
 243     while (1)
 244     {
 245         int t;
 246         int relevance = 0;
 247         struct record_cluster *rec = reclist_read_record(reclist);
 248         if (!rec)
 249             break;
 250         for (t = 1; t < rel->vec_len; t++)
 251         {
 252             float termfreq = (float) rec->term_frequency_vecf[t];
 253             relevance += 100000 * (termfreq * idfvec[t] + 0.0000005);
 254         }
 255         rec->relevance_score = relevance;
 256     }
 257     reclist_leave(reclist);
 258     xfree(idfvec);
 259 }
 260
 261 /*
 262  * Local variables:
 263  * c-basic-offset: 4
 264  * c-file-style: "Stroustrup"
 265  * indent-tabs-mode: nil
 266  * End:
 267  * vim: shiftwidth=4 tabstop=8 expandtab
 268  */
 269