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