X-Git-Url: http://git.indexdata.com/?a=blobdiff_plain;f=src%2Frelevance.c;h=a365ebd91a369c6f1e4336c003e784ba47a0f6d4;hb=3af29dd9e6ef67ee79146ef9ace3e3abdb42c9bb;hp=5e1fd76225ff7f9f2bb26990b353840777bf8d9b;hpb=cc29eab9f928f6cd0f4231cb2e554e2ac7b0b1f3;p=pazpar2-moved-to-github.git diff --git a/src/relevance.c b/src/relevance.c index 5e1fd76..a365ebd 100644 --- a/src/relevance.c +++ b/src/relevance.c @@ -1,7 +1,5 @@ -/* $Id: relevance.c,v 1.9 2007-04-10 08:48:56 adam Exp $ - Copyright (c) 2006-2007, Index Data. - -This file is part of Pazpar2. +/* This file is part of Pazpar2. + Copyright (C) 2006-2012 Index Data Pazpar2 is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free @@ -14,172 +12,175 @@ FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License -along with Pazpar2; see the file LICENSE. If not, write to the -Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. - */ +along with this program; if not, write to the Free Software +Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA -#include -#include -#include +*/ #if HAVE_CONFIG_H -#include +#include #endif +#include +#include +#include + #include "relevance.h" -#include "pazpar2.h" +#include "session.h" struct relevance { int *doc_frequency_vec; int vec_len; - struct word_trie *wt; + struct word_entry *entries; + pp2_charset_token_t prt; NMEM nmem; }; -// We use this data structure to recognize terms in input records, -// and map them to record term vectors for counting. -struct word_trie -{ - struct - { - struct word_trie *child; - int termno; - } list[26]; +struct word_entry { + const char *norm_str; + int termno; + char *ccl_field; + struct word_entry *next; }; -static struct word_trie *create_word_trie_node(NMEM nmem) +int word_entry_match(struct word_entry *entries, const char *norm_str) { - struct word_trie *res = nmem_malloc(nmem, sizeof(struct word_trie)); - int i; - for (i = 0; i < 26; i++) + for (; entries; entries = entries->next) { - res->list[i].child = 0; - res->list[i].termno = -1; - } - return res; -} - -static void word_trie_addterm(NMEM nmem, struct word_trie *n, const char *term, int num) -{ - while (*term) { - int c = tolower(*term); - if (c < 'a' || c > 'z') - term++; - else - { - c -= 'a'; - if (!*(++term)) - n->list[c].termno = num; - else - { - if (!n->list[c].child) - { - struct word_trie *new = create_word_trie_node(nmem); - n->list[c].child = new; - } - word_trie_addterm(nmem, n->list[c].child, term, num); - } - break; - } + if (!strcmp(norm_str, entries->norm_str)) + return entries->termno; } + return 0; } -#define raw_char(c) (((c) >= 'a' && (c) <= 'z') ? (c) - 'a' : -1) - -static int word_trie_match(struct word_trie *t, const char *word, int *skipped) +void relevance_countwords(struct relevance *r, struct record_cluster *cluster, + const char *words, int multiplier, const char *name) { - int c = raw_char(tolower(*word)); + int *mult = cluster->term_frequency_vec_tmp; + const char *norm_str; + int i, length = 0; - if (!*word) - return 0; + pp2_charset_token_first(r->prt, words, 0); + for (i = 1; i < r->vec_len; i++) + mult[i] = 0; - word++; - (*skipped)++; - if (!*word || raw_char(*word) < 0) + while ((norm_str = pp2_charset_token_next(r->prt))) { - if (t->list[c].termno > 0) - return t->list[c].termno; - else - return 0; - } - else - { - if (t->list[c].child) + int res = word_entry_match(r->entries, norm_str); + if (res) { - return word_trie_match(t->list[c].child, word, skipped); + assert(res < r->vec_len); + mult[res] += multiplier; } - else - return 0; + length++; } -} + for (i = 1; i < r->vec_len; i++) + { + if (length > 0) /* only add if non-empty */ + cluster->term_frequency_vecf[i] += (double) mult[i] / length; + cluster->term_frequency_vec[i] += mult[i]; + } + cluster->term_frequency_vec[0] += length; +} -static struct word_trie *build_word_trie(NMEM nmem, const char **terms) +static void pull_terms(struct relevance *res, struct ccl_rpn_node *n) { - struct word_trie *res = create_word_trie_node(nmem); - const char **p; + char **words; + int numwords; + char *ccl_field; int i; - for (i = 1, p = terms; *p; p++, i++) - word_trie_addterm(nmem, res, *p, i); - return res; + switch (n->kind) + { + case CCL_RPN_AND: + case CCL_RPN_OR: + case CCL_RPN_NOT: + case CCL_RPN_PROX: + pull_terms(res, n->u.p[0]); + pull_terms(res, n->u.p[1]); + break; + case CCL_RPN_TERM: + nmem_strsplit(res->nmem, " ", n->u.t.term, &words, &numwords); + for (i = 0; i < numwords; i++) + { + const char *norm_str; + + ccl_field = nmem_strdup_null(res->nmem, n->u.t.qual); + + pp2_charset_token_first(res->prt, words[i], 0); + while ((norm_str = pp2_charset_token_next(res->prt))) + { + struct word_entry **e = &res->entries; + while (*e) + e = &(*e)->next; + *e = nmem_malloc(res->nmem, sizeof(**e)); + (*e)->norm_str = nmem_strdup(res->nmem, norm_str); + (*e)->ccl_field = ccl_field; + (*e)->termno = res->vec_len++; + (*e)->next = 0; + } + } + break; + default: + break; + } } -struct relevance *relevance_create(NMEM nmem, const char **terms, int numrecs) +struct relevance *relevance_create_ccl(pp2_charset_fact_t pft, + NMEM nmem, struct ccl_rpn_node *query) { - struct relevance *res = nmem_malloc(nmem, sizeof(struct relevance)); - const char **p; + struct relevance *res = nmem_malloc(nmem, sizeof(*res)); int i; - for (p = terms, i = 0; *p; p++, i++) - ; - res->vec_len = ++i; - res->doc_frequency_vec = nmem_malloc(nmem, res->vec_len * sizeof(int)); - memset(res->doc_frequency_vec, 0, res->vec_len * sizeof(int)); res->nmem = nmem; - res->wt = build_word_trie(nmem, terms); + res->entries = 0; + res->vec_len = 1; + res->prt = pp2_charset_token_create(pft, "relevance"); + + pull_terms(res, query); + + res->doc_frequency_vec = nmem_malloc(nmem, res->vec_len * sizeof(int)); + for (i = 0; i < res->vec_len; i++) + res->doc_frequency_vec[i] = 0; return res; } -void relevance_newrec(struct relevance *r, struct record_cluster *rec) +void relevance_destroy(struct relevance **rp) { - if (!rec->term_frequency_vec) + if (*rp) { - rec->term_frequency_vec = nmem_malloc(r->nmem, r->vec_len * sizeof(int)); - memset(rec->term_frequency_vec, 0, r->vec_len * sizeof(int)); + pp2_charset_token_destroy((*rp)->prt); + *rp = 0; } } - -// FIXME. The definition of a word is crude here.. should support -// some form of localization mechanism? -void relevance_countwords(struct relevance *r, struct record_cluster *cluster, - const char *words, int multiplier) +void relevance_newrec(struct relevance *r, struct record_cluster *rec) { - while (*words) + if (!rec->term_frequency_vec) { - char c; - int res; - int skipped; - while (*words && (c = raw_char(tolower(*words))) < 0) - words++; - if (!*words) - return; - skipped = 0; - if ((res = word_trie_match(r->wt, words, &skipped))) - { - words += skipped; - cluster->term_frequency_vec[res] += multiplier; - } - else - { - while (*words && (c = raw_char(tolower(*words))) >= 0) - words++; - } - cluster->term_frequency_vec[0]++; + int i; + + // term frequency [1,..] . [0] is total length of all fields + rec->term_frequency_vec = + nmem_malloc(r->nmem, + r->vec_len * sizeof(*rec->term_frequency_vec)); + for (i = 0; i < r->vec_len; i++) + rec->term_frequency_vec[i] = 0; + + // term frequency divided by length of field [1,...] + rec->term_frequency_vecf = + nmem_malloc(r->nmem, + r->vec_len * sizeof(*rec->term_frequency_vecf)); + for (i = 0; i < r->vec_len; i++) + rec->term_frequency_vecf[i] = 0.0; + + // for relevance_countwords (so we don't have to xmalloc/xfree) + rec->term_frequency_vec_tmp = + nmem_malloc(r->nmem, + r->vec_len * sizeof(*rec->term_frequency_vec_tmp)); } } @@ -194,73 +195,56 @@ void relevance_donerecord(struct relevance *r, struct record_cluster *cluster) r->doc_frequency_vec[0]++; } -#ifdef GAGA -#ifdef FLOAT_REL -static int comp(const void *p1, const void *p2) -{ - float res; - struct record **r1 = (struct record **) p1; - struct record **r2 = (struct record **) p2; - res = (*r2)->relevance - (*r1)->relevance; - if (res > 0) - return 1; - else if (res < 0) - return -1; - else - return 0; -} -#else -static int comp(const void *p1, const void *p2) -{ - struct record_cluster **r1 = (struct record_cluster **) p1; - struct record_cluster **r2 = (struct record_cluster **) p2; - return (*r2)->relevance - (*r1)->relevance; -} -#endif -#endif - // Prepare for a relevance-sorted read void relevance_prepare_read(struct relevance *rel, struct reclist *reclist) { int i; float *idfvec = xmalloc(rel->vec_len * sizeof(float)); + reclist_enter(reclist); // Calculate document frequency vector for each term. for (i = 1; i < rel->vec_len; i++) { if (!rel->doc_frequency_vec[i]) idfvec[i] = 0; else - idfvec[i] = log((float) rel->doc_frequency_vec[0] / rel->doc_frequency_vec[i]); + { + // This conditional may be terribly wrong + // It was there to address the situation where vec[0] == vec[i] + // which leads to idfvec[i] == 0... not sure about this + // Traditional TF-IDF may assume that a word that occurs in every + // record is irrelevant, but this is actually something we will + // see a lot + if ((idfvec[i] = log((float) rel->doc_frequency_vec[0] / + rel->doc_frequency_vec[i])) < 0.0000001) + idfvec[i] = 1; + } } // Calculate relevance for each document - for (i = 0; i < reclist->num_records; i++) + while (1) { int t; - struct record_cluster *rec = reclist->flatlist[i]; - float relevance; - relevance = 0; + int relevance = 0; + struct record_cluster *rec = reclist_read_record(reclist); + if (!rec) + break; for (t = 1; t < rel->vec_len; t++) { - float termfreq; - if (!rec->term_frequency_vec[0]) - break; - termfreq = (float) rec->term_frequency_vec[t] / rec->term_frequency_vec[0]; - relevance += termfreq * idfvec[t]; + float termfreq = (float) rec->term_frequency_vecf[t]; + relevance += 100000 * (termfreq * idfvec[t] + 0.0000005); } - rec->relevance = (int) (relevance * 100000); + rec->relevance_score = relevance; } -#ifdef GAGA - qsort(reclist->flatlist, reclist->num_records, sizeof(struct record*), comp); -#endif - reclist->pointer = 0; + reclist_leave(reclist); xfree(idfvec); } /* * Local variables: * c-basic-offset: 4 + * c-file-style: "Stroustrup" * indent-tabs-mode: nil * End: * vim: shiftwidth=4 tabstop=8 expandtab */ +