Documentation up to date with available settings (allow and maxrecs not yet implemented).
[pazpar2-moved-to-github.git] / src / relevance.c
1 /* $Id: relevance.c,v 1.9 2007-04-10 08:48:56 adam Exp $
2    Copyright (c) 2006-2007, Index Data.
3
4 This file is part of Pazpar2.
5
6 Pazpar2 is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
9 version.
10
11 Pazpar2 is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with Pazpar2; see the file LICENSE.  If not, write to the
18 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
19 02111-1307, USA.
20  */
21
22 #include <ctype.h>
23 #include <math.h>
24 #include <stdlib.h>
25
26 #if HAVE_CONFIG_H
27 #include <cconfig.h>
28 #endif
29
30 #include "relevance.h"
31 #include "pazpar2.h"
32
33 struct relevance
34 {
35     int *doc_frequency_vec;
36     int vec_len;
37     struct word_trie *wt;
38     NMEM nmem;
39 };
40
41 // We use this data structure to recognize terms in input records,
42 // and map them to record term vectors for counting.
43 struct word_trie
44 {
45     struct
46     {
47         struct word_trie *child;
48         int termno;
49     } list[26];
50 };
51
52 static struct word_trie *create_word_trie_node(NMEM nmem)
53 {
54     struct word_trie *res = nmem_malloc(nmem, sizeof(struct word_trie));
55     int i;
56     for (i = 0; i < 26; i++)
57     {
58         res->list[i].child = 0;
59         res->list[i].termno = -1;
60     }
61     return res;
62 }
63
64 static void word_trie_addterm(NMEM nmem, struct word_trie *n, const char *term, int num)
65 {
66     while (*term) {
67         int c = tolower(*term);
68         if (c < 'a' || c > 'z')
69             term++;
70         else
71         {
72             c -= 'a';
73             if (!*(++term))
74                 n->list[c].termno = num;
75             else
76             {
77                 if (!n->list[c].child)
78                 {
79                     struct word_trie *new = create_word_trie_node(nmem);
80                     n->list[c].child = new;
81                 }
82                 word_trie_addterm(nmem, n->list[c].child, term, num);
83             }
84             break;
85         }
86     }
87 }
88
89 #define raw_char(c) (((c) >= 'a' && (c) <= 'z') ? (c) - 'a' : -1)
90
91 static int word_trie_match(struct word_trie *t, const char *word, int *skipped)
92 {
93     int c = raw_char(tolower(*word));
94
95     if (!*word)
96         return 0;
97
98     word++;
99     (*skipped)++;
100     if (!*word || raw_char(*word) < 0)
101     {
102         if (t->list[c].termno > 0)
103             return t->list[c].termno;
104         else
105             return 0;
106     }
107     else
108     {
109         if (t->list[c].child)
110         {
111             return word_trie_match(t->list[c].child, word, skipped);
112         }
113         else
114             return 0;
115     }
116
117 }
118
119
120 static struct word_trie *build_word_trie(NMEM nmem, const char **terms)
121 {
122     struct word_trie *res = create_word_trie_node(nmem);
123     const char **p;
124     int i;
125
126     for (i = 1, p = terms; *p; p++, i++)
127         word_trie_addterm(nmem, res, *p, i);
128     return res;
129 }
130
131 struct relevance *relevance_create(NMEM nmem, const char **terms, int numrecs)
132 {
133     struct relevance *res = nmem_malloc(nmem, sizeof(struct relevance));
134     const char **p;
135     int i;
136
137     for (p = terms, i = 0; *p; p++, i++)
138         ;
139     res->vec_len = ++i;
140     res->doc_frequency_vec = nmem_malloc(nmem, res->vec_len * sizeof(int));
141     memset(res->doc_frequency_vec, 0, res->vec_len * sizeof(int));
142     res->nmem = nmem;
143     res->wt = build_word_trie(nmem, terms);
144     return res;
145 }
146
147 void relevance_newrec(struct relevance *r, struct record_cluster *rec)
148 {
149     if (!rec->term_frequency_vec)
150     {
151         rec->term_frequency_vec = nmem_malloc(r->nmem, r->vec_len * sizeof(int));
152         memset(rec->term_frequency_vec, 0, r->vec_len * sizeof(int));
153     }
154 }
155
156
157 // FIXME. The definition of a word is crude here.. should support
158 // some form of localization mechanism?
159 void relevance_countwords(struct relevance *r, struct record_cluster *cluster,
160         const char *words, int multiplier)
161 {
162     while (*words)
163     {
164         char c;
165         int res;
166         int skipped;
167         while (*words && (c = raw_char(tolower(*words))) < 0)
168             words++;
169         if (!*words)
170             return;
171         skipped = 0;
172         if ((res = word_trie_match(r->wt, words, &skipped)))
173         {
174             words += skipped;
175             cluster->term_frequency_vec[res] += multiplier;
176         }
177         else
178         {
179             while (*words && (c = raw_char(tolower(*words))) >= 0)
180                 words++;
181         }
182         cluster->term_frequency_vec[0]++;
183     }
184 }
185
186 void relevance_donerecord(struct relevance *r, struct record_cluster *cluster)
187 {
188     int i;
189
190     for (i = 1; i < r->vec_len; i++)
191         if (cluster->term_frequency_vec[i] > 0)
192             r->doc_frequency_vec[i]++;
193
194     r->doc_frequency_vec[0]++;
195 }
196
197 #ifdef GAGA
198 #ifdef FLOAT_REL
199 static int comp(const void *p1, const void *p2)
200 {
201     float res;
202     struct record **r1 = (struct record **) p1;
203     struct record **r2 = (struct record **) p2;
204     res = (*r2)->relevance - (*r1)->relevance;
205     if (res > 0)
206         return 1;
207     else if (res < 0)
208         return -1;
209     else
210         return 0;
211 }
212 #else
213 static int comp(const void *p1, const void *p2)
214 {
215     struct record_cluster **r1 = (struct record_cluster **) p1;
216     struct record_cluster **r2 = (struct record_cluster **) p2;
217     return (*r2)->relevance - (*r1)->relevance;
218 }
219 #endif
220 #endif
221
222 // Prepare for a relevance-sorted read
223 void relevance_prepare_read(struct relevance *rel, struct reclist *reclist)
224 {
225     int i;
226     float *idfvec = xmalloc(rel->vec_len * sizeof(float));
227
228     // Calculate document frequency vector for each term.
229     for (i = 1; i < rel->vec_len; i++)
230     {
231         if (!rel->doc_frequency_vec[i])
232             idfvec[i] = 0;
233         else
234             idfvec[i] = log((float) rel->doc_frequency_vec[0] / rel->doc_frequency_vec[i]);
235     }
236     // Calculate relevance for each document
237     for (i = 0; i < reclist->num_records; i++)
238     {
239         int t;
240         struct record_cluster *rec = reclist->flatlist[i];
241         float relevance;
242         relevance = 0;
243         for (t = 1; t < rel->vec_len; t++)
244         {
245             float termfreq;
246             if (!rec->term_frequency_vec[0])
247                 break;
248             termfreq = (float) rec->term_frequency_vec[t] / rec->term_frequency_vec[0];
249             relevance += termfreq * idfvec[t];
250         }
251         rec->relevance = (int) (relevance * 100000);
252     }
253 #ifdef GAGA
254     qsort(reclist->flatlist, reclist->num_records, sizeof(struct record*), comp);
255 #endif
256     reclist->pointer = 0;
257     xfree(idfvec);
258 }
259
260 /*
261  * Local variables:
262  * c-basic-offset: 4
263  * indent-tabs-mode: nil
264  * End:
265  * vim: shiftwidth=4 tabstop=8 expandtab
266  */