1 /* $Id: relevance.c,v 1.13 2007-05-10 11:46:09 adam Exp $
2 Copyright (c) 2006-2007, Index Data.
4 This file is part of Pazpar2.
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
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
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
30 #include "relevance.h"
37 int *doc_frequency_vec;
42 struct word_entry *entries;
49 #define raw_char(c) (((c) >= 'a' && (c) <= 'z') ? (c) - 'a' : -1)
52 // We use this data structure to recognize terms in input records,
53 // and map them to record term vectors for counting.
58 struct word_trie *child;
63 static struct word_trie *create_word_trie_node(NMEM nmem)
65 struct word_trie *res = nmem_malloc(nmem, sizeof(struct word_trie));
67 for (i = 0; i < 26; i++)
69 res->list[i].child = 0;
70 res->list[i].termno = -1;
75 static void word_trie_addterm(NMEM nmem, struct word_trie *n, const char *term, int num)
79 int c = tolower(*term);
80 if (c < 'a' || c > 'z')
86 n->list[c].termno = num;
89 if (!n->list[c].child)
91 struct word_trie *new = create_word_trie_node(nmem);
92 n->list[c].child = new;
94 word_trie_addterm(nmem, n->list[c].child, term, num);
101 static int word_trie_match(struct word_trie *t, const char *word, int *skipped)
103 int c = raw_char(tolower(*word));
110 if (!*word || raw_char(*word) < 0)
112 if (t->list[c].termno > 0)
113 return t->list[c].termno;
119 if (t->list[c].child)
121 return word_trie_match(t->list[c].child, word, skipped);
130 static struct word_trie *build_word_trie(NMEM nmem, const char **terms)
132 struct word_trie *res = create_word_trie_node(nmem);
136 for (i = 1, p = terms; *p; p++, i++)
137 word_trie_addterm(nmem, res, *p, i);
142 // FIXME. The definition of a word is crude here.. should support
143 // some form of localization mechanism?
144 void relevance_countwords(struct relevance *r, struct record_cluster *cluster,
145 const char *words, int multiplier)
152 while (*words && (c = raw_char(tolower(*words))) < 0)
156 res = word_trie_match(r->wt, words, &skipped);
160 cluster->term_frequency_vec[res] += multiplier;
164 while (*words && (c = raw_char(tolower(*words))) >= 0)
167 cluster->term_frequency_vec[0]++;
174 const char *norm_str;
176 struct word_entry *next;
179 static void add_word_entry(NMEM nmem,
180 struct word_entry **entries,
181 const char *norm_str,
184 struct word_entry *ne = nmem_malloc(nmem, sizeof(*ne));
185 ne->norm_str = nmem_strdup(nmem, norm_str);
186 ne->termno = term_no;
193 int word_entry_match(struct word_entry *entries, const char *norm_str)
195 for (; entries; entries = entries->next)
197 if (!strcmp(norm_str, entries->norm_str))
198 return entries->termno;
203 static struct word_entry *build_word_entries(pp2_charset_t pct, NMEM nmem,
206 int termno = 1; /* >0 signals THERE is an entry */
207 struct word_entry *entries = 0;
208 const char **p = terms;
212 pp2_relevance_token_t prt = pp2_relevance_tokenize(pct, *p);
213 const char *norm_str;
215 while ((norm_str = pp2_relevance_token_next(prt)))
216 add_word_entry(nmem, &entries, norm_str, termno);
218 pp2_relevance_token_destroy(prt);
225 void relevance_countwords(struct relevance *r, struct record_cluster *cluster,
226 const char *words, int multiplier)
228 pp2_relevance_token_t prt = pp2_relevance_tokenize(r->pct, words);
230 const char *norm_str;
232 while ((norm_str = pp2_relevance_token_next(prt)))
234 int res = word_entry_match(r->entries, norm_str);
236 cluster->term_frequency_vec[res] += multiplier;
237 cluster->term_frequency_vec[0]++;
239 pp2_relevance_token_destroy(prt);
246 struct relevance *relevance_create(pp2_charset_t pct,
247 NMEM nmem, const char **terms, int numrecs)
249 struct relevance *res = nmem_malloc(nmem, sizeof(struct relevance));
253 for (p = terms, i = 0; *p; p++, i++)
256 res->doc_frequency_vec = nmem_malloc(nmem, res->vec_len * sizeof(int));
257 memset(res->doc_frequency_vec, 0, res->vec_len * sizeof(int));
260 res->wt = build_word_trie(nmem, terms);
262 res->entries = build_word_entries(pct, nmem, terms);
268 void relevance_newrec(struct relevance *r, struct record_cluster *rec)
270 if (!rec->term_frequency_vec)
272 rec->term_frequency_vec = nmem_malloc(r->nmem, r->vec_len * sizeof(int));
273 memset(rec->term_frequency_vec, 0, r->vec_len * sizeof(int));
278 void relevance_donerecord(struct relevance *r, struct record_cluster *cluster)
282 for (i = 1; i < r->vec_len; i++)
283 if (cluster->term_frequency_vec[i] > 0)
284 r->doc_frequency_vec[i]++;
286 r->doc_frequency_vec[0]++;
291 static int comp(const void *p1, const void *p2)
294 struct record **r1 = (struct record **) p1;
295 struct record **r2 = (struct record **) p2;
296 res = (*r2)->relevance - (*r1)->relevance;
305 static int comp(const void *p1, const void *p2)
307 struct record_cluster **r1 = (struct record_cluster **) p1;
308 struct record_cluster **r2 = (struct record_cluster **) p2;
309 return (*r2)->relevance - (*r1)->relevance;
314 // Prepare for a relevance-sorted read
315 void relevance_prepare_read(struct relevance *rel, struct reclist *reclist)
318 float *idfvec = xmalloc(rel->vec_len * sizeof(float));
320 // Calculate document frequency vector for each term.
321 for (i = 1; i < rel->vec_len; i++)
323 if (!rel->doc_frequency_vec[i])
327 // This conditional may be terribly wrong
328 // It was there to address the situation where vec[0] == vec[i]
329 // which leads to idfvec[i] == 0... not sure about this
330 // Traditional TF-IDF may assume that a word that occurs in every
331 // record is irrelevant, but this is actually something we will
333 if ((idfvec[i] = log((float) rel->doc_frequency_vec[0] /
334 rel->doc_frequency_vec[i])) < 0.0000001)
338 // Calculate relevance for each document
339 for (i = 0; i < reclist->num_records; i++)
342 struct record_cluster *rec = reclist->flatlist[i];
345 for (t = 1; t < rel->vec_len; t++)
348 if (!rec->term_frequency_vec[0])
350 termfreq = (float) rec->term_frequency_vec[t] / rec->term_frequency_vec[0];
351 relevance += termfreq * idfvec[t];
353 rec->relevance = (int) (relevance * 100000);
356 qsort(reclist->flatlist, reclist->num_records, sizeof(struct record*), comp);
358 reclist->pointer = 0;
365 * indent-tabs-mode: nil
367 * vim: shiftwidth=4 tabstop=8 expandtab