rset/rsrel.c

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