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