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