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