src/relevance.c

   1 /* This file is part of Pazpar2.
   2    Copyright (C) 2006-2013 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 "pazpar2_config.h"
  29 #include "relevance.h"
  30 #include "session.h"
  31 #include "client.h"
  32
  33 #ifdef WIN32
  34 #define log2(x) (log(x)/log(2))
  35 #endif
  36
  37 struct relevance
  38 {
  39     int *doc_frequency_vec;
  40     int *term_frequency_vec_tmp;
  41     int *term_pos;
  42     int vec_len;
  43     struct word_entry *entries;
  44     pp2_charset_token_t prt;
  45     int rank_cluster;
  46     double follow_factor;
  47     double lead_decay;
  48     int length_divide;
  49     NMEM nmem;
  50 };
  51
  52 struct word_entry {
  53     const char *norm_str;
  54     const char *display_str;
  55     int termno;
  56     char *ccl_field;
  57     struct word_entry *next;
  58 };
  59
  60 static struct word_entry *word_entry_match(struct relevance *r,
  61                                            const char *norm_str,
  62                                            const char *rank, int *weight)
  63 {
  64     int i = 1;
  65     struct word_entry *entries = r->entries;
  66     for (; entries; entries = entries->next, i++)
  67     {
  68         if (*norm_str && !strcmp(norm_str, entries->norm_str))
  69         {
  70             const char *cp = 0;
  71             int no_read = 0;
  72             sscanf(rank, "%d%n", weight, &no_read);
  73             rank += no_read;
  74             while (*rank == ' ')
  75                 rank++;
  76             if (no_read > 0 && (cp = strchr(rank, ' ')))
  77             {
  78                 if ((cp - rank) == strlen(entries->ccl_field) &&
  79                     memcmp(entries->ccl_field, rank, cp - rank) == 0)
  80                     *weight = atoi(cp + 1);
  81             }
  82             return entries;
  83         }
  84     }
  85     return 0;
  86 }
  87
  88 int relevance_snippet(struct relevance *r,
  89                       const char *words, const char *name,
  90                       WRBUF w_snippet)
  91 {
  92     int no = 0;
  93     const char *norm_str;
  94     int highlight = 0;
  95
  96     pp2_charset_token_first(r->prt, words, 0);
  97     while ((norm_str = pp2_charset_token_next(r->prt)))
  98     {
  99         size_t org_start, org_len;
 100         struct word_entry *entries = r->entries;
 101         int i;
 102
 103         pp2_get_org(r->prt, &org_start, &org_len);
 104         for (; entries; entries = entries->next, i++)
 105         {
 106             if (*norm_str && !strcmp(norm_str, entries->norm_str))
 107                 break;
 108         }
 109         if (entries)
 110         {
 111             if (!highlight)
 112             {
 113                 highlight = 1;
 114                 wrbuf_puts(w_snippet, "<match>");
 115                 no++;
 116             }
 117         }
 118         else
 119         {
 120             if (highlight)
 121             {
 122                 highlight = 0;
 123                 wrbuf_puts(w_snippet, "</match>");
 124             }
 125         }
 126         wrbuf_xmlputs_n(w_snippet, words + org_start, org_len);
 127     }
 128     if (highlight)
 129         wrbuf_puts(w_snippet, "</match>");
 130     if (no)
 131     {
 132         yaz_log(YLOG_DEBUG, "SNIPPET match: %s", wrbuf_cstr(w_snippet));
 133     }
 134     return no;
 135 }
 136
 137 void relevance_countwords(struct relevance *r, struct record_cluster *cluster,
 138                           const char *words, const char *rank,
 139                           const char *name)
 140 {
 141     int *w = r->term_frequency_vec_tmp;
 142     const char *norm_str;
 143     int i, length = 0;
 144     double lead_decay = r->lead_decay;
 145     struct word_entry *e;
 146     WRBUF wr = cluster->relevance_explain1;
 147     int printed_about_field = 0;
 148
 149     pp2_charset_token_first(r->prt, words, 0);
 150     for (e = r->entries, i = 1; i < r->vec_len; i++, e = e->next)
 151     {
 152         w[i] = 0;
 153         r->term_pos[i] = 0;
 154     }
 155
 156     assert(rank);
 157     while ((norm_str = pp2_charset_token_next(r->prt)))
 158     {
 159         int local_weight = 0;
 160         e = word_entry_match(r, norm_str, rank, &local_weight);
 161         if (e)
 162         {
 163             int res = e->termno;
 164             int j;
 165
 166             if (!printed_about_field)
 167             {
 168                 printed_about_field = 1;
 169                 wrbuf_printf(wr, "field=%s content=", name);
 170                 if (strlen(words) > 50)
 171                 {
 172                     wrbuf_xmlputs_n(wr, words, 49);
 173                     wrbuf_puts(wr, " ...");
 174                 }
 175                 else
 176                     wrbuf_xmlputs(wr, words);
 177                 wrbuf_puts(wr, ";\n");
 178             }
 179             assert(res < r->vec_len);
 180             w[res] += local_weight / (1 + log2(1 + lead_decay * length));
 181             wrbuf_printf(wr, "%s: w[%d] += w(%d) / "
 182                          "(1+log2(1+lead_decay(%f) * length(%d)));\n",
 183                          e->display_str, res, local_weight, lead_decay, length);
 184             j = res - 1;
 185             if (j > 0 && r->term_pos[j])
 186             {
 187                 int d = length + 1 - r->term_pos[j];
 188                 wrbuf_printf(wr, "%s: w[%d] += w[%d](%d) * follow(%f) / "
 189                              "(1+log2(d(%d));\n",
 190                              e->display_str, res, res, w[res],
 191                              r->follow_factor, d);
 192                 w[res] += w[res] * r->follow_factor / (1 + log2(d));
 193             }
 194             for (j = 0; j < r->vec_len; j++)
 195                 r->term_pos[j] = j < res ? 0 : length + 1;
 196         }
 197         length++;
 198     }
 199
 200     for (e = r->entries, i = 1; i < r->vec_len; i++, e = e->next)
 201     {
 202         if (length == 0 || w[i] == 0)
 203             continue;
 204         wrbuf_printf(wr, "%s: tf[%d] += w[%d](%d)", e->display_str, i, i, w[i]);
 205         switch (r->length_divide)
 206         {
 207         case 0:
 208             cluster->term_frequency_vecf[i] += (double) w[i];
 209             break;
 210         case 1:
 211             wrbuf_printf(wr, " / log2(1+length(%d))", length);
 212             cluster->term_frequency_vecf[i] +=
 213                 (double) w[i] / log2(1 + length);
 214             break;
 215         case 2:
 216             wrbuf_printf(wr, " / length(%d)", length);
 217             cluster->term_frequency_vecf[i] += (double) w[i] / length;
 218         }
 219         cluster->term_frequency_vec[i] += w[i];
 220         wrbuf_printf(wr, " (%f);\n", cluster->term_frequency_vecf[i]);
 221     }
 222
 223     cluster->term_frequency_vec[0] += length;
 224 }
 225
 226 static void pull_terms(struct relevance *res, struct ccl_rpn_node *n)
 227 {
 228     char **words;
 229     int numwords;
 230     char *ccl_field;
 231     int i;
 232
 233     switch (n->kind)
 234     {
 235     case CCL_RPN_AND:
 236     case CCL_RPN_OR:
 237     case CCL_RPN_NOT:
 238     case CCL_RPN_PROX:
 239         pull_terms(res, n->u.p[0]);
 240         pull_terms(res, n->u.p[1]);
 241         break;
 242     case CCL_RPN_TERM:
 243         nmem_strsplit(res->nmem, " ", n->u.t.term, &words, &numwords);
 244         for (i = 0; i < numwords; i++)
 245         {
 246             const char *norm_str;
 247
 248             ccl_field = nmem_strdup_null(res->nmem, n->u.t.qual);
 249
 250             pp2_charset_token_first(res->prt, words[i], 0);
 251             while ((norm_str = pp2_charset_token_next(res->prt)))
 252             {
 253                 struct word_entry **e = &res->entries;
 254                 while (*e)
 255                     e = &(*e)->next;
 256                 *e = nmem_malloc(res->nmem, sizeof(**e));
 257                 (*e)->norm_str = nmem_strdup(res->nmem, norm_str);
 258                 (*e)->ccl_field = ccl_field;
 259                 (*e)->termno = res->vec_len++;
 260                 (*e)->display_str = nmem_strdup(res->nmem, words[i]);
 261                 (*e)->next = 0;
 262             }
 263         }
 264         break;
 265     default:
 266         break;
 267     }
 268 }
 269 void relevance_clear(struct relevance *r)
 270 {
 271     if (r)
 272     {
 273         int i;
 274         for (i = 0; i < r->vec_len; i++)
 275             r->doc_frequency_vec[i] = 0;
 276     }
 277 }
 278
 279 struct relevance *relevance_create_ccl(pp2_charset_fact_t pft,
 280                                        struct ccl_rpn_node *query,
 281                                        int rank_cluster,
 282                                        double follow_factor, double lead_decay,
 283                                        int length_divide)
 284 {
 285     NMEM nmem = nmem_create();
 286     struct relevance *res = nmem_malloc(nmem, sizeof(*res));
 287
 288     res->nmem = nmem;
 289     res->entries = 0;
 290     res->vec_len = 1;
 291     res->rank_cluster = rank_cluster;
 292     res->follow_factor = follow_factor;
 293     res->lead_decay = lead_decay;
 294     res->length_divide = length_divide;
 295     res->prt = pp2_charset_token_create(pft, "relevance");
 296
 297     pull_terms(res, query);
 298
 299     res->doc_frequency_vec = nmem_malloc(nmem, res->vec_len * sizeof(int));
 300
 301     // worker array
 302     res->term_frequency_vec_tmp =
 303         nmem_malloc(res->nmem,
 304                     res->vec_len * sizeof(*res->term_frequency_vec_tmp));
 305
 306     res->term_pos =
 307         nmem_malloc(res->nmem, res->vec_len * sizeof(*res->term_pos));
 308
 309     relevance_clear(res);
 310     return res;
 311 }
 312
 313 void relevance_destroy(struct relevance **rp)
 314 {
 315     if (*rp)
 316     {
 317         pp2_charset_token_destroy((*rp)->prt);
 318         nmem_destroy((*rp)->nmem);
 319         *rp = 0;
 320     }
 321 }
 322
 323 void relevance_newrec(struct relevance *r, struct record_cluster *rec)
 324 {
 325     if (!rec->term_frequency_vec)
 326     {
 327         int i;
 328
 329         // term frequency [1,..] . [0] is total length of all fields
 330         rec->term_frequency_vec =
 331             nmem_malloc(r->nmem,
 332                         r->vec_len * sizeof(*rec->term_frequency_vec));
 333         for (i = 0; i < r->vec_len; i++)
 334             rec->term_frequency_vec[i] = 0;
 335
 336         // term frequency divided by length of field [1,...]
 337         rec->term_frequency_vecf =
 338             nmem_malloc(r->nmem,
 339                         r->vec_len * sizeof(*rec->term_frequency_vecf));
 340         for (i = 0; i < r->vec_len; i++)
 341             rec->term_frequency_vecf[i] = 0.0;
 342     }
 343 }
 344
 345 void relevance_donerecord(struct relevance *r, struct record_cluster *cluster)
 346 {
 347     int i;
 348
 349     for (i = 1; i < r->vec_len; i++)
 350         if (cluster->term_frequency_vec[i] > 0)
 351             r->doc_frequency_vec[i]++;
 352
 353     r->doc_frequency_vec[0]++;
 354 }
 355
 356 // Prepare for a relevance-sorted read
 357 void relevance_prepare_read(struct relevance *rel, struct reclist *reclist,
 358                             enum conf_sortkey_type type)
 359 {
 360     int i;
 361     float *idfvec = xmalloc(rel->vec_len * sizeof(float));
 362     int n_clients = clients_count();
 363     struct client * clients[n_clients];
 364     yaz_log(YLOG_LOG,"round-robin: have %d clients", n_clients);
 365     for (i = 0; i < n_clients; i++)
 366         clients[i] = 0;
 367
 368
 369     reclist_enter(reclist);
 370     // Calculate document frequency vector for each term.
 371     for (i = 1; i < rel->vec_len; i++)
 372     {
 373         if (!rel->doc_frequency_vec[i])
 374             idfvec[i] = 0;
 375         else
 376         {
 377             /* add one to nominator idf(t,D) to ensure a value > 0 */
 378             idfvec[i] = log((float) (1 + rel->doc_frequency_vec[0]) /
 379                             rel->doc_frequency_vec[i]);
 380         }
 381     }
 382     // Calculate relevance for each document
 383     while (1)
 384     {
 385         int relevance = 0;
 386         WRBUF w;
 387         struct word_entry *e = rel->entries;
 388         struct record_cluster *rec = reclist_read_record(reclist);
 389         if (!rec)
 390             break;
 391         w = rec->relevance_explain2;
 392         wrbuf_rewind(w);
 393         wrbuf_puts(w, "relevance = 0;\n");
 394         for (i = 1; i < rel->vec_len; i++)
 395         {
 396             float termfreq = (float) rec->term_frequency_vecf[i];
 397             int add = 100000 * termfreq * idfvec[i];
 398
 399             wrbuf_printf(w, "idf[%d] = log(((1 + total(%d))/termoccur(%d));\n",
 400                          i, rel->doc_frequency_vec[0],
 401                          rel->doc_frequency_vec[i]);
 402             wrbuf_printf(w, "%s: relevance += 100000 * tf[%d](%f) * "
 403                          "idf[%d](%f) (%d);\n",
 404                          e->display_str, i, termfreq, i, idfvec[i], add);
 405             relevance += add;
 406             e = e->next;
 407         }
 408         if (!rel->rank_cluster)
 409         {
 410             struct record *record;
 411             int cluster_size = 0;
 412
 413             for (record = rec->records; record; record = record->next)
 414                 cluster_size++;
 415
 416             wrbuf_printf(w, "score = relevance(%d)/cluster_size(%d);\n",
 417                          relevance, cluster_size);
 418             relevance /= cluster_size;
 419         }
 420         else
 421         {
 422             wrbuf_printf(w, "score = relevance(%d);\n", relevance);
 423         }
 424         // Experimental round-robin
 425         // Overwrites the score calculated above, but I keep it there to
 426         // get the log entries
 427         if (type == Metadata_sortkey_relevance_h) {
 428             struct record *record;
 429             int thisclient = 0;
 430             struct record *bestrecord = 0;
 431             int nclust = 0;
 432             for (record = rec->records; record; record = record->next) {
 433                 if ( bestrecord == 0 || bestrecord->position < record->position )
 434                     bestrecord = record;
 435                 nclust++;
 436             }
 437             while ( clients[thisclient] != 0
 438                     && clients[thisclient] != bestrecord->client )
 439                 thisclient++;
 440             if ( clients[thisclient] == 0 )
 441             {
 442                 yaz_log(YLOG_LOG,"round-robin: found new client at %d: p=%p\n", thisclient, bestrecord->client);
 443                 clients[thisclient] = bestrecord->client;
 444             }
 445             int tfrel = relevance;
 446             relevance = -(bestrecord->position * n_clients + thisclient) ;
 447             wrbuf_printf(w,"round-robin score: pos=%d client=%d ncl=%d tfscore=%d score=%d\n",
 448                          bestrecord->position, thisclient, nclust, tfrel, relevance );
 449             yaz_log(YLOG_LOG,"round-robin score: pos=%d client=%d ncl=%d score=%d",
 450                          bestrecord->position, thisclient, nclust, relevance );
 451         }
 452         rec->relevance_score = relevance;
 453     }
 454     reclist_leave(reclist);
 455     xfree(idfvec);
 456 }
 457
 458 /*
 459  * Local variables:
 460  * c-basic-offset: 4
 461  * c-file-style: "Stroustrup"
 462  * indent-tabs-mode: nil
 463  * End:
 464  * vim: shiftwidth=4 tabstop=8 expandtab
 465  */
 466