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