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