1 /* $Id: relevance.c,v 1.11 2007-05-01 05:04:53 quinn 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"
35 int *doc_frequency_vec;
41 // We use this data structure to recognize terms in input records,
42 // and map them to record term vectors for counting.
47 struct word_trie *child;
52 static struct word_trie *create_word_trie_node(NMEM nmem)
54 struct word_trie *res = nmem_malloc(nmem, sizeof(struct word_trie));
56 for (i = 0; i < 26; i++)
58 res->list[i].child = 0;
59 res->list[i].termno = -1;
64 static void word_trie_addterm(NMEM nmem, struct word_trie *n, const char *term, int num)
68 int c = tolower(*term);
69 if (c < 'a' || c > 'z')
75 n->list[c].termno = num;
78 if (!n->list[c].child)
80 struct word_trie *new = create_word_trie_node(nmem);
81 n->list[c].child = new;
83 word_trie_addterm(nmem, n->list[c].child, term, num);
90 #define raw_char(c) (((c) >= 'a' && (c) <= 'z') ? (c) - 'a' : -1)
92 static int word_trie_match(struct word_trie *t, const char *word, int *skipped)
94 int c = raw_char(tolower(*word));
101 if (!*word || raw_char(*word) < 0)
103 if (t->list[c].termno > 0)
104 return t->list[c].termno;
110 if (t->list[c].child)
112 return word_trie_match(t->list[c].child, word, skipped);
121 static struct word_trie *build_word_trie(NMEM nmem, const char **terms)
123 struct word_trie *res = create_word_trie_node(nmem);
127 for (i = 1, p = terms; *p; p++, i++)
128 word_trie_addterm(nmem, res, *p, i);
132 struct relevance *relevance_create(NMEM nmem, const char **terms, int numrecs)
134 struct relevance *res = nmem_malloc(nmem, sizeof(struct relevance));
138 for (p = terms, i = 0; *p; p++, i++)
141 res->doc_frequency_vec = nmem_malloc(nmem, res->vec_len * sizeof(int));
142 memset(res->doc_frequency_vec, 0, res->vec_len * sizeof(int));
144 res->wt = build_word_trie(nmem, terms);
148 void relevance_newrec(struct relevance *r, struct record_cluster *rec)
150 if (!rec->term_frequency_vec)
152 rec->term_frequency_vec = nmem_malloc(r->nmem, r->vec_len * sizeof(int));
153 memset(rec->term_frequency_vec, 0, r->vec_len * sizeof(int));
158 // FIXME. The definition of a word is crude here.. should support
159 // some form of localization mechanism?
160 void relevance_countwords(struct relevance *r, struct record_cluster *cluster,
161 const char *words, int multiplier)
168 while (*words && (c = raw_char(tolower(*words))) < 0)
173 if ((res = word_trie_match(r->wt, words, &skipped)))
176 cluster->term_frequency_vec[res] += multiplier;
180 while (*words && (c = raw_char(tolower(*words))) >= 0)
183 cluster->term_frequency_vec[0]++;
187 void relevance_donerecord(struct relevance *r, struct record_cluster *cluster)
191 for (i = 1; i < r->vec_len; i++)
192 if (cluster->term_frequency_vec[i] > 0)
193 r->doc_frequency_vec[i]++;
195 r->doc_frequency_vec[0]++;
200 static int comp(const void *p1, const void *p2)
203 struct record **r1 = (struct record **) p1;
204 struct record **r2 = (struct record **) p2;
205 res = (*r2)->relevance - (*r1)->relevance;
214 static int comp(const void *p1, const void *p2)
216 struct record_cluster **r1 = (struct record_cluster **) p1;
217 struct record_cluster **r2 = (struct record_cluster **) p2;
218 return (*r2)->relevance - (*r1)->relevance;
223 // Prepare for a relevance-sorted read
224 void relevance_prepare_read(struct relevance *rel, struct reclist *reclist)
227 float *idfvec = xmalloc(rel->vec_len * sizeof(float));
229 // Calculate document frequency vector for each term.
230 for (i = 1; i < rel->vec_len; i++)
232 if (!rel->doc_frequency_vec[i])
236 // This conditional may be terribly wrong
237 // It was there to address the situation where vec[0] == vec[i]
238 // which leads to idfvec[i] == 0... not sure about this
239 // Traditional TF-IDF may assume that a word that occurs in every
240 // record is irrelevant, but this is actually something we will
242 if ((idfvec[i] = log((float) rel->doc_frequency_vec[0] /
243 rel->doc_frequency_vec[i])) < 0.0000001)
247 // Calculate relevance for each document
248 for (i = 0; i < reclist->num_records; i++)
251 struct record_cluster *rec = reclist->flatlist[i];
254 for (t = 1; t < rel->vec_len; t++)
257 if (!rec->term_frequency_vec[0])
259 termfreq = (float) rec->term_frequency_vec[t] / rec->term_frequency_vec[0];
260 relevance += termfreq * idfvec[t];
262 rec->relevance = (int) (relevance * 100000);
265 qsort(reclist->flatlist, reclist->num_records, sizeof(struct record*), comp);
267 reclist->pointer = 0;
274 * indent-tabs-mode: nil
276 * vim: shiftwidth=4 tabstop=8 expandtab