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