rset/rsrel.c

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