1 /* $Id: zvrank.c,v 1.3 2003-03-26 16:41:48 adam Exp $
2 Copyright (C) 1995,1996,1997,1998,1999,2000,2001,2002,2003
5 This file is part of the Zebra server.
7 Zebra is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
12 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with Zebra; see the file LICENSE.zebra. If not, write to the
19 Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
24 /* Zebra Vector Space Model RANKing */
26 ** six (seven) letter identifier for weighting schema
27 ** best document weighting:
28 ** tfc nfc (tpc npc) [original naming]
29 ** ntc atc npc apc [SMART naming, used here]
30 ** best query weighting:
31 ** nfx tfx bfx (npx tpx bpx) [original naming]
32 ** atn ntn btn apn npn bpn [SMART naming]
35 #include <math.h> /* for log */
47 double blog2(double x) { /* sometimes log_e or log_10 is used */
55 struct rs_info { /* for result set */
56 int db_docs; /* number of documents in database (collection) */
57 int db_terms; /* number of distinct terms in database */
58 int db_f_max; /* maximum of f_t in database */
59 char *db_f_max_str; /* string (most frequent term) */
61 char rschema[8]; /* name of ranking schema */
64 void (*d_tf_fct)(void *, void *); /* doc term frequency function */
65 void (*d_idf_fct)(void *, void *); /* doc idf function */
66 void (*d_norm_fct)(void *, void *); /* doc normalization function */
68 void (*q_tf_fct)(void *, void *); /* query term frequency function */
69 void (*q_idf_fct)(void *, void *); /* query idf function */
70 void (*q_norm_fct)(void *, void *); /* query normalization function */
72 double (*sim_fct)(void *, void *); /* similarity function (scoring function) */
76 typedef struct rs_info *RS;
79 yaz_log(LOG_DEBUG, "* RS:\n");
80 yaz_log(LOG_DEBUG, " db_docs: %d\n", rs->db_docs);
81 yaz_log(LOG_DEBUG, " db_terms: %d\n", rs->db_terms);
82 yaz_log(LOG_DEBUG, " f_max: %d\n", rs->db_f_max);
83 yaz_log(LOG_DEBUG, " f_max_str: %s\n", rs->db_f_max_str);
84 yaz_log(LOG_DEBUG, " veclen: %d\n", rs->veclen);
85 /* rschema implies functions */
86 yaz_log(LOG_DEBUG, " rschema: %s\n", rs->rschema);
90 struct ds_info { /* document info */
91 char *docid; /* unique doc identifier */
92 int docno; /* doc number */
93 int doclen; /* document length */
94 int d_f_max; /* maximum number of any term in doc */
95 char *d_f_max_str; /* most frequent term in d */
96 int veclen; /* vector length */
97 struct ts_info *terms;
98 double docsim; /* similarity in [0, ..., 1] (= score/1000) */
100 typedef struct ds_info* DS;
103 yaz_log(LOG_DEBUG, " * DS:\n");
104 yaz_log(LOG_DEBUG, " docid: %s\n", ds->docid);
105 yaz_log(LOG_DEBUG, " docno: %d\n", ds->docno);
106 yaz_log(LOG_DEBUG, " doclen: %d\n", ds->doclen);
107 yaz_log(LOG_DEBUG, " d_f_max: %d\n", ds->d_f_max);
108 yaz_log(LOG_DEBUG, " d_f_max_str:%s\n", ds->d_f_max_str);
109 yaz_log(LOG_DEBUG, " veclen: %d\n", ds->veclen);
113 struct ts_info { /* term info */
123 typedef struct ts_info *TS;
126 yaz_log(LOG_DEBUG, " * TERM:%s gocc:%d locc:%d tf:%f idf:%f wt:%f\n",
127 ts->name, ts->gocc, ts->locc, ts->tf, ts->idf, ts->wt);
136 ** weighting functions
139 /* calculate new term frequency vector */
140 void tf_none(void *rsi, void *dsi) {
147 for (i=0; i < veclen; i++) {
148 freq=ds->terms[i].locc;
149 ds->terms[i].tf=freq;
154 void tf_binary(void *rsi, void *dsi) {
161 for (i=0; i < veclen; i++) {
162 freq=ds->terms[i].locc;
171 void tf_max_norm(void *rsi, void *dsi) {
181 for (i=0; i < veclen; i++) {
182 freq=ds->terms[i].locc;
185 ds->terms[i].tf=freq/tf_max;
192 void tf_aug_norm(void *rsi, void *dsi) {
204 for (i=0; i < veclen; i++) {
205 freq=ds->terms[i].locc;
208 ds->terms[i].tf=K+(1-K)*(freq/tf_max);
215 void tf_square(void *rsi, void *dsi) {
222 for (i=0; i < veclen; i++) {
223 freq=ds->terms[i].locc;
225 ds->terms[i].tf=freq*freq;
232 void tf_log(void *rsi, void *dsi) {
239 for (i=0; i < veclen; i++) {
240 freq=ds->terms[i].locc;
242 ds->terms[i].tf=1+blog2(freq);
249 /* calculate inverse document frequency vector */
250 void idf_none(void *rsi, void *dsi) {
255 for (i=0; i < veclen; i++) {
256 ds->terms[i].idf=1.0;
261 void idf_tfidf(void *rsi, void *dsi) {
270 num_docs=rs->db_docs;
271 for (i=0; i < veclen; i++) {
272 gocc=ds->terms[i].gocc;
276 idf=blog2(num_docs/gocc);
277 ds->terms[i].idf=idf;
282 void idf_prob(void *rsi, void *dsi) {
291 num_docs=rs->db_docs;
292 for (i=0; i < veclen; i++) {
293 gocc=ds->terms[i].gocc;
297 idf=(num_docs-gocc)/gocc;
298 ds->terms[i].idf=idf;
303 void idf_freq(void *rsi, void *dsi) {
311 num_docs=rs->db_docs;
316 for (i=0; i < veclen; i++) {
317 ds->terms[i].idf=idf;
322 void idf_squared(void *rsi, void *dsi) {
331 num_docs=rs->db_docs;
332 for (i=0; i < veclen; i++) {
333 gocc=ds->terms[i].gocc;
337 idf=blog2(num_docs/gocc);
339 ds->terms[i].idf=idf;
344 /* calculate normalized weight (tf-idf) vector */
345 void norm_none(void *rsi, void *dsi) {
350 for (i=0; i < veclen; i++) {
351 ds->terms[i].wt=ds->terms[i].tf*ds->terms[i].idf;
356 void norm_sum(void *rsi, void *dsi) {
362 for (i=0; i < veclen; i++) {
363 ds->terms[i].wt=ds->terms[i].tf*ds->terms[i].idf;
364 tfs+=ds->terms[i].wt;
366 for (i=0; i < veclen; i++) {
368 ds->terms[i].wt=ds->terms[i].wt/tfs;
373 void norm_cosine(void *rsi, void *dsi) {
379 for (i=0; i < veclen; i++) {
380 ds->terms[i].wt=ds->terms[i].tf*ds->terms[i].idf;
381 tfs+=(ds->terms[i].wt*ds->terms[i].wt);
383 for (i=0; i < veclen; i++) {
385 ds->terms[i].wt=ds->terms[i].wt/tfs;
390 void norm_fourth(void *rsi, void *dsi) {
396 for (i=0; i < veclen; i++) {
397 ds->terms[i].wt=ds->terms[i].tf*ds->terms[i].idf;
398 fr=(ds->terms[i].wt*ds->terms[i].wt);
402 for (i=0; i < veclen; i++) {
404 ds->terms[i].wt=ds->terms[i].wt/tfs;
409 void norm_max(void *rsi, void *dsi) {
415 for (i=0; i < veclen; i++) {
416 ds->terms[i].wt=ds->terms[i].tf*ds->terms[i].idf;
417 if (ds->terms[i].wt > tfm)
420 for (i=0; i < veclen; i++) {
422 ds->terms[i].wt=ds->terms[i].wt/tfm;
427 /* add: norm_pivot, ... */
429 double sim_cosine(void *dsi1, void *dsi2) {
433 double smul=0.0, sdiv=0.0, sqr11=0.0, sqr22=0.0;
436 veclen=ds1->veclen; /* and ds2->veclen */
437 for (i=0; i < veclen; i++) {
444 sdiv=sqrt(sqr11*sqr22);
450 /* add: norm_jaccard, norm_dice, ... */
452 /* end weighting functions */
456 /* best-fully-weighted */
457 const char* def_rschema="ntc-atn";
460 void zv_init_schema(RS, const char*);
462 void zv_init(RS rs) {
463 char *sname="ntc-atn";/* obtain from configuration file */
464 yaz_log(LOG_DEBUG, "zv_init\n");
466 rs->db_docs=100000; /* assign correct value here */
467 rs->db_terms=500000; /* assign correct value here */
468 rs->db_f_max=50; /* assign correct value here */
469 rs->db_f_max_str="a"; /* assign correct value here */
470 zv_init_schema(rs, sname);
474 void zv_init_schema(RS rs, const char *sname) {
476 char c0, c1, c2, c3, c4, c5, c6;
478 yaz_log(LOG_DEBUG, "zv_init_schema\n");
480 if (slen>0) c0=sname[0]; else c0=def_rschema[0];
481 if (slen>0) c1=sname[1]; else c1=def_rschema[1];
482 if (slen>0) c2=sname[2]; else c2=def_rschema[2];
484 if (slen>0) c4=sname[4]; else c4=def_rschema[4];
485 if (slen>0) c5=sname[5]; else c5=def_rschema[5];
486 if (slen>0) c6=sname[6]; else c6=def_rschema[6];
488 /* assign doc functions */
491 rs->d_tf_fct=tf_binary;
495 rs->d_tf_fct=tf_max_norm;
499 rs->d_tf_fct=tf_aug_norm;
503 rs->d_tf_fct=tf_square;
511 rs->d_tf_fct=tf_none;
516 rs->d_idf_fct=idf_tfidf;
520 rs->d_idf_fct=idf_prob;
524 rs->d_idf_fct=idf_freq;
528 rs->d_idf_fct=idf_squared;
532 rs->d_idf_fct=idf_none;
537 rs->d_norm_fct=norm_sum;
541 rs->d_norm_fct=norm_cosine;
545 rs->d_norm_fct=norm_fourth;
549 rs->d_norm_fct=norm_max;
553 rs->d_norm_fct=norm_none;
558 /* assign query functions */
561 rs->q_tf_fct=tf_binary;
565 rs->q_tf_fct=tf_max_norm;
569 rs->q_tf_fct=tf_aug_norm;
573 rs->q_tf_fct=tf_square;
581 rs->q_tf_fct=tf_none;
586 rs->q_idf_fct=idf_tfidf;
590 rs->q_idf_fct=idf_prob;
594 rs->q_idf_fct=idf_freq;
598 rs->q_idf_fct=idf_squared;
602 rs->q_idf_fct=idf_none;
607 rs->q_norm_fct=norm_sum;
611 rs->q_norm_fct=norm_cosine;
615 rs->q_norm_fct=norm_fourth;
619 rs->q_norm_fct=norm_max;
623 rs->q_norm_fct=norm_none;
628 rs->sim_fct=sim_cosine;
629 yaz_log(LOG_DEBUG, "zv_schema %s\n", rs->rschema);
636 struct rank_class_info { /* where do we need this ? */
641 struct rank_term_info {
649 struct rank_set_info {
653 struct rank_term_info *entries;
659 * zv_create: Creates/Initialises this rank handler. This routine is
660 * called exactly once. The routine returns the class_handle.
662 static void *zv_create (ZebraHandle zh) {
663 struct rank_class_info *ci = (struct rank_class_info *)
664 xmalloc (sizeof(*ci));
665 yaz_log(LOG_DEBUG, "zv_create\n");
666 logf (LOG_DEBUG, "zv_create");
671 * zv_destroy: Destroys this rank handler. This routine is called
672 * when the handler is no longer needed - i.e. when the server
673 * dies. The class_handle was previously returned by create.
675 static void zv_destroy (struct zebra_register *reg, void *class_handle) {
676 struct rank_class_info *ci = (struct rank_class_info *) class_handle;
677 yaz_log(LOG_DEBUG, "zv_destroy\n");
678 logf (LOG_DEBUG, "zv_destroy");
684 * zv_begin: Prepares beginning of "real" ranking. Called once for
685 * each result set. The returned handle is a "set handle" and
686 * will be used in each of the handlers below.
688 static void *zv_begin (struct zebra_register *reg, void *class_handle, RSET rset)
690 struct rs_info *rs=(struct rs_info *)xmalloc(sizeof(*rs));
694 logf (LOG_DEBUG, "rank-1 zvbegin");
695 yaz_log(LOG_DEBUG, "zv_begin\n");
696 veclen=rset->no_rset_terms; /* smaller vector here */
701 rs->qdoc=(struct ds_info *)xmalloc(sizeof(*rs->qdoc));
702 rs->qdoc->terms=(struct ts_info *)xmalloc(sizeof(*rs->qdoc->terms)*rs->veclen);
703 rs->qdoc->veclen=veclen;
705 rs->rdoc=(struct ds_info *)xmalloc(sizeof(*rs->rdoc));
706 rs->rdoc->terms=(struct ts_info *)xmalloc(sizeof(*rs->rdoc->terms)*rs->veclen);
707 rs->rdoc->veclen=veclen;
708 /* yaz_log(LOG_DEBUG, "zv_begin_init\n"); */
709 for (i = 0; i < rs->veclen; i++)
711 gocc=rset->rset_terms[i]->nn;
712 /* yaz_log(LOG_DEBUG, "zv_begin_init i=%d gocc=%d\n", i, gocc); */
713 /* "rank": check name from config file */
714 if (!strncmp (rset->rset_terms[i]->flags, "rank,", 5)) {
715 yaz_log (LOG_LOG, "%s", rset->rset_terms[i]->flags);
716 /*si->entries[i].rank_flag = 1;
717 (si->no_rank_entries)++;
720 /* si->entries[i].rank_flag = 0; */
722 rs->qdoc->terms[i].gocc=gocc;
723 rs->qdoc->terms[i].locc=1; /* assume query has no duplicates */
724 rs->rdoc->terms[i].gocc=gocc;
725 rs->rdoc->terms[i].locc=0;
731 * zv_end: Terminates ranking process. Called after a result set
734 static void zv_end (struct zebra_register *reg, void *rsi)
737 yaz_log(LOG_DEBUG, "zv_end\n");
738 logf (LOG_DEBUG, "rank-1 end");
739 xfree(rs->qdoc->terms);
740 xfree(rs->rdoc->terms);
748 * zv_add: Called for each word occurence in a result set. This routine
749 * should be as fast as possible. This routine should "incrementally"
752 static void zv_add (void *rsi, int seqno, int i) {
754 /*logf (LOG_DEBUG, "rank-1 add seqno=%d term_index=%d", seqno, term_index);*/
755 /*si->last_pos = seqno;*/
756 rs->rdoc->terms[i].locc++;
760 * zv_calc: Called for each document in a result. This handler should
761 * produce a score based on previous call(s) to the add handler. The
762 * score should be between 0 and 1000. If score cannot be obtained
763 * -1 should be returned.
765 static int zv_calc (void *rsi, int sysno)
771 /* yaz_log(LOG_DEBUG, "zv_calc\n"); */
776 for (i = 0; i < veclen; i++) {
777 (*rs->q_tf_fct)(rs, rs->qdoc); /* we should actually do this once */
778 (*rs->q_idf_fct)(rs, rs->qdoc);
779 (*rs->q_norm_fct)(rs, rs->qdoc);
781 (*rs->d_tf_fct)(rs, rs->rdoc);
782 (*rs->d_idf_fct)(rs, rs->rdoc);
783 (*rs->d_norm_fct)(rs, rs->rdoc);
785 dscore=rs->sim_fct(rs->qdoc, rs->rdoc);
787 score = dscore * 1000;
788 yaz_log (LOG_LOG, "sysno=%d score=%d", sysno, score);
792 for (i = 0; i < si->no_entries; i++)
793 si->entries[i].local_occur = 0;
799 * Pseudo-meta code with sequence of calls as they occur in a
800 * server. Handlers are prefixed by --:
816 static struct rank_control rank_control_vsm = {
817 "zvrank", /* "zv_rank", */ /* zvrank */
826 struct rank_control *rankzv_class = &rank_control_vsm;