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