Package it.unimi.di.big.mg4j.search.score

Class BM25Scorer

  • All Implemented Interfaces:
    DelegatingScorer, Scorer, FlyweightPrototype<Scorer>
    public class BM25Scorer
extends AbstractWeightedScorer
implements DelegatingScorer
    A scorer that implements the BM25 ranking scheme.

    BM25 is the name of a ranking scheme for text derived from the probabilistic model. The essential feature of the scheme is that of assigning to each term appearing in a given document a weight depending both on the count (the number of occurrences of the term in the document), on the frequency (the number of the documents in which the term appears) and on the document length (in words). It was devised in the early nineties, and it provides a significant improvement over the classical TF/IDF scheme. Karen Spärck Jones, Steve Walker and Stephen E. Robertson give a full account of BM25 and of the probabilistic model in “A probabilistic model of information retrieval: development and comparative experiments”, Inf. Process. Management 36(6):779−840, 2000.

    There are a number of incarnations with small variations of the formula itself. Here, the weight assigned to a term which appears in f documents out of a collection of N documents w.r.t. to a document of length l in which the term appears c times is

    log( (N − f + 1/2) / (f + 1/2) ) ( k1 + 1 ) c  ⁄  ( c + k1 ((1 − b) + bl / L) ),
    where L is the average document length, and k1 and b are parameters that default to DEFAULT_K1 and DEFAULT_B: these values were chosen following the suggestions given in “Efficiency vs. effectiveness in Terabyte-scale information retrieval”, by Stefan Büttcher and Charles L. A. Clarke, in Proceedings of the 14th Text REtrieval Conference (TREC 2005). Gaithersburg, USA, November 2005. The logarithmic part (a.k.a. idf (inverse document-frequency) part) is actually maximised with EPSILON_SCORE, so it is never negative (the net effect being that terms appearing in more than half of the documents have almost no weight).

    Evaluation

    This class has two modes of evaluation, generic and flat. The generic evaluator uses an internal visitor building on CounterSetupVisitor and related classes (by means of DocumentIterator.acceptOnTruePaths(it.unimi.di.big.mg4j.search.visitor.DocumentIteratorVisitor)) to take into consideration only terms that are actually involved in query semantics for the current document. The flat evaluator simulates the behaviour of the generic evaluator on a special subset of queries, that is, queries that are formed by an index iterator or a composite document iterator whose underlying queries are all index iterators, by means of a simple loop. This is significantly faster than the generic evaluator (as there is no recursive visit) either if document iterator is a subclass of AbstractIntersectionDocumentIterator, or if it is a subclass of AbstractUnionDocumentIterator and the disjuncts are not too many (less than MAX_FLAT_DISJUNCTS).

    Author:
    Mauro Mereu, Sebastiano Vigna

    • Field Detail

      • LOGGER

        public static final Logger LOGGER

      • DEFAULT_K1

        public static final double DEFAULT_K1
        The default value used for the parameter k1.
        See Also:
        Constant Field Values

      • DEFAULT_B

        public static final double DEFAULT_B
        The default value used for the parameter b.
        See Also:
        Constant Field Values

      • EPSILON_SCORE

        public static final double EPSILON_SCORE
        The value of the document-frequency part for terms appearing in more than half of the documents.
        See Also:
        Constant Field Values

      • MAX_FLAT_DISJUNCTS

        public static final int MAX_FLAT_DISJUNCTS
        Disjunctive queries on index iterators are handled using the flat evaluator only if they contain less than this number of disjuncts. The generic evaluator is more efficient if there are several disjuncts, as it invokes IndexIterator.count() only on the terms that are part of the front. This value is largely architecture, query, term-distribution, and whatever else dependent.
        See Also:
        Constant Field Values

    • Constructor Detail

      • BM25Scorer

        public BM25Scorer()
        Creates a BM25 scorer using DEFAULT_K1 and DEFAULT_B as parameters.

      • BM25Scorer

        public BM25Scorer​(double k1,
                  double b)
        Creates a BM25 scorer using specified k1 and b parameters.
        Parameters:
        k1 - the k1 parameter.
        b - the b parameter.

      • BM25Scorer

        public BM25Scorer​(String k1,
                  String b)
        Creates a BM25 scorer using specified k1 and b parameters specified by strings.
        Parameters:
        k1 - the k1 parameter.
        b - the b parameter.