form_res_rels.c

/* 
   Copyright (c) 2008 - Chris Buckley. 

   Permission is granted for use and modification of this file for
   research, non-commercial purposes. 
*/
#include "common.h"
#include "sysfunc.h"
#include "trec_eval.h"
#include "trec_format.h"
#include "functions.h"
/* Takes the top docs and judged docs for a query, and returns a
   rel_rank object giving the ordered relevance values for retrieved
   docs, plus relevance occurrence statatistics.
   Relevance value is
       value in text_qrels if docno is in text_qrels and was judged
           (assumed to be a small non-negative integer)
       RELVALUE_NONPOOL (-1) if docno is not in text_qrels
       RELVALUE_UNJUDGED (-2) if docno is in text_qrels and was not judged.

   This procedure may be called repeatedly for a given topic - returned
   values are cached until the query changes.

   results and rel_info formats must be "trec_results" and "qrels"
   respectively.  

   UNDEF returned if error, 0 if used cache values, 1 if new values.
*/

static int comp_rank_judged(), comp_sim_docno(), comp_docno();

/* Definitions used for temporary and cached values */
typedef struct {
    char *docno;
    double sim;
    long rank;
    long rel;
} DOCNO_INFO;

/* Current cached query */
static char *current_query = "no query";
static long max_current_query = 0;

/* Space reserved for cached returned values */
static long *rel_levels;
static long max_rel_levels = 0;
static RES_RELS saved_res_rels;
static long *ranked_rel_list;
static long max_ranked_rel_list = 0;

/* Space reserved for intermediate values */
static DOCNO_INFO *docno_info;
static long max_docno_info = 0;


