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