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