int
te_form_res_rels(const EPI * epi, const REL_INFO * rel_info,
                 const RESULTS * results, RES_RELS * res_rels)
{
    long i;
    long num_results;
    long max_rel;

    TEXT_RESULTS_INFO *text_results_info;
    TEXT_QRELS_INFO *trec_qrels;

    TEXT_QRELS *qrels_ptr, *end_qrels;

    if (0 == strcmp(current_query, results->qid)) {
        /* Have done this query already. Return cached values */
        *res_rels = saved_res_rels;
        return (0);
    }

    /* Check that format type of result info and rel info are correct */
    if (strcmp("qrels", rel_info->rel_format) ||
        strcmp("trec_results", results->ret_format)) {
        fprintf(stderr,
                "trec_eval.form_res_qrels: rel_info format not qrels or results format not trec_results\n");
        return (UNDEF);
    }

    /* Make sure enough space for query and save copy */
    i = strlen(results->qid) + 1;
    if (NULL == (current_query =
                 te_chk_and_malloc(current_query, &max_current_query,
                                   i, sizeof(char))))
        return (UNDEF);
    (void) strncpy(current_query, results->qid, i);

    text_results_info = (TEXT_RESULTS_INFO *) results->q_results;
    trec_qrels = (TEXT_QRELS_INFO *) rel_info->q_rel_info;

    num_results = text_results_info->num_text_results;

    /* Check and reserve space for output structure */
    /* Reserve space for temp structure copying results */
    if (NULL == (ranked_rel_list =
                 te_chk_and_malloc(ranked_rel_list, &max_ranked_rel_list,
                                   num_results, sizeof(long))) ||
        NULL == (docno_info =
                 te_chk_and_malloc(docno_info, &max_docno_info,
                                   num_results, sizeof(DOCNO_INFO))))
        return (UNDEF);

    for (i = 0; i < num_results; i++) {
        docno_info[i].docno = text_results_info->text_results[i].docno;
        docno_info[i].sim = text_results_info->text_results[i].sim;
    }

    /* Sort results by sim, breaking ties lexicographically using docno */
    qsort((char *) docno_info,
          (int) num_results, sizeof(DOCNO_INFO), comp_sim_docno);

    /* Only look at epi->max_num_docs_per_topic (not normally an issue) */
    if (num_results > epi->max_num_docs_per_topic)
        num_results = epi->max_num_docs_per_topic;

    /* Add ranks to docno_info (starting at 1) */
    for (i = 0; i < num_results; i++) {
        docno_info[i].rank = i + 1;
    }

    /* Sort trec_top lexicographically */
    qsort((char *) docno_info,
          (int) num_results, sizeof(DOCNO_INFO), comp_docno);

    /* Error checking for duplicates */
    for (i = 1; i < num_results; i++) {
        if (0 == strcmp(docno_info[i].docno, docno_info[i - 1].docno)) {
            fprintf(stderr, "trec_eval.form_res_qrels: duplicate docs %s",
                    docno_info[i].docno);
            return (UNDEF);
        }
    }

    /* Find max_rel among qid, reserve and zero space for rel_levels */
    /* Check for duplicate docnos. */
    qrels_ptr = trec_qrels->text_qrels;
    end_qrels = &trec_qrels->text_qrels[trec_qrels->num_text_qrels];
    max_rel = qrels_ptr->rel;
    qrels_ptr++;
    while (qrels_ptr < end_qrels) {
        if (max_rel < qrels_ptr->rel)
            max_rel = qrels_ptr->rel;
        if (0 == strcmp((qrels_ptr - 1)->docno, qrels_ptr->docno)) {
            fprintf(stderr, "trec_eval.form_res_rels: duplicate docs %s\n",
                    qrels_ptr->docno);
            return (UNDEF);
        }
        qrels_ptr++;
    }
    if (NULL == (rel_levels =
                 te_chk_and_malloc(rel_levels, &max_rel_levels,
                                   (max_rel + 1), sizeof(long))))
        return (UNDEF);
    (void) memset(rel_levels, 0, (max_rel + 1) * sizeof(long));

    /* Construct rank_rel array and rel_levels */
    /* Go through docno_info, trec_qrels in parallel to determine relevance
       for each doc in docno_info.
       Note that trec_qrels already sorted by docno with no duplicates */
    qrels_ptr = trec_qrels->text_qrels;
    end_qrels = &trec_qrels->text_qrels[trec_qrels->num_text_qrels];
    for (i = 0; i < num_results; i++) {
        while (qrels_ptr < end_qrels &&
               strcmp(qrels_ptr->docno, docno_info[i].docno) < 0) {
            if (qrels_ptr->rel >= 0)
                rel_levels[qrels_ptr->rel]++;
            qrels_ptr++;
        }
        if (qrels_ptr >= end_qrels ||
            strcmp(qrels_ptr->docno, docno_info[i].docno) > 0) {
            /* Doc is non-judged */
            docno_info[i].rel = RELVALUE_NONPOOL;
        } else {
            /* Doc is in pool, assign relevance */
            if (qrels_ptr->rel < 0)
                /* In pool, but unjudged (eg, infAP uses a sample of pool) */
                docno_info[i].rel = RELVALUE_UNJUDGED;
            else {
                docno_info[i].rel = qrels_ptr->rel;
            }
            if (qrels_ptr->rel >= 0)
                rel_levels[qrels_ptr->rel]++;
            qrels_ptr++;
        }
    }
    /* Finish counting rels */
    while (qrels_ptr < end_qrels) {
        if (qrels_ptr->rel >= 0)
            rel_levels[qrels_ptr->rel]++;
        qrels_ptr++;
    }

    /* Construct ranked_rel_list and associated counts */
    saved_res_rels.num_rel_ret = 0;
    saved_res_rels.num_nonpool = 0;
    saved_res_rels.num_unjudged_in_pool = 0;
    saved_res_rels.results_rel_list = ranked_rel_list;
    saved_res_rels.rel_levels = rel_levels;
    if (epi->judged_docs_only_flag) {
        /* If judged_docs_only_flag, then must fix up ranks to
           reflect unjudged docs being thrown out. Note: done this way
           to preserve original tie-breaking based on text docno */
        long rrl;
        /* Sort tuples by increasing rank among judged docs */
        qsort((char *) docno_info,
              (int) num_results, sizeof(DOCNO_INFO), comp_rank_judged);
        rrl = 0;
        i = 0;
        while (i < num_results && docno_info[i].rel >= 0) {
            if (docno_info[i].rel >= epi->relevance_level)
                saved_res_rels.num_rel_ret++;
            saved_res_rels.results_rel_list[rrl++] = docno_info[i++].rel;
        }
        saved_res_rels.num_ret = rrl;
    } else {
        /* Normal path.  Assign rel value to appropriate rank */
        for (i = 0; i < num_results; i++) {
            saved_res_rels.results_rel_list[docno_info[i].rank - 1] =
                docno_info[i].rel;
            if (RELVALUE_NONPOOL == docno_info[i].rel)
                saved_res_rels.num_nonpool++;
            else if (RELVALUE_UNJUDGED == docno_info[i].rel)
                saved_res_rels.num_unjudged_in_pool++;
            else {
                if (docno_info[i].rel >= epi->relevance_level)
                    saved_res_rels.num_rel_ret++;
            }
        }
        saved_res_rels.num_ret = num_results;
    }
    saved_res_rels.num_rel = 0;
    for (i = 0; i <= max_rel; i++) {
        if (saved_res_rels.rel_levels[i]) {
            saved_res_rels.num_rel_levels = i + 1;
            if (i >= epi->relevance_level)
                saved_res_rels.num_rel += saved_res_rels.rel_levels[i];
        }
    }

    *res_rels = saved_res_rels;

    return (1);
}

static int comp_rank_judged(ptr1, ptr2)
DOCNO_INFO *ptr1;
DOCNO_INFO *ptr2;
{
    if (ptr1->rel >= 0 && ptr2->rel >= 0) {
        if (ptr1->rank < ptr2->rank)
            return (-1);
        if (ptr1->rank > ptr2->rank)
            return (1);
        return (0);
    }
    if (ptr1->rel >= 0)
        return (-1);
    if (ptr2->rel >= 0)
        return (1);
    return (0);
}

static int comp_sim_docno(ptr1, ptr2)
DOCNO_INFO *ptr1;
DOCNO_INFO *ptr2;
{
    if (ptr1->sim > ptr2->sim)
        return (-1);
    if (ptr1->sim < ptr2->sim)
        return (1);
    return (strcmp(ptr2->docno, ptr1->docno));
}

static int comp_docno(ptr1, ptr2)
DOCNO_INFO *ptr1;
DOCNO_INFO *ptr2;
{
    return (strcmp(ptr1->docno, ptr2->docno));
}


int te_form_res_rels_cleanup()
{
    if (max_current_query > 0) {
        Free(current_query);
        max_current_query = 0;
        current_query = "no_query";
    }
    if (max_rel_levels > 0) {
        Free(rel_levels);
        max_rel_levels = 0;
    }
    if (max_ranked_rel_list > 0) {
        Free(ranked_rel_list);
        max_ranked_rel_list = 0;
    }
    if (max_docno_info > 0) {
        Free(docno_info);
        max_docno_info = 0;
    }
    return (1);
}