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