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