a11c0533b75aa15eccbe9cf38dec30c98e481580
[pazpar2-moved-to-github.git] / src / relevance.c
1 /*
2  * $Id: relevance.c,v 1.7 2007-01-10 10:04:23 adam 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 FLOAT_REL
181 static int comp(const void *p1, const void *p2)
182 {
183     float res;
184     struct record **r1 = (struct record **) p1;
185     struct record **r2 = (struct record **) p2;
186     res = (*r2)->relevance - (*r1)->relevance;
187     if (res > 0)
188         return 1;
189     else if (res < 0)
190         return -1;
191     else
192         return 0;
193 }
194 #else
195 static int comp(const void *p1, const void *p2)
196 {
197     struct record_cluster **r1 = (struct record_cluster **) p1;
198     struct record_cluster **r2 = (struct record_cluster **) p2;
199     return (*r2)->relevance - (*r1)->relevance;
200 }
201 #endif
202
203 // Prepare for a relevance-sorted read of up to num entries
204 void relevance_prepare_read(struct relevance *rel, struct reclist *reclist)
205 {
206     int i;
207     float *idfvec = xmalloc(rel->vec_len * sizeof(float));
208
209     // Calculate document frequency vector for each term.
210     for (i = 1; i < rel->vec_len; i++)
211     {
212         if (!rel->doc_frequency_vec[i])
213             idfvec[i] = 0;
214         else
215             idfvec[i] = log((float) rel->doc_frequency_vec[0] / rel->doc_frequency_vec[i]);
216     }
217     // Calculate relevance for each document
218     for (i = 0; i < reclist->num_records; i++)
219     {
220         int t;
221         struct record_cluster *rec = reclist->flatlist[i];
222         float relevance;
223         relevance = 0;
224         for (t = 1; t < rel->vec_len; t++)
225         {
226             float termfreq;
227             if (!rec->term_frequency_vec[0])
228                 break;
229             termfreq = (float) rec->term_frequency_vec[t] / rec->term_frequency_vec[0];
230             relevance += termfreq * idfvec[t];
231         }
232         rec->relevance = (int) (relevance * 100000);
233     }
234     qsort(reclist->flatlist, reclist->num_records, sizeof(struct record*), comp);
235     reclist->pointer = 0;
236     xfree(idfvec);
237 }
238
239 /*
240  * Local variables:
241  * c-basic-offset: 4
242  * indent-tabs-mode: nil
243  * End:
244  * vim: shiftwidth=4 tabstop=8 expandtab
245  */