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 *term_frequency_vec_tmp;
  35     int vec_len;
  36     struct word_entry *entries;
  37     pp2_charset_token_t prt;
  38     int rank_cluster;
  39     int follow_boost;
  40     int lead_boost;
  41     int length_divide;
  42     NMEM nmem;
  43 };
  44
  45 struct word_entry {
  46     const char *norm_str;
  47     const char *display_str;
  48     int termno;
  49     int follow_boost;
  50     char *ccl_field;
  51     struct word_entry *next;
  52 };
  53
  54 static int word_entry_match(struct relevance *r, const char *norm_str,
  55                             const char *rank, int *mult)
  56 {
  57     int i = 1;
  58     struct word_entry *entries = r->entries;
  59     for (; entries; entries = entries->next, i++)
  60     {
  61         if (*norm_str && !strcmp(norm_str, entries->norm_str))
  62         {
  63             int extra = r->follow_boost;
  64             struct word_entry *e_follow = entries;
  65             const char *cp = 0;
  66             int no_read = 0;
  67             sscanf(rank, "%d%n", mult, &no_read);
  68             rank += no_read;
  69             while (*rank == ' ')
  70                 rank++;
  71             if (no_read > 0 && (cp = strchr(rank, ' ')))
  72             {
  73                 if ((cp - rank) == strlen(entries->ccl_field) &&
  74                     memcmp(entries->ccl_field, rank, cp - rank) == 0)
  75                     *mult = atoi(cp + 1);
  76             }
  77             (*mult) += entries->follow_boost;
  78             while ((e_follow = e_follow->next) != 0 && extra > 0)
  79             {
  80                 e_follow->follow_boost = extra--;
  81             }
  82             return entries->termno;
  83         }
  84         entries->follow_boost = 0;
  85     }
  86     return 0;
  87 }
  88
  89 void relevance_countwords(struct relevance *r, struct record_cluster *cluster,
  90                           const char *words, const char *rank,
  91                           const char *name)
  92 {
  93     int *mult = r->term_frequency_vec_tmp;
  94     const char *norm_str;
  95     int i, length = 0;
  96     int lead_mult = r->lead_boost;
  97     struct word_entry *e;
  98     WRBUF w = cluster->relevance_explain1;
  99
 100     pp2_charset_token_first(r->prt, words, 0);
 101     for (e = r->entries, i = 1; i < r->vec_len; i++, e = e->next)
 102     {
 103         mult[i] = 0;
 104         e->follow_boost = 0;
 105     }
 106
 107     assert(rank);
 108     while ((norm_str = pp2_charset_token_next(r->prt)))
 109     {
 110         int local_mult = 0;
 111         int res = word_entry_match(r, norm_str, rank, &local_mult);
 112         if (res)
 113         {
 114             assert(res < r->vec_len);
 115             mult[res] += local_mult + lead_mult;
 116         }
 117         if (lead_mult > 0)
 118             --lead_mult;
 119         length++;
 120     }
 121
 122     for (e = r->entries, i = 1; i < r->vec_len; i++, e = e->next)
 123     {
 124         if (length == 0 || mult[i] == 0)
 125             continue;
 126         wrbuf_printf(w, "%s: field=%s vecf[%d] += mult(%d)",
 127                      e->display_str, name, i, mult[i]);
 128         switch (r->length_divide)
 129         {
 130         case 0:
 131             wrbuf_printf(w, ";\n");
 132             cluster->term_frequency_vecf[i] += (double) mult[i];
 133             break;
 134         case 1:
 135             wrbuf_printf(w, " / log2(1+length(%d));\n", length);
 136             cluster->term_frequency_vecf[i] +=
 137                 (double) mult[i] / log2(1 + length);
 138             break;
 139         case 2:
 140             wrbuf_printf(w, " / length(%d);\n", length);
 141             cluster->term_frequency_vecf[i] += (double) mult[i] / length;
 142         }
 143         cluster->term_frequency_vec[i] += mult[i];
 144     }
 145
 146     cluster->term_frequency_vec[0] += length;
 147 }
 148
 149 static void pull_terms(struct relevance *res, struct ccl_rpn_node *n)
 150 {
 151     char **words;
 152     int numwords;
 153     char *ccl_field;
 154     int i;
 155
 156     switch (n->kind)
 157     {
 158     case CCL_RPN_AND:
 159     case CCL_RPN_OR:
 160     case CCL_RPN_NOT:
 161     case CCL_RPN_PROX:
 162         pull_terms(res, n->u.p[0]);
 163         pull_terms(res, n->u.p[1]);
 164         break;
 165     case CCL_RPN_TERM:
 166         nmem_strsplit(res->nmem, " ", n->u.t.term, &words, &numwords);
 167         for (i = 0; i < numwords; i++)
 168         {
 169             const char *norm_str;
 170
 171             ccl_field = nmem_strdup_null(res->nmem, n->u.t.qual);
 172
 173             pp2_charset_token_first(res->prt, words[i], 0);
 174             while ((norm_str = pp2_charset_token_next(res->prt)))
 175             {
 176                 struct word_entry **e = &res->entries;
 177                 while (*e)
 178                     e = &(*e)->next;
 179                 *e = nmem_malloc(res->nmem, sizeof(**e));
 180                 (*e)->norm_str = nmem_strdup(res->nmem, norm_str);
 181                 (*e)->ccl_field = ccl_field;
 182                 (*e)->termno = res->vec_len++;
 183                 (*e)->display_str = nmem_strdup(res->nmem, words[i]);
 184                 (*e)->next = 0;
 185             }
 186         }
 187         break;
 188     default:
 189         break;
 190     }
 191 }
 192
 193 struct relevance *relevance_create_ccl(pp2_charset_fact_t pft,
 194                                        struct ccl_rpn_node *query,
 195                                        int rank_cluster,
 196                                        int follow_boost, int lead_boost,
 197                                        int length_divide)
 198 {
 199     NMEM nmem = nmem_create();
 200     struct relevance *res = nmem_malloc(nmem, sizeof(*res));
 201     int i;
 202
 203     res->nmem = nmem;
 204     res->entries = 0;
 205     res->vec_len = 1;
 206     res->rank_cluster = rank_cluster;
 207     res->follow_boost = follow_boost;
 208     res->lead_boost = lead_boost;
 209     res->length_divide = length_divide;
 210     res->prt = pp2_charset_token_create(pft, "relevance");
 211
 212     pull_terms(res, query);
 213
 214     res->doc_frequency_vec = nmem_malloc(nmem, res->vec_len * sizeof(int));
 215     for (i = 0; i < res->vec_len; i++)
 216         res->doc_frequency_vec[i] = 0;
 217
 218     // worker array
 219     res->term_frequency_vec_tmp =
 220         nmem_malloc(res->nmem,
 221                     res->vec_len * sizeof(*res->term_frequency_vec_tmp));
 222     return res;
 223 }
 224
 225 void relevance_destroy(struct relevance **rp)
 226 {
 227     if (*rp)
 228     {
 229         pp2_charset_token_destroy((*rp)->prt);
 230         nmem_destroy((*rp)->nmem);
 231         *rp = 0;
 232     }
 233 }
 234
 235 void relevance_newrec(struct relevance *r, struct record_cluster *rec)
 236 {
 237     if (!rec->term_frequency_vec)
 238     {
 239         int i;
 240
 241         // term frequency [1,..] . [0] is total length of all fields
 242         rec->term_frequency_vec =
 243             nmem_malloc(r->nmem,
 244                         r->vec_len * sizeof(*rec->term_frequency_vec));
 245         for (i = 0; i < r->vec_len; i++)
 246             rec->term_frequency_vec[i] = 0;
 247
 248         // term frequency divided by length of field [1,...]
 249         rec->term_frequency_vecf =
 250             nmem_malloc(r->nmem,
 251                         r->vec_len * sizeof(*rec->term_frequency_vecf));
 252         for (i = 0; i < r->vec_len; i++)
 253             rec->term_frequency_vecf[i] = 0.0;
 254     }
 255 }
 256
 257 void relevance_donerecord(struct relevance *r, struct record_cluster *cluster)
 258 {
 259     int i;
 260
 261     for (i = 1; i < r->vec_len; i++)
 262         if (cluster->term_frequency_vec[i] > 0)
 263             r->doc_frequency_vec[i]++;
 264
 265     r->doc_frequency_vec[0]++;
 266 }
 267
 268 // Prepare for a relevance-sorted read
 269 void relevance_prepare_read(struct relevance *rel, struct reclist *reclist)
 270 {
 271     int i;
 272     float *idfvec = xmalloc(rel->vec_len * sizeof(float));
 273
 274     reclist_enter(reclist);
 275     // Calculate document frequency vector for each term.
 276     for (i = 1; i < rel->vec_len; i++)
 277     {
 278         if (!rel->doc_frequency_vec[i])
 279             idfvec[i] = 0;
 280         else
 281         {
 282             /* add one to nominator idf(t,D) to ensure a value > 0 */
 283             idfvec[i] = log((float) (1 + rel->doc_frequency_vec[0]) /
 284                             rel->doc_frequency_vec[i]);
 285         }
 286     }
 287     // Calculate relevance for each document
 288     while (1)
 289     {
 290         int relevance = 0;
 291         WRBUF w;
 292         struct word_entry *e = rel->entries;
 293         struct record_cluster *rec = reclist_read_record(reclist);
 294         if (!rec)
 295             break;
 296         w = rec->relevance_explain2;
 297         wrbuf_rewind(w);
 298         for (i = 1; i < rel->vec_len; i++)
 299         {
 300             float termfreq = (float) rec->term_frequency_vecf[i];
 301             int add = 100000 * termfreq * idfvec[i];
 302
 303             wrbuf_printf(w, "idf[%d] = log(((1 + total(%d))/termoccur(%d));\n",
 304                          i, rel->doc_frequency_vec[0],
 305                          rel->doc_frequency_vec[i]);
 306             wrbuf_printf(w, "%s: relevance += 100000 * vecf[%d](%f) * "
 307                          "idf[%d](%f) (%d);\n",
 308                          e->display_str, i, termfreq, i, idfvec[i], add);
 309             relevance += add;
 310             e = e->next;
 311         }
 312         if (!rel->rank_cluster)
 313         {
 314             struct record *record;
 315             int cluster_size = 0;
 316
 317             for (record = rec->records; record; record = record->next)
 318                 cluster_size++;
 319
 320             wrbuf_printf(w, "score = relevance(%d)/cluster_size(%d);\n",
 321                          relevance, cluster_size);
 322             relevance /= cluster_size;
 323         }
 324         else
 325         {
 326             wrbuf_printf(w, "score = relevance(%d);\n", relevance);
 327         }
 328         rec->relevance_score = relevance;
 329     }
 330     reclist_leave(reclist);
 331     xfree(idfvec);
 332 }
 333
 334 /*
 335  * Local variables:
 336  * c-basic-offset: 4
 337  * c-file-style: "Stroustrup"
 338  * indent-tabs-mode: nil
 339  * End:
 340  * vim: shiftwidth=4 tabstop=8 expandtab
 341  */
 342