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