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