char *usageText = "Usage: %s [options] qrels run (-help for full usage information)\n"; char *helpText = "ndeval [options] qrels run\n" " Compute novelty and diversity evaluation measures for TREC Web tasks.\n" " Evalution measures are written to standard output as a CSV file.\n" "\n" " options:\n" " -alpha value\n" " Redundancy intolerance (parameter for computing alpha-nDCG and NRBP)\n" " -beta value\n" " Patience (parameter for computing NRBP)\n" " -traditional\n" " Sort runs by score and then by docno, which is the traditional\n" " behavior for TREC. By default, the program sorts runs by rank.\n" " -c\n" " Average over the complete set of topics in the relevance judgments\n" " instead of the topics in the intersection of relevance judgments\n" " and results.\n" " -M depth\n" " Cut off run at given depth.\n" "\n" " Computes the following measures. All measures are \"intent aware\" in\n" " the sense of Agrawal et al. (WSDM 20009). Normalization may be collection\n" " dependent or collection independent.\n" "\n" " ERR-IA@k for k = 5, 10 and 20\n" " Chapelle et al. (CIKM 2009) with collection-independent normalization\n" " nERR-IA@k for k = 5, 10 and 20\n" " Chapelle et al. (CIKM 2009) with collection-dependent normalization\n" " alpha-DCG@k for k = 5, 10 and 20\n" " Clarke et al. (SIGIR 2008) with collection-independent normalization\n" " alpha-nDCG@k for k = 5, 10 and 20\n" " Clarke et al., SIGIR 2008 with collection-dependent normalization\n" " NRBP\n" " Clarke et al. (ICTIR 2009) with collection-independent normalization\n" " nNRBP\n" " Clarke et al. (ICTIR 2009) with collection-dependent normalization\n" " MAP-IA\n" " intent aware mean average precision\n" " P-IA@k for k = 5, 10, 20\n" " intent aware precision@k\n" " strec@k for k = 5, 10, 20\n" " subtopic recall (the number of subtopics covered by the top k docs)\n"; #include #include #include #include #include #include #define DEPTH 20 /* max depth for computing alpha-ndcg, precision-ia, etc. */ #define ALPHA 0.5 /* default alpha value for alpha-nDCG and NRBP */ #define BETA 0.5 /* default beta value for NRBP */ static char *version = "version 4.4 (Thu 14 Oct 2010 18:34:50 EDT)"; #define LARGE_ENOUGH 100000 /* Global command line parameters */ static double alpha = ALPHA; /* alpha value for alpha-nDCG and NRBP */ static double beta = BETA; /* beta value for NRBP */ static int traditional = 0; /* use traditional TREC sort order for runs */ static int depthM = 0; /* cut off rank for runs (0 => no cut off) */ static char *programName = (char *) 0; static void error (char *format, ...) { va_list args; fflush (stderr); if (programName) fprintf (stderr, "%s: ", programName); va_start (args, format); vfprintf (stderr, format, args); va_end (args); fflush (stderr); exit (1); } static void * localMalloc (size_t size) { void *memory; if ((memory = malloc (size))) return memory; else { error ("Out of memory!\n"); /*NOTREACHED*/ return (void *) 0; } } static void * localRealloc (void *memory, size_t size) { if ((memory = realloc (memory, size))) return memory; else { error ("Out of memory!\n"); /*NOTREACHED*/ return (void *) 0; } } static char * localStrdup (const char *string) { return strcpy (localMalloc (strlen (string) + 1), string); } static void setProgramName (char *argv0) { char *pn; if (argv0 == (char *) 0) { programName = (char *) 0; return; } for (pn = argv0 + strlen (argv0); pn > argv0; --pn) if (*pn == '/') { pn++; break; } programName = localStrdup (pn); } static char * getline (FILE *fp) { int const GETLINE_INITIAL_BUFSIZ = 256; static unsigned bufsiz = 0; static char *buffer = (char *) 0; unsigned count = 0; if (bufsiz == 0) { buffer = (char *) localMalloc ((unsigned) GETLINE_INITIAL_BUFSIZ); bufsiz = GETLINE_INITIAL_BUFSIZ; } if (fgets (buffer, bufsiz, fp) == NULL) return (char *) 0; for (;;) { unsigned nlpos = strlen (buffer + count) - 1; if (buffer[nlpos + count] == '\n') { if (nlpos && buffer[nlpos + count - 1] == '\r') --nlpos; buffer[nlpos + count] = '\0'; return buffer; } count = bufsiz - 1; bufsiz <<= 1; buffer = (char *) localRealloc (buffer, (unsigned) bufsiz); if (fgets (buffer + count, count + 2, fp) == NULL) { buffer[count] = '\0'; return buffer; } } } static int split (char *s, char **a, int m) { int n = 0; while (n < m) { for (; isspace (*s); s++) ; if (*s == '\0') return n; a[n++] = s; for (s++; *s && !isspace (*s); s++) ; if (*s == '\0') return n; *s++ = '\0'; } return n; } static int naturalNumber (char *s) { int value = 0; if (s == (char *) 0 || *s == '\0') return -1; for (; *s; s++) if (*s >= '0' && *s <= '9') { if (value > LARGE_ENOUGH) return -1; value = 10*value + (*s - '0'); } else return -1; return value; } /* parseTopic: topic numbers in run files may be prefaced by a string indicating the task; remove this string (e.g., "wt09-") and extract the topic number; we assume the string ends with a "-" character; */ static int parseTopic(char *s) { if (*s >= '0' && *s <= '9') return naturalNumber (s); for (;*s && *s != '-'; s++) ; return naturalNumber (s + 1); } struct result { /* a single result, with a pointer to relevance judgments */ char *docno; int topic, rank, *rel; double score; /* used only for traditional sort */ }; struct rList { /* result list (or summarized qrels) for a single topic */ struct result *list; int topic, subtopics, actualSubtopics, results; int nrel, *nrelSub; double mapIA, map; double nrbp, nnrbp; double dcg[DEPTH], ndcg[DEPTH]; double err[DEPTH], nerr[DEPTH]; double precision[DEPTH]; /* really precision-IA */ double strec[DEPTH]; /* subtopic recall */ }; struct qrel { /* a single qrel */ char *docno; int topic, subtopic, judgment; }; /* qrelCompare: qsort comparison function for qrels */ static int qrelCompare (const void *a, const void *b) { struct qrel *aq = (struct qrel *) a; struct qrel *bq = (struct qrel *) b; if (aq->topic < bq->topic) return -1; if (aq->topic > bq->topic) return 1; return strcmp (aq->docno, bq->docno); } /* qrelSort: sort qrels by topic and then by docno */ static void qrelSort (struct qrel *q, int n) { qsort (q, n, sizeof (struct qrel), qrelCompare); } /* qrelCountTopics: count the number of distinct topics in a qrel file; assume qrels are sorted */ static int qrelCountTopics (struct qrel *q, int n) { int i, topics = 1, currentTopic = q[0].topic; for (i = 1; i < n; i++) if (q[i].topic != currentTopic) { topics++; currentTopic = q[i].topic; } return topics; } /* nrel: for a given qrel result list, compute overall number of relevant documents by assuming that a document which is relevant to any subtopic is relevant to the topic as a whole; used to compute (non-intent-aware) MAP. */ static void nrel (struct rList *rl) { int i, j; rl->nrel = 0; for (i = 0; i < rl->results; i++) { int todo = 1; for (j = 0; todo && j < rl->subtopics; j++) if (rl->list[i].rel[j]) { rl->nrel++; todo = 0; } } } /* actualSubtopics: for a given qrel result list, determine the number of subtopics actually represented; if a subtopic has never received a positive judgment, we ignore it. */ static void actualSubtopics (struct rList *rl) { int i; rl->actualSubtopics = 0; for (i = 0; i < rl->subtopics; i++) if (rl->nrelSub[i]) rl->actualSubtopics++; } /* idealResult: for a qrel result list, assign ranks to maximize gain at each rank; the problem is NP-complete, but a simple greedy algorithm works fine */ static void idealResult (struct rList *rl) { int i, rank; double *subtopicGain = (double *) alloca (rl->subtopics*sizeof(double)); for (i = 0; i < rl->subtopics; i++) subtopicGain[i] = 1.0; for (i = 0; i < rl->results; i++) rl->list[i].rank = 0; /* horrible quadratic greedy approximation of the ideal result */ for (rank = 1; rank <= rl->results; rank++) { int where = -1; double maxScore = 0.0; for (i = 0; i < rl->results; i++) if (rl->list[i].rank == 0) { int j; double currentScore = 0.0; for (j = 0; j < rl->subtopics; j++) if (rl->list[i].rel[j]) currentScore += subtopicGain[j]; /* tied scores are arbitrarily resolved by docno */ if ( where == -1 || currentScore > maxScore || ( currentScore == maxScore && strcmp (rl->list[i].docno, rl->list[where].docno) > 0 ) ) { maxScore = currentScore; where = i; } } rl->list[where].rank = rank; for (i = 0; i < rl->subtopics; i++) if (rl->list[where].rel[i]) subtopicGain[i] *= (1.0 - alpha); } } /* resultCompareByRank: qsort comparison funtion for results; sort by topic and then by rank */ int resultCompareByRank (const void *a, const void *b) { struct result *ar = (struct result *) a; struct result *br = (struct result *) b; if (ar->topic < br->topic) return -1; if (ar->topic > br->topic) return 1; return ar->rank - br->rank; } /* resultSortByRank: sort results, first by topic and then by rank */ static void resultSortByRank (struct result *list, int results) { qsort (list, results, sizeof (struct result), resultCompareByRank); } /* resultCompareByDocno: qsort comparison funtion for results; sort by topic and then by docno */ static int resultCompareByDocno (const void *a, const void *b) { struct result *ar = (struct result *) a; struct result *br = (struct result *) b; if (ar->topic < br->topic) return -1; if (ar->topic > br->topic) return 1; return strcmp(ar->docno, br->docno); } /* resultSortByRank: sort results, first by topic and then by docno */ static void resultSortByDocno (struct result *list, int results) { qsort (list, results, sizeof (struct result), resultCompareByDocno); } /* resultCompareByScore: qsort comparison funtion for results; sort by topic, then by score, and then by docno, which is the traditional sort order for TREC runs */ int resultCompareByScore (const void *a, const void *b) { struct result *ar = (struct result *) a; struct result *br = (struct result *) b; if (ar->topic < br->topic) return -1; if (ar->topic > br->topic) return 1; if (ar->score < br->score) return 1; if (ar->score > br->score) return -1; return strcmp (br->docno, ar->docno); } /* resultSortByScore: sort results; first by topic, then by score, and then by docno */ static void resultSortByScore (struct result *list, int results) { qsort (list, results, sizeof (struct result), resultCompareByScore); } /* computeMAP: compute intent-aware mean average precision (MAP-IA); also computes standard MAP by assuming that a document relevant to any subtopic is relevant to the topic as a whole. */ static void computeMAP (struct rList *rl) { int i,j; double count = 0.0, total = 0.0; int *subtopicCount = (int *) alloca (rl->subtopics*sizeof(int)); double *subtopicTotal = (double *) alloca (rl->subtopics*sizeof(double)); rl->map = rl->mapIA = 0.0; if (rl->actualSubtopics == 0) return; for (j = 0; j < rl->subtopics; j++) subtopicCount[j] = subtopicTotal[j] = 0.0; for (i = 0; i < rl->results; i++) { int todo = 1; if (rl->list[i].rel) for (j = 0; j < rl->subtopics; j++) if (rl->list[i].rel[j]) { subtopicCount[j]++; subtopicTotal[j] += subtopicCount[j]/((double)(i+1)); if (todo) { count++; total += count/((double)(i+1)); todo = 0; } } } rl->map = total/rl->nrel; rl->mapIA = 0.0; for (j = 0; j < rl->subtopics; j++) if (rl->nrelSub[j]) rl->mapIA += subtopicTotal[j]/rl->nrelSub[j]; rl->mapIA /= rl->actualSubtopics; } /* computeNRBP: compute NRBP for a result list; assumes all results are labeled with relevance judgments */ static void computeNRBP (struct rList *rl) { int i; double decay = 1.0; double *subtopicGain = (double *) alloca (rl->subtopics*sizeof(double)); rl->nrbp = 0.0; if (rl->actualSubtopics == 0) return; for (i = 0; i < rl->subtopics; i++) subtopicGain[i] = 1.0; for (i = 0; i < rl->results; i++) { int j; double score = 0.0; if (rl->list[i].rel) for (j = 0; j < rl->subtopics; j++) if (rl->list[i].rel[j]) { score += subtopicGain[j]; subtopicGain[j] *= (1.0 - alpha); } rl->nrbp += score*decay; decay *= beta; } rl->nrbp *= (1 - (1 - alpha)*beta)/rl->actualSubtopics; } /* discount: compute (and cache) ranked based discount for ndcg */ double discount (int rank) { static double cache[LARGE_ENOUGH]; static int top = 0; if (rank > 0) if (rank < top) return cache[rank]; else if (rank < LARGE_ENOUGH) { do { cache[top] = log(2.0)/log(top + 2.0); top++; } while (rank >= top); return cache[rank]; } else return log(2.0)/log(rank + 2.0); else return 1; } /* computeERR: compute ERR for a result list (a run or qrels); assumes all results are labeled with relevance judgments; the result is normalized using a simple "ideal ideal" normalization */ static void computeERR (struct rList *rl) { int i; double *subtopicGain = (double *) alloca (rl->subtopics*sizeof(double)); double idealIdeal[DEPTH], idealIdealGain = (double) rl->actualSubtopics; for (i = 0; i < DEPTH; i++) rl->err[i] = 0.0; if (rl->actualSubtopics == 0) return; for (i = 0; i < rl->subtopics; i++) subtopicGain[i] = 1.0; for (i = 0; i < DEPTH && i < rl->results; i++) { int j; double score = 0.0; if (rl->list[i].rel) for (j = 0; j < rl->subtopics; j++) if (rl->list[i].rel[j]) { score += subtopicGain[j]; subtopicGain[j] *= (1.0 - alpha); } rl->err[i] = score/((double)(i + 1)); } for (i = 0; i < DEPTH; i++) { idealIdeal[i] = idealIdealGain/((double)(i + 1)); idealIdealGain *= (1.0 - alpha); } for (i = 1; i < DEPTH; i++) { rl->err[i] += rl->err[i-1]; idealIdeal[i] += idealIdeal[i - 1]; } /* simple normalization ("ideal ideal normalization") */ for (i = 1; i < DEPTH; i++) rl->err[i] /= idealIdeal[i]; } /* computeDCG: compute DCG for a result list (a run or qrels); assumes all results are labeled with relevance judgments; the result is normalized using a simple "ideal ideal" normalization (standard nDCG normalization comes later) */ static void computeDCG (struct rList *rl) { int i; double *subtopicGain = (double *) alloca (rl->subtopics*sizeof(double)); double idealIdeal[DEPTH], idealIdealGain = (double) rl->actualSubtopics; for (i = 0; i < DEPTH; i++) rl->dcg[i] = 0.0; if (rl->actualSubtopics == 0) return; for (i = 0; i < rl->subtopics; i++) subtopicGain[i] = 1.0; for (i = 0; i < DEPTH && i < rl->results; i++) { int j; double score = 0.0; if (rl->list[i].rel) for (j = 0; j < rl->subtopics; j++) if (rl->list[i].rel[j]) { score += subtopicGain[j]; subtopicGain[j] *= (1.0 - alpha); } rl->dcg[i] = score*discount(i); } for (i = 0; i < DEPTH; i++) { idealIdeal[i] = idealIdealGain*discount(i); idealIdealGain *= (1.0 - alpha); } for (i = 1; i < DEPTH; i++) { /* cumulative gain */ rl->dcg[i] += rl->dcg[i-1]; idealIdeal[i] += idealIdeal[i - 1]; } /* simple normalization ("ideal ideal normalization") */ for (i = 1; i < DEPTH; i++) rl->dcg[i] /= idealIdeal[i]; } /* computeSTRecall compute subtopic recall for a result list; assumes all results are labeled with relevance judgments */ static void computeSTRecall (struct rList *rl) { int i, j, count = 0; int *subtopicSeen = (int *) alloca (rl->subtopics*sizeof(int)); if (rl->actualSubtopics == 0) return; for (j = 0; j < rl->subtopics; j++) subtopicSeen[j] = 0; for (i = 0; i < DEPTH && i < rl->results; i++) { if (rl->list[i].rel) for (j = 0; j < rl->subtopics; j++) if (subtopicSeen[j] == 0 && rl->list[i].rel[j]) { count++; subtopicSeen[j] = 1; } rl->strec[i] = ((double) count/ (double) rl->actualSubtopics); } for (; i < DEPTH; i++) rl->strec[i] = ((double) count/ (double) rl->actualSubtopics); } /* computePrecision: compute intent aware precision for a result list; assumes all results are labeled with relevance judgments */ static void computePrecision (struct rList *rl) { int i, count = 0; if (rl->actualSubtopics == 0) return; for (i = 0; i < DEPTH && i < rl->results; i++) { if (rl->list[i].rel) { int j; for (j = 0; j < rl->subtopics; j++) if (rl->list[i].rel[j]) count++; } rl->precision[i] = ((double) count)/((i + 1)*rl->actualSubtopics); } for (; i < DEPTH; i++) rl->precision[i] = ((double) count)/((i + 1)*rl->actualSubtopics); } /* qrelPopulateResultList: populate an ideal result list from the qrels; also used to label the run with relevance judgments */ static void qrelPopulateResultList (struct qrel *q, int n, struct rList *rl, int topics) { int i, j, k, currentTopic; char *currentDocno = ""; j = currentTopic = -1; for (i = 0; i < n; i++) { if (q[i].topic != currentTopic) { j++; currentTopic = q[i].topic; currentDocno = ""; rl[j].topic = currentTopic; rl[j].subtopics = rl[j].results = 0; rl[j].nrel = 0; rl[j].mapIA = rl[j].map = 0.0; rl[j].nrbp = rl[j].nnrbp = 0.0; for (k = 0; k < DEPTH; k++) rl[j].dcg[k] = rl[j].ndcg[k] = rl[j].err[k] = rl[j].nerr[k] = rl[j].precision[k] = rl[j].strec[k] = 0.0; } if (rl[j].subtopics <= q[i].subtopic) rl[j].subtopics = q[i].subtopic + 1; if (strcmp (q[i].docno, currentDocno) != 0) { currentDocno = q[i].docno; rl[j].results++; } } for (i = 0; i < topics; i++) { rl[i].list = (struct result *) localMalloc (rl[i].results*sizeof (struct result)); rl[i].nrelSub = (int *) localMalloc (rl[i].subtopics*sizeof (int)); for (j = 0; j < rl[i].subtopics; j++) rl[i].nrelSub[j] = 0; for (j = 0; j < rl[i].results; j++) { rl[i].list[j].topic = rl[i].topic; rl[i].list[j].rel = (int *) localMalloc (rl[i].subtopics*sizeof (int)); for (k = 0; k < rl[i].subtopics; k++) rl[i].list[j].rel[k] = 0; } } j = k = currentTopic = -1; currentDocno = ""; for (i = 0; i < n; i++) { if (q[i].topic != currentTopic) { j++; currentTopic = q[i].topic; k = -1; currentDocno = ""; } if (strcmp (q[i].docno, currentDocno) != 0) { currentDocno = q[i].docno; k++; rl[j].list[k].docno = localStrdup (currentDocno); } rl[j].list[k].rel[q[i].subtopic] = q[i].judgment; rl[j].nrelSub[q[i].subtopic] += q[i].judgment; } for (i = 0; i < topics; i++) { nrel(rl + i); actualSubtopics (rl + i); idealResult (rl + i); resultSortByRank (rl[i].list, rl[i].results); computeDCG (rl + i); computeNRBP(rl + i); computeERR (rl + i); resultSortByDocno (rl[i].list, rl[i].results); } } /* qrelToRList: construct an ideal result list from the qrels */ static struct rList * qrelToRList (struct qrel *q, int n, int *topics) { struct rList *rl; *topics = qrelCountTopics (q, n); rl = (struct rList *) localMalloc ((*topics)*sizeof (struct rList)); qrelPopulateResultList (q, n, rl, *topics); return rl; } /* qrelToRList: process the qrels file, contructing an ideal result list */ static struct rList * processQrels (char *fileName, int *topics) { FILE *fp; char *line; struct qrel *q; int i = 0, n = 0; if ((fp = fopen (fileName, "r")) == NULL) error ("cannot open qrel file \"%s\"\n", fileName); while (getline(fp)) n++; fclose (fp); if (n == 0) error ("qrel file \"%s\" is empty\n", fileName); q = localMalloc (n*sizeof (struct qrel)); if ((fp = fopen (fileName, "r")) == NULL) error ("cannot open qrel file \"%s\"\n", fileName); while ((line = getline (fp))) { char *a[4]; int topic, subtopic, judgment; if ( split (line, a, 4) != 4 || (topic = naturalNumber (a[0])) < 0 || (subtopic = naturalNumber (a[1])) < 0 || (judgment = naturalNumber (a[3])) < 0 ) error ( "syntax error in qrel file \"%s\" at line %d\n", fileName, i + 1 ); else { q[i].topic = topic; q[i].subtopic = subtopic; if (judgment > 1) judgment = 1; /* binary assessment only */ q[i].judgment = judgment; q[i].docno = localStrdup (a[2]); i++; } } fclose (fp); qrelSort (q, n); return qrelToRList (q, n, topics); } /* resultCountTopics: count the number of distinct topics in a run; assumes results are sorted */ static int resultCountTopics (struct result *r, int n) { int i, topics = 1, currentTopic = r[0].topic; for (i = 1; i < n; i++) if (r[i].topic != currentTopic) { topics++; currentTopic = r[i].topic; } return topics; } /* populateResultList: populate a result list from a run */ static void populateResultList (struct result *r, int n, struct rList *rl, int topics) { int i, j, k, currentTopic = -1; j = 0; for (i = 0; i < n; i++) if (r[i].topic != currentTopic) { currentTopic = r[i].topic; rl[j].list = r + i; rl[j].topic = currentTopic; rl[j].subtopics = 0; rl[j].actualSubtopics = 0; if (j > 0) rl[j-1].results = rl[j].list - rl[j-1].list; rl[j].nrel = 0; rl[j].mapIA = rl[j].map = 0.0; rl[j].nrbp = rl[j].nnrbp = 0.0; for (k = 0; k < DEPTH; k++) rl[j].dcg[k] = rl[j].ndcg[k] = rl[j].err[k] = rl[j].nerr[k] = rl[j].precision[k] = rl[j].strec[k] = 0.0; j++; } if (j > 0) rl[j-1].results = (r + n) - rl[j-1].list; } /* forceTraditionalRanks: Re-assign ranks so that runs are sorted by score and then by docno, which is the traditional sort order for TREC runs. */ static void forceTraditionalRanks (struct result *r, int n) { int i, rank, currentTopic = -1; resultSortByScore (r, n); for (i = 0; i < n; i++) { if (r[i].topic != currentTopic) { currentTopic = r[i].topic; rank = 1; } r[i].rank = rank; rank++; } } /* applyCutoff: Throw away results deeper than a specified depth. Run must be sorted by topic and then rank. Return number of remaing results. */ static int applyCutoff (struct result *r, int n, int depthMax) { int i, j, depth, currentTopic = -1; j = 0; for (i = 0; i < n; i++) { if (r[i].topic != currentTopic) { currentTopic = r[i].topic; depth = 1; } else depth++; if (depth <= depthMax) r[j++] = r[i]; } return j; } /* processRun: process a run file, returning a result list */ static struct rList * processRun (char *fileName, int *topics, char **runid) { FILE *fp; char *line; int i = 0, n = 0; int needRunid = 1; struct result *r; struct rList *rl; if ((fp = fopen (fileName, "r")) == NULL) error ("cannot open run file \"%s\"n", fileName); while (getline(fp)) n++; fclose (fp); if (n == 0) error ("run file \"%s\" is empty\n", fileName); r = localMalloc (n*sizeof (struct result)); if ((fp = fopen (fileName, "r")) == NULL) error ("cannot open run file \"%s\"\n", fileName); while ((line = getline (fp))) { char *a[6]; int topic, rank; if ( split (line, a, 6) != 6 || (topic = parseTopic (a[0])) < 0 || (rank = naturalNumber (a[3])) < 0 ) error ("syntax error in run file \"%s\" at line %d\n", fileName, i + 1); else { if (needRunid) { *runid = localStrdup (a[5]); needRunid = 0; } r[i].docno = localStrdup (a[2]); r[i].topic = topic; r[i].rank = rank; r[i].rel = (int *) 0; sscanf (a[4],"%lf", &(r[i].score)); i++; } } /* force ranks to be consistent with traditional TREC sort order */ if (traditional) forceTraditionalRanks (r, n); /* for each topic, verify that ranks have not been duplicated */ resultSortByRank (r, n); for (i = 1; i < n; i++) if (r[i].topic == r[i-1].topic && r[i].rank == r[i-1].rank) error ( "duplicate rank (%d) for topic %d in run file \"%s\"\n", r[i].rank, r[i].topic, fileName ); /* apply depth cutoff if specified on the command line */ if (depthM > 0) n = applyCutoff (r, n, depthM); /* for each topic, verify that docnos have not been duplicated */ resultSortByDocno (r, n); for (i = 1; i < n; i++) if (r[i].topic == r[i-1].topic && strcmp(r[i].docno,r[i-1].docno) == 0) error ( "duplicate docno (%s) for topic %d in run file \"%s\"\n", r[i].docno, r[i].topic, fileName ); /* split results by topic */ *topics = resultCountTopics (r, n); rl = (struct rList *) localMalloc ((*topics)*sizeof (struct rList)); populateResultList (r, n, rl, *topics); return rl; } /* applyJudgments: copy relevance judgments from qrel results to run results; assumes results are sorted by docno */ static void applyJudgments (struct result *q, int qResults, struct result *r, int rResults) { int i = 0, j = 0; while (i < qResults && j < rResults) { int cmp = strcmp (q[i].docno, r[j].docno); if (cmp < 0) i++; else if (cmp > 0) j++; else { r[j].rel = q[i].rel; i++; j++; } } } /* renormalize: normalize a result list against an ideal result list (created from qrels) */ static void renormalize (struct rList *ql, struct rList *rl) { int i; for (i = 0; i < DEPTH; i++) if (rl->dcg[i]) { rl->ndcg[i] = rl->dcg[i]/ql->dcg[i]; rl->nerr[i] = rl->err[i]/ql->err[i]; } rl->nnrbp = rl->nrbp/ql->nrbp; } /* applyQrels: transfer relevance judgments from qrels to a run */ static int applyQrels (struct rList *qrl, int qTopics, struct rList *rrl, int rTopics) { int actualTopics = 0, i = 0, j = 0; while (i < qTopics && j < rTopics) if (qrl[i].topic < rrl[j].topic) i++; else if (qrl[i].topic > rrl[j].topic) j++; else { rrl[j].subtopics = qrl[i].subtopics; rrl[j].actualSubtopics = qrl[i].actualSubtopics; rrl[j].nrel = qrl[i].nrel; rrl[j].nrelSub = qrl[i].nrelSub; applyJudgments ( qrl[i].list, qrl[i].results, rrl[j].list, rrl[j].results ); resultSortByRank (rrl[j].list, rrl[j].results); computeDCG (rrl + j); computeNRBP (rrl + j); computeERR (rrl + j); renormalize (qrl + i, rrl + j); computeSTRecall (rrl + j); computePrecision (rrl + j); computeMAP (rrl + j); i++; j++; actualTopics++; } return actualTopics; } /* outputMeasures: output evaluation measures as a CSV file (ugly, ugly, ugly) */ static void outputMeasures ( struct rList *rl, int topics, int actualTopics, char *runid, int all ) { int i; double totalERR5 = 0.0, totalERR10 = 0.0, totalERR20 = 0.0; double totalnERR5 = 0.0, totalnERR10 = 0.0, totalnERR20 = 0.0; double totalDCG5 = 0.0, totalDCG10 = 0.0, totalDCG20 = 0.0; double totalnDCG5 = 0.0, totalnDCG10 = 0.0, totalnDCG20 = 0.0; double totalNRBP = 0.0, totalnNRBP = 0.0; double totalMAPIA = 0.0; double totalP5 = 0.0, totalP10 = 0.0, totalP20 = 0.0; double totalSTRec5 = 0.0, totalSTRec10 = 0.0, totalSTRec20 = 0.0; printf ("runid,topic"); printf (",ERR-IA@5,ERR-IA@10,ERR-IA@20"); printf (",nERR-IA@5,nERR-IA@10,nERR-IA@20"); printf (",alpha-DCG@5,alpha-DCG@10,alpha-DCG@20"); printf (",alpha-nDCG@5,alpha-nDCG@10,alpha-nDCG@20"); printf (",NRBP,nNRBP"); printf (",MAP-IA"); printf (",P-IA@5,P-IA@10,P-IA@20"); printf (",strec@5,strec@10,strec@20"); printf ("\n"); if (actualTopics == 0) { printf ("%s,amean", runid); printf (",0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00"); printf (",0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00,0.00"); printf ("\n"); return; } for (i = 0; i < topics; i++) { printf ( "%s,%d" ",%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f" ",%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f\n", runid, rl[i].topic, rl[i].err[4], rl[i].err[9], rl[i].err[19], rl[i].nerr[4], rl[i].nerr[9], rl[i].nerr[19], rl[i].dcg[4], rl[i].dcg[9], rl[i].dcg[19], rl[i].ndcg[4], rl[i].ndcg[9], rl[i].ndcg[19], rl[i].nrbp, rl[i].nnrbp, rl[i].mapIA, rl[i].precision[4], rl[i].precision[9], rl[i].precision[19], rl[i].strec[4], rl[i].strec[9], rl[i].strec[19] ); totalERR5 += rl[i].err[4]; totalERR10 += rl[i].err[9]; totalERR20 += rl[i].err[19]; totalnERR5 += rl[i].nerr[4]; totalnERR10 += rl[i].nerr[9]; totalnERR20 += rl[i].nerr[19]; totalDCG5 += rl[i].dcg[4]; totalDCG10 += rl[i].dcg[9]; totalDCG20 += rl[i].dcg[19]; totalnDCG5 += rl[i].ndcg[4]; totalnDCG10 += rl[i].ndcg[9]; totalnDCG20 += rl[i].ndcg[19]; totalNRBP += rl[i].nrbp; totalnNRBP += rl[i].nnrbp; totalMAPIA += rl[i].mapIA; totalP5 += rl[i].precision[4]; totalP10 += rl[i].precision[9]; totalP20 += rl[i].precision[19]; totalSTRec5 += rl[i].strec[4]; totalSTRec10 += rl[i].strec[9]; totalSTRec20 += rl[i].strec[19]; } printf ( "%s,amean" ",%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f" ",%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f,%.6f\n", runid, totalERR5/actualTopics, totalERR10/actualTopics, totalERR20/actualTopics, totalnERR5/actualTopics, totalnERR10/actualTopics, totalnERR20/actualTopics, totalDCG5/actualTopics, totalDCG10/actualTopics, totalDCG20/actualTopics, totalnDCG5/actualTopics, totalnDCG10/actualTopics, totalnDCG20/actualTopics, totalNRBP/actualTopics, totalnNRBP/actualTopics, totalMAPIA/actualTopics, totalP5/actualTopics, totalP10/actualTopics, totalP20/actualTopics, totalSTRec5/actualTopics,totalSTRec10/actualTopics,totalSTRec20/actualTopics ); } static void usage () { error (usageText, programName); } int main (int argc, char **argv) { char *runid; int qTopics, rTopics, actualTopics; struct rList *qrl, *rrl; int cFlag = 0; /* average over complete set of queries */ int aFlag = 0; /* report all measures */ setProgramName (argv[0]); while (argc != 3) if (argc >= 2 && strcmp ("-version", argv[1]) == 0) { printf ("%s: %s\n", programName, version); exit (0); } else if (argc >= 2 && strcmp ("-help", argv[1]) == 0) { printf (helpText); exit (0); } else if (argc >= 5 && strcmp ("-alpha", argv[1]) == 0) { sscanf (argv[2], "%lf", &alpha); if (alpha < 0.0 || alpha > 1.0) usage(); argc -= 2; argv += 2; } else if (argc >= 5 && strcmp ("-beta", argv[1]) == 0) { sscanf (argv[2], "%lf", &beta); if (beta < 0.0 || beta > 1.0) usage(); argc -= 2; argv += 2; } else if (argc >= 5 && strcmp ("-M", argv[1]) == 0) { sscanf (argv[2], "%d", &depthM); if (depthM <= 0) usage(); argc -= 2; argv += 2; } else if (argc >= 4 && strcmp ("-traditional", argv[1]) == 0) { traditional = 1; --argc; argv++; } else if (argc >= 4 && argv[1][0] == '-') { int i; for (i = 1; argv[1][i]; i++) switch (argv[1][i]) { case 'c': cFlag = 1; break; case 'a': aFlag = 1; break; default: usage(); } --argc; argv++; } else usage(); qrl = processQrels (argv[1], &qTopics); rrl = processRun (argv[2], &rTopics, &runid); actualTopics = applyQrels (qrl, qTopics, rrl, rTopics); if (cFlag) actualTopics = qTopics; outputMeasures (rrl, rTopics, actualTopics, runid, aFlag); return 0; }