bc841e4e5e18396ee988824eb57343ca545a0205
[pazpar2-moved-to-github.git] / src / relevance.c
1 /*
2  * $Id: relevance.c,v 1.8 2007-01-15 04:34:28 quinn Exp $
3  */
4
5 #include <ctype.h>
6 #include <math.h>
7 #include <stdlib.h>
8
9 #if HAVE_CONFIG_H
10 #include <cconfig.h>
11 #endif
12
13 #include "relevance.h"
14 #include "pazpar2.h"
15
16 struct relevance
17 {
18     int *doc_frequency_vec;
19     int vec_len;
20     struct word_trie *wt;
21     NMEM nmem;
22 };
23
24 // We use this data structure to recognize terms in input records,
25 // and map them to record term vectors for counting.
26 struct word_trie
27 {
28     struct
29     {
30         struct word_trie *child;
31         int termno;
32     } list[26];
33 };
34
35 static struct word_trie *create_word_trie_node(NMEM nmem)
36 {
37     struct word_trie *res = nmem_malloc(nmem, sizeof(struct word_trie));
38     int i;
39     for (i = 0; i < 26; i++)
40     {
41         res->list[i].child = 0;
42         res->list[i].termno = -1;
43     }
44     return res;
45 }
46
47 static void word_trie_addterm(NMEM nmem, struct word_trie *n, const char *term, int num)
48 {
49     while (*term) {
50         int c = tolower(*term);
51         if (c < 'a' || c > 'z')
52             term++;
53         else
54         {
55             c -= 'a';
56             if (!*(++term))
57                 n->list[c].termno = num;
58             else
59             {
60                 if (!n->list[c].child)
61                 {
62                     struct word_trie *new = create_word_trie_node(nmem);
63                     n->list[c].child = new;
64                 }
65                 word_trie_addterm(nmem, n->list[c].child, term, num);
66             }
67             break;
68         }
69     }
70 }
71
72 #define raw_char(c) (((c) >= 'a' && (c) <= 'z') ? (c) - 'a' : -1)
73
74 static int word_trie_match(struct word_trie *t, const char *word, int *skipped)
75 {
76     int c = raw_char(tolower(*word));
77
78     if (!*word)
79         return 0;
80
81     word++;
82     (*skipped)++;
83     if (!*word || raw_char(*word) < 0)
84     {
85         if (t->list[c].termno > 0)
86             return t->list[c].termno;
87         else
88             return 0;
89     }
90     else
91     {
92         if (t->list[c].child)
93         {
94             return word_trie_match(t->list[c].child, word, skipped);
95         }
96         else
97             return 0;
98     }
99
100 }
101
102
103 static struct word_trie *build_word_trie(NMEM nmem, const char **terms)
104 {
105     struct word_trie *res = create_word_trie_node(nmem);
106     const char **p;
107     int i;
108
109     for (i = 1, p = terms; *p; p++, i++)
110         word_trie_addterm(nmem, res, *p, i);
111     return res;
112 }
113
114 struct relevance *relevance_create(NMEM nmem, const char **terms, int numrecs)
115 {
116     struct relevance *res = nmem_malloc(nmem, sizeof(struct relevance));
117     const char **p;
118     int i;
119
120     for (p = terms, i = 0; *p; p++, i++)
121         ;
122     res->vec_len = ++i;
123     res->doc_frequency_vec = nmem_malloc(nmem, res->vec_len * sizeof(int));
124     memset(res->doc_frequency_vec, 0, res->vec_len * sizeof(int));
125     res->nmem = nmem;
126     res->wt = build_word_trie(nmem, terms);
127     return res;
128 }
129
130 void relevance_newrec(struct relevance *r, struct record_cluster *rec)
131 {
132     if (!rec->term_frequency_vec)
133     {
134         rec->term_frequency_vec = nmem_malloc(r->nmem, r->vec_len * sizeof(int));
135         memset(rec->term_frequency_vec, 0, r->vec_len * sizeof(int));
136     }
137 }
138
139
140 // FIXME. The definition of a word is crude here.. should support
141 // some form of localization mechanism?
142 void relevance_countwords(struct relevance *r, struct record_cluster *cluster,
143         const char *words, int multiplier)
144 {
145     while (*words)
146     {
147         char c;
148         int res;
149         int skipped;
150         while (*words && (c = raw_char(tolower(*words))) < 0)
151             words++;
152         if (!*words)
153             return;
154         skipped = 0;
155         if ((res = word_trie_match(r->wt, words, &skipped)))
156         {
157             words += skipped;
158             cluster->term_frequency_vec[res] += multiplier;
159         }
160         else
161         {
162             while (*words && (c = raw_char(tolower(*words))) >= 0)
163                 words++;
164         }
165         cluster->term_frequency_vec[0]++;
166     }
167 }
168
169 void relevance_donerecord(struct relevance *r, struct record_cluster *cluster)
170 {
171     int i;
172
173     for (i = 1; i < r->vec_len; i++)
174         if (cluster->term_frequency_vec[i] > 0)
175             r->doc_frequency_vec[i]++;
176
177     r->doc_frequency_vec[0]++;
178 }
179
180 #ifdef GAGA
181 #ifdef FLOAT_REL
182 static int comp(const void *p1, const void *p2)
183 {
184     float res;
185     struct record **r1 = (struct record **) p1;
186     struct record **r2 = (struct record **) p2;
187     res = (*r2)->relevance - (*r1)->relevance;
188     if (res > 0)
189         return 1;
190     else if (res < 0)
191         return -1;
192     else
193         return 0;
194 }
195 #else
196 static int comp(const void *p1, const void *p2)
197 {
198     struct record_cluster **r1 = (struct record_cluster **) p1;
199     struct record_cluster **r2 = (struct record_cluster **) p2;
200     return (*r2)->relevance - (*r1)->relevance;
201 }
202 #endif
203 #endif
204
205 // Prepare for a relevance-sorted read
206 void relevance_prepare_read(struct relevance *rel, struct reclist *reclist)
207 {
208     int i;
209     float *idfvec = xmalloc(rel->vec_len * sizeof(float));
210
211     // Calculate document frequency vector for each term.
212     for (i = 1; i < rel->vec_len; i++)
213     {
214         if (!rel->doc_frequency_vec[i])
215             idfvec[i] = 0;
216         else
217             idfvec[i] = log((float) rel->doc_frequency_vec[0] / rel->doc_frequency_vec[i]);
218     }
219     // Calculate relevance for each document
220     for (i = 0; i < reclist->num_records; i++)
221     {
222         int t;
223         struct record_cluster *rec = reclist->flatlist[i];
224         float relevance;
225         relevance = 0;
226         for (t = 1; t < rel->vec_len; t++)
227         {
228             float termfreq;
229             if (!rec->term_frequency_vec[0])
230                 break;
231             termfreq = (float) rec->term_frequency_vec[t] / rec->term_frequency_vec[0];
232             relevance += termfreq * idfvec[t];
233         }
234         rec->relevance = (int) (relevance * 100000);
235     }
236 #ifdef GAGA
237     qsort(reclist->flatlist, reclist->num_records, sizeof(struct record*), comp);
238 #endif
239     reclist->pointer = 0;
240     xfree(idfvec);
241 }
242
243 /*
244  * Local variables:
245  * c-basic-offset: 4
246  * indent-tabs-mode: nil
247  * End:
248  * vim: shiftwidth=4 tabstop=8 expandtab
249  */