rset/rsrel.c

   1 /*
   2  * Copyright (C) 1994-1997, Index Data I/S
   3  * All rights reserved.
   4  * Sebastian Hammer, Adam Dickmeiss
   5  *
   6  * $Log: rsrel.c,v $
   7  * Revision 1.20  1997-10-31 12:37:55  adam
   8  * Code calls xfree() instead of free().
   9  *
  10  * Revision 1.19  1997/10/01 11:44:06  adam
  11  * Small improvement of new ranking.
  12  *
  13  * Revision 1.18  1997/09/24 13:36:41  adam
  14  * More work on new ranking algorithm.
  15  *
  16  * Revision 1.17  1997/09/22 12:39:07  adam
  17  * Added get_pos method for the ranked result sets.
  18  *
  19  * Revision 1.16  1997/09/17 12:19:23  adam
  20  * Zebra version corresponds to YAZ version 1.4.
  21  * Changed Zebra server so that it doesn't depend on global common_resource.
  22  *
  23  * Revision 1.15  1997/09/09 13:38:16  adam
  24  * Partial port to WIN95/NT.
  25  *
  26  * Revision 1.14  1996/11/08 11:15:58  adam
  27  * Compressed isam fully supported.
  28  *
  29  * Revision 1.13  1996/10/29 13:55:26  adam
  30  * Include of zebrautl.h instead of alexutil.h.
  31  *
  32  * Revision 1.12  1996/10/08 13:00:40  adam
  33  * Bug fix: result sets with ranked operands in boolean operations weren't
  34  * sorted.
  35  *
  36  * Revision 1.11  1996/10/07  16:05:29  quinn
  37  * Work.
  38  *
  39  * Revision 1.9  1995/12/11  09:15:26  adam
  40  * New set types: sand/sor/snot - ranked versions of and/or/not in
  41  * ranked/semi-ranked result sets.
  42  * Note: the snot not finished yet.
  43  * New rset member: flag.
  44  * Bug fix: r_delete in rsrel.c did free bad memory block.
  45  *
  46  * Revision 1.8  1995/12/05  11:25:45  adam
  47  * Doesn't include math.h.
  48  *
  49  * Revision 1.7  1995/10/12  12:41:57  adam
  50  * Private info (buf) moved from struct rset_control to struct rset.
  51  * Bug fixes in relevance.
  52  *
  53  * Revision 1.6  1995/10/10  14:00:04  adam
  54  * Function rset_open changed its wflag parameter to general flags.
  55  *
  56  * Revision 1.5  1995/10/06  14:38:06  adam
  57  * New result set method: r_score.
  58  * Local no (sysno) and score is transferred to retrieveCtrl.
  59  *
  60  * Revision 1.4  1995/09/14  07:48:56  adam
  61  * Other score calculation.
  62  *
  63  * Revision 1.3  1995/09/11  15:23:40  adam
  64  * More work on relevance search.
  65  *
  66  * Revision 1.2  1995/09/11  13:09:41  adam
  67  * More work on relevance feedback.
  68  *
  69  * Revision 1.1  1995/09/08  14:52:42  adam
  70  * Work on relevance feedback.
  71  *
  72  */
  73
  74 #include <stdio.h>
  75 #include <stdlib.h>
  76 #include <string.h>
  77 #include <assert.h>
  78
  79 #include <isam.h>
  80 #include <isamc.h>
  81 #include <rsrel.h>
  82 #include <zebrautl.h>
  83
  84 static void *r_create(const struct rset_control *sel, void *parms,
  85                       int *flags);
  86 static RSFD r_open (RSET ct, int flag);
  87 static void r_close (RSFD rfd);
  88 static void r_delete (RSET ct);
  89 static void r_rewind (RSFD rfd);
  90 static int r_count (RSET ct);
  91 static int r_read (RSFD rfd, void *buf);
  92 static int r_write (RSFD rfd, const void *buf);
  93 static int r_score (RSFD rfd, int *score);
  94
  95 static const rset_control control =
  96 {
  97     "relevance",
  98     r_create,
  99     r_open,
 100     r_close,
 101     r_delete,
 102     r_rewind,
 103     r_count,
 104     r_read,
 105     r_write,
 106     r_score
 107 };
 108
 109 const rset_control *rset_kind_relevance = &control;
 110
 111 struct rset_rel_info {
 112     int     key_size;
 113     int     max_rec;
 114     int     no_rec;
 115     int     (*cmp)(const void *p1, const void *p2);
 116     int     (*get_pos)(const void *p);
 117     char    *key_buf;                   /* key buffer */
 118     float   *score_buf;                 /* score buffer */
 119     int     *sort_idx;                  /* score sorted index */
 120     int     *sysno_idx;                /* sysno sorted index (ring buffer) */
 121     struct rset_rel_rfd *rfd_list;
 122 };
 123
 124 struct rset_rel_rfd {
 125     int     last_read_pos;
 126     int     position;
 127     int     flag;
 128     struct rset_rel_rfd *next;
 129     struct rset_rel_info *info;
 130 };
 131
 132 static void add_rec (struct rset_rel_info *info, double score, void *key)
 133 {
 134     int idx, i, j;
 135
 136     for (i = 0; i<info->no_rec; i++)
 137     {
 138         idx = info->sort_idx[i];
 139         if (score <= info->score_buf[idx])
 140             break;
 141     }
 142     if (info->no_rec < info->max_rec)
 143     {                                        /* there is room for this entry */
 144         for (j = info->no_rec; j > i; --j)
 145             info->sort_idx[j] = info->sort_idx[j-1];
 146         idx = info->sort_idx[j] = info->no_rec;
 147         ++(info->no_rec);
 148     }
 149     else if (i == 0)
 150         return;                              /* score too low */
 151     else
 152     {
 153         idx = info->sort_idx[0];             /* remove this entry */
 154
 155         --i;
 156         for (j = 0; j < i; ++j)              /* make room */
 157             info->sort_idx[j] = info->sort_idx[j+1];
 158         info->sort_idx[j] = idx;             /* allocate sort entry */
 159     }
 160     memcpy (info->key_buf + idx*info->key_size, key, info->key_size);
 161     info->score_buf[idx] = score;
 162 }
 163
 164
 165 static struct rset_rel_info *qsort_info;
 166
 167 static int qcomp (const void *p1, const void *p2)
 168 {
 169     int i1 = *(int*) p1;
 170     int i2 = *(int*) p2;
 171
 172     return qsort_info->cmp (qsort_info->key_buf + i1*qsort_info->key_size,
 173                             qsort_info->key_buf + i2*qsort_info->key_size);
 174 }
 175
 176 #define NEW_RANKING 1
 177
 178 #define SCORE_SHOW 0.0                       /* base score for showing up */
 179 #define SCORE_COOC 0.3                       /* component dependent on co-oc */
 180 #define SCORE_DYN  (1-(SCORE_SHOW+SCORE_COOC)) /* dynamic component of score */
 181
 182 static void relevance (struct rset_rel_info *info, rset_relevance_parms *parms)
 183 {
 184     char **isam_buf;
 185     char *isam_tmp_buf;
 186     int  *isam_r;
 187     int  *max_tf, *tf;
 188
 189 #if NEW_RANKING
 190     int  *pos_tf = NULL;
 191     int score_sum = 0;
 192     int no_occur = 0;
 193     char *isam_prev_buf = NULL;
 194     int fact1, fact2;
 195 #endif
 196     ISPT *isam_pt = NULL;
 197     ISAMC_PP *isamc_pp = NULL;
 198     int i;
 199
 200     logf (LOG_DEBUG, "relevance");
 201     isam_buf = xmalloc (parms->no_isam_positions * sizeof(*isam_buf));
 202     isam_r = xmalloc (sizeof (*isam_r) * parms->no_isam_positions);
 203     if (parms->is)
 204         isam_pt = xmalloc (sizeof (*isam_pt) * parms->no_isam_positions);
 205     else if (parms->isc)
 206         isamc_pp = xmalloc (sizeof (*isamc_pp) * parms->no_isam_positions);
 207     else
 208     {
 209         logf (LOG_FATAL, "No isamc or isam in rs_rel");
 210         abort ();
 211     }
 212     isam_tmp_buf = xmalloc (info->key_size);
 213     max_tf = xmalloc (sizeof (*max_tf) * parms->no_terms);
 214     tf = xmalloc (sizeof (*tf) * parms->no_terms);
 215
 216     for (i = 0; i<parms->no_terms; i++)
 217         max_tf[i] = 0;
 218     for (i = 0; i<parms->no_isam_positions; i++)
 219     {
 220         isam_buf[i] = xmalloc (info->key_size);
 221         if (isam_pt)
 222         {
 223             isam_pt[i] = is_position (parms->is, parms->isam_positions[i]);
 224             max_tf [parms->term_no[i]] = is_numkeys (isam_pt[i]);
 225             isam_r[i] = is_readkey (isam_pt[i], isam_buf[i]);
 226         }
 227         else if (isamc_pp)
 228         {
 229             isamc_pp[i] = isc_pp_open (parms->isc, parms->isam_positions[i]);
 230             max_tf [parms->term_no[i]] = isc_pp_num (isamc_pp[i]);
 231             isam_r[i] = isc_pp_read (isamc_pp[i], isam_buf[i]);
 232         }
 233         logf (LOG_DEBUG, "max tf %d = %d", i, max_tf[i]);
 234     }
 235 #if NEW_RANKING
 236     while (1)
 237     {
 238         int r, min = -1;
 239         int pos = 0;
 240         for (i = 0; i<parms->no_isam_positions; i++)
 241             if (isam_r[i] &&
 242                 (min < 0 ||
 243                  (r = (*parms->cmp)(isam_buf[i], isam_buf[min])) < 1))
 244                 min = i;
 245         if (!isam_prev_buf)
 246         {
 247             pos_tf = xmalloc (sizeof(*pos_tf) * parms->no_isam_positions);
 248             isam_prev_buf = xmalloc (info->key_size);
 249             fact1 = 100000/parms->no_isam_positions;
 250             fact2 = 100000/(parms->no_isam_positions*parms->no_isam_positions);
 251
 252             no_occur = score_sum = 0;
 253             memcpy (isam_prev_buf, isam_buf[min], info->key_size);
 254             for (i = 0; i<parms->no_isam_positions; i++)
 255                 pos_tf[i] = -10;
 256         }
 257         else if (min < 0 ||
 258                  (*parms->cmp)(isam_buf[min], isam_prev_buf) > 1)
 259         {
 260             logf (LOG_LOG, "final occur = %d ratio=%d",
 261                   no_occur, score_sum / no_occur);
 262             add_rec (info, score_sum / (10000.0*no_occur), isam_prev_buf);
 263             if (min < 0)
 264                 break;
 265             no_occur = score_sum = 0;
 266             memcpy (isam_prev_buf, isam_buf[min], info->key_size);
 267             for (i = 0; i<parms->no_isam_positions; i++)
 268                 pos_tf[i] = -10;
 269         }
 270         pos = (*parms->get_pos)(isam_buf[min]);
 271         logf (LOG_LOG, "pos=%d", pos);
 272         for (i = 0; i<parms->no_isam_positions; i++)
 273         {
 274             int d = pos - pos_tf[i];
 275
 276             no_occur++;
 277             if (pos_tf[i] < 0 && i != min)
 278                 continue;
 279             if (d < 10)
 280                 d = 10;
 281             if (i == min)
 282                 score_sum += fact2 / d;
 283             else
 284                 score_sum += fact1 / d;
 285         }
 286         pos_tf[min] = pos;
 287         logf (LOG_LOG, "score_sum = %d", score_sum);
 288         i = min;
 289         if (isam_pt)
 290             isam_r[i] = is_readkey (isam_pt[i], isam_buf[i]);
 291         else if (isamc_pp)
 292             isam_r[i] = isc_pp_read (isamc_pp[i], isam_buf[i]);
 293     }
 294     xfree (isam_prev_buf);
 295     xfree (pos_tf);
 296 #else
 297     while (1)
 298     {
 299         int min = -1, i, r;
 300         double score;
 301         int co_oc, last_term;    /* Number of co-occurrences */
 302
 303         last_term = -1;
 304         /* find min with lowest sysno */
 305         for (i = 0; i<parms->no_isam_positions; i++)
 306         {
 307             if (isam_r[i] &&
 308                (min < 0 || (r = (*parms->cmp)(isam_buf[i], isam_buf[min])) < 2))
 309             {
 310                 min = i;
 311                 co_oc = 1;
 312             }
 313             else if (!r && last_term != parms->term_no[i]) /* new occurrence */
 314                 co_oc++;
 315             last_term = parms->term_no[i];
 316         }
 317
 318         if (min < 0)
 319             break;
 320         memcpy (isam_tmp_buf, isam_buf[min], info->key_size);
 321         /* calculate for all with those sysno */
 322         for (i = 0; i < parms->no_terms; i++)
 323             tf[i] = 0;
 324         for (i = 0; i<parms->no_isam_positions; i++)
 325         {
 326             int r;
 327
 328             if (isam_r[i])
 329                 r = (*parms->cmp)(isam_buf[i], isam_tmp_buf);
 330             else
 331                 r = 2;
 332             if (r <= 1 && r >= -1)
 333             {
 334                 do
 335                 {
 336                     tf[parms->term_no[i]]++;
 337                     if (isam_pt)
 338                         isam_r[i] = is_readkey (isam_pt[i], isam_buf[i]);
 339                     else if (isamc_pp)
 340                         isam_r[i] = isc_pp_read (isamc_pp[i], isam_buf[i]);
 341                 } while (isam_r[i] &&
 342                          (*parms->cmp)(isam_buf[i], isam_tmp_buf) <= 1);
 343             }
 344         }
 345         /* calculate relevance value */
 346         score = 0.0;
 347         for (i = 0; i<parms->no_terms; i++)
 348             if (tf[i])
 349                 score += SCORE_SHOW + SCORE_COOC*co_oc/parms->no_terms +
 350                     SCORE_DYN*tf[i]/max_tf[i];
 351         /* if value is in the top score, then save it - don't emit yet */
 352         add_rec (info, score/parms->no_terms, isam_tmp_buf);
 353     }
 354 #endif
 355     for (i = 0; i<info->no_rec; i++)
 356         info->sysno_idx[i] = i;
 357     qsort_info = info;
 358     qsort (info->sysno_idx, info->no_rec, sizeof(*info->sysno_idx), qcomp);
 359     for (i = 0; i<parms->no_isam_positions; i++)
 360     {
 361         if (isam_pt)
 362             is_pt_free (isam_pt[i]);
 363         if (isamc_pp)
 364             isc_pp_close (isamc_pp[i]);
 365         xfree (isam_buf[i]);
 366     }
 367     xfree (max_tf);
 368     xfree (isam_tmp_buf);
 369     xfree (isam_buf);
 370     xfree (isam_r);
 371     xfree (isam_pt);
 372     xfree (isamc_pp);
 373     xfree(tf);
 374 }
 375
 376 static void *r_create (const struct rset_control *sel, void *parms,
 377                        int *flags)
 378 {
 379     rset_relevance_parms *r_parms = parms;
 380     struct rset_rel_info *info;
 381
 382     *flags |= RSET_FLAG_RANKED;
 383     info = xmalloc (sizeof(struct rset_rel_info));
 384     info->key_size = r_parms->key_size;
 385     assert (info->key_size > 1);
 386     info->max_rec = r_parms->max_rec;
 387     assert (info->max_rec > 1);
 388     info->cmp = r_parms->cmp;
 389     info->get_pos = r_parms->get_pos;
 390
 391     info->key_buf = xmalloc (info->key_size * info->max_rec);
 392     info->score_buf = xmalloc (sizeof(*info->score_buf) * info->max_rec);
 393     info->sort_idx = xmalloc (sizeof(*info->sort_idx) * info->max_rec);
 394     info->sysno_idx = xmalloc (sizeof(*info->sysno_idx) * info->max_rec);
 395     info->no_rec = 0;
 396     info->rfd_list = NULL;
 397
 398     relevance (info, r_parms);
 399     return info;
 400 }
 401
 402 static RSFD r_open (RSET ct, int flag)
 403 {
 404     struct rset_rel_rfd *rfd;
 405     struct rset_rel_info *info = ct->buf;
 406
 407     if (flag & RSETF_WRITE)
 408     {
 409         logf (LOG_FATAL, "relevance set type is read-only");
 410         return NULL;
 411     }
 412     rfd = xmalloc (sizeof(*rfd));
 413     rfd->flag = flag;
 414     rfd->next = info->rfd_list;
 415     rfd->info = info;
 416     info->rfd_list = rfd;
 417     r_rewind (rfd);
 418     return rfd;
 419 }
 420
 421 static void r_close (RSFD rfd)
 422 {
 423     struct rset_rel_info *info = ((struct rset_rel_rfd*)rfd)->info;
 424     struct rset_rel_rfd **rfdp;
 425
 426     for (rfdp = &info->rfd_list; *rfdp; rfdp = &(*rfdp)->next)
 427         if (*rfdp == rfd)
 428         {
 429             *rfdp = (*rfdp)->next;
 430             xfree (rfd);
 431             return;
 432         }
 433     logf (LOG_FATAL, "r_close but no rfd match!");
 434     assert (0);
 435 }
 436
 437 static void r_delete (RSET ct)
 438 {
 439     struct rset_rel_info *info = ct->buf;
 440
 441     assert (info->rfd_list == NULL);
 442     xfree (info->key_buf);
 443     xfree (info->score_buf);
 444     xfree (info->sort_idx);
 445     xfree (info->sysno_idx);
 446     xfree (info);
 447 }
 448
 449 static void r_rewind (RSFD rfd)
 450 {
 451     struct rset_rel_rfd *p = rfd;
 452     struct rset_rel_info *info = p->info;
 453
 454     if (p->flag & RSETF_SORT_RANK)
 455         p->position = info->no_rec;
 456     else
 457         p->position = 0;
 458 }
 459
 460 static int r_count (RSET ct)
 461 {
 462     struct rset_rel_info *info = ct->buf;
 463
 464     return info->no_rec;
 465 }
 466
 467 static int r_read (RSFD rfd, void *buf)
 468 {
 469     struct rset_rel_rfd *p = rfd;
 470     struct rset_rel_info *info = p->info;
 471
 472     if (p->flag & RSETF_SORT_RANK)
 473     {
 474         if (p->position <= 0)
 475             return 0;
 476         --(p->position);
 477         p->last_read_pos = info->sort_idx[p->position];
 478     }
 479     else
 480     {
 481         if (p->position == info->no_rec)
 482             return 0;
 483         p->last_read_pos = info->sysno_idx[p->position];
 484         ++(p->position);
 485     }
 486     memcpy ((char*) buf,
 487             info->key_buf + info->key_size * p->last_read_pos,
 488             info->key_size);
 489     return 1;
 490 }
 491
 492 static int r_score (RSFD rfd, int *score)
 493 {
 494     struct rset_rel_rfd *p = rfd;
 495     struct rset_rel_info *info = p->info;
 496
 497     *score = (int) (1000*info->score_buf[p->last_read_pos]);
 498     return 1;
 499 }
 500
 501 static int r_write (RSFD rfd, const void *buf)
 502 {
 503     logf (LOG_FATAL, "relevance set type is read-only");
 504     return -1;
 505 }