Similarity defines the components of Lucene scoring. * Overriding computation of these components is a convenient * way to alter Lucene scoring. * *
Suggested reading: * * Introduction To Information Retrieval, Chapter 6. * *
The following describes how Lucene scoring evolves from * underlying information retrieval models to (efficient) implementation. * We first brief on VSM Score, * then derive from it Lucene's Conceptual Scoring Formula, * from which, finally, evolves Lucene's Practical Scoring Function * (the latter is connected directly with Lucene classes and methods). * *
Lucene combines * * Boolean model (BM) of Information Retrieval * with * * Vector Space Model (VSM) of Information Retrieval - * documents "approved" by BM are scored by VSM. * *
In VSM, documents and queries are represented as * weighted vectors in a multi-dimensional space, * where each distinct index term is a dimension, * and weights are * Tf-idf values. * *
VSM does not require weights to be Tf-idf values, * but Tf-idf values are believed to produce search results of high quality, * and so Lucene is using Tf-idf. * Tf and Idf are described in more detail below, * but for now, for completion, let's just say that * for given term t and document (or query) x, * Tf(t,x) varies with the number of occurrences of term t in x * (when one increases so does the other) and * idf(t) similarly varies with the inverse of the * number of index documents containing term t. * *
VSM score of document d for query q is the
*
* Cosine Similarity
* of the weighted query vectors V(q) and V(d):
*
*
*
*
| ||||||
|
* |
Note: the above equation can be viewed as the dot product of * the normalized weighted vectors, in the sense that dividing * V(q) by its euclidean norm is normalizing it to a unit vector. * *
Lucene refines VSM score for both search quality and usability: *
Under the simplifying assumption of a single field in the index,
* we get Lucene's Conceptual scoring formula:
*
*
*
*
| |||||||
|
* |
The conceptual formula is a simplification in the sense that (1) terms and documents * are fielded and (2) boosts are usually per query term rather than per query. * *
We now describe how Lucene implements this conceptual scoring formula, and * derive from it Lucene's Practical Scoring Function. * *
For efficient score computation some scoring components * are computed and aggregated in advance: * *
Lucene's Practical Scoring Function is derived from the above. * The color codes demonstrate how it relates * to those of the conceptual formula: * *
*
*
| |||||||
|
* |
where *
| * {@link org.apache.lucene.search.DefaultSimilarity#tf(float) tf(t in d)} = * | ** frequency½ * | *
| * {@link org.apache.lucene.search.DefaultSimilarity#idf(int, int) idf(t)} = * | ** 1 + log ( * | *
*
|
* * ) * | *
| * queryNorm(q) = * {@link org.apache.lucene.search.DefaultSimilarity#queryNorm(float) queryNorm(sumOfSquaredWeights)} * = * | *
*
|
*
| * {@link org.apache.lucene.search.Weight#sumOfSquaredWeights() sumOfSquaredWeights} = * {@link org.apache.lucene.search.Query#getBoost() q.getBoost()} 2 * · * | ** ∑ * | ** ( * idf(t) · * t.getBoost() * ) 2 * | *
| * | t in q | ** |
* When a document is added to the index, all the above factors are multiplied.
* If the document has multiple fields with the same name, all their boosts are multiplied together:
*
*
*
| * norm(t,d) = * {@link org.apache.lucene.document.Document#getBoost() doc.getBoost()} * · * {@link #lengthNorm(String, int) lengthNorm(field)} * · * | ** ∏ * | ** {@link org.apache.lucene.document.Fieldable#getBoost() f.getBoost}() * | *
| * | field f in d named as t | ** |
This is initially an instance of {@link DefaultSimilarity}. * * @see Searcher#setSimilarity(Similarity) * @see org.apache.lucene.index.IndexWriter#setSimilarity(Similarity) */ public static Similarity getDefault() { return Similarity.defaultImpl; } /** Cache of decoded bytes. */ private static final float[] NORM_TABLE = new float[256]; static { for (int i = 0; i < 256; i++) NORM_TABLE[i] = SmallFloat.byte315ToFloat((byte)i); } /** * Decodes a normalization factor stored in an index. * @see #decodeNormValue(byte) * @deprecated Use {@link #decodeNormValue} instead. */ @Deprecated public static float decodeNorm(byte b) { return NORM_TABLE[b & 0xFF]; // & 0xFF maps negative bytes to positive above 127 } /** Decodes a normalization factor stored in an index. * @see #encodeNormValue(float) */ public float decodeNormValue(byte b) { return NORM_TABLE[b & 0xFF]; // & 0xFF maps negative bytes to positive above 127 } /** Returns a table for decoding normalization bytes. * @see #encodeNormValue(float) * @see #decodeNormValue(byte) * * @deprecated Use instance methods for encoding/decoding norm values to enable customization. */ @Deprecated public static float[] getNormDecoder() { return NORM_TABLE; } /** * Compute the normalization value for a field, given the accumulated * state of term processing for this field (see {@link FieldInvertState}). * *
Implementations should calculate a float value based on the field * state and then return that value. * *
For backward compatibility this method by default calls * {@link #lengthNorm(String, int)} passing * {@link FieldInvertState#getLength()} as the second argument, and * then multiplies this value by {@link FieldInvertState#getBoost()}.
* *WARNING: This API is new and experimental and may * suddenly change.
* * @param field field name * @param state current processing state for this field * @return the calculated float norm */ public float computeNorm(String field, FieldInvertState state) { return (float) (state.getBoost() * lengthNorm(field, state.getLength())); } /** Computes the normalization value for a field given the total number of * terms contained in a field. These values, together with field boosts, are * stored in an index and multipled into scores for hits on each field by the * search code. * *Matches in longer fields are less precise, so implementations of this
* method usually return smaller values when numTokens is large,
* and larger values when numTokens is small.
*
*
Note that the return values are computed under * {@link org.apache.lucene.index.IndexWriter#addDocument(org.apache.lucene.document.Document)} * and then stored using * {@link #encodeNormValue(float)}. * Thus they have limited precision, and documents * must be re-indexed if this method is altered. * * @param fieldName the name of the field * @param numTokens the total number of tokens contained in fields named * fieldName of doc. * @return a normalization factor for hits on this field of this document * * @see org.apache.lucene.document.Field#setBoost(float) */ public abstract float lengthNorm(String fieldName, int numTokens); /** Computes the normalization value for a query given the sum of the squared * weights of each of the query terms. This value is multiplied into the * weight of each query term. While the classic query normalization factor is * computed as 1/sqrt(sumOfSquaredWeights), other implementations might * completely ignore sumOfSquaredWeights (ie return 1). * *
This does not affect ranking, but the default implementation does make scores * from different queries more comparable than they would be by eliminating the * magnitude of the Query vector as a factor in the score. * * @param sumOfSquaredWeights the sum of the squares of query term weights * @return a normalization factor for query weights */ public abstract float queryNorm(float sumOfSquaredWeights); /** Encodes a normalization factor for storage in an index. * *
The encoding uses a three-bit mantissa, a five-bit exponent, and * the zero-exponent point at 15, thus * representing values from around 7x10^9 to 2x10^-9 with about one * significant decimal digit of accuracy. Zero is also represented. * Negative numbers are rounded up to zero. Values too large to represent * are rounded down to the largest representable value. Positive values too * small to represent are rounded up to the smallest positive representable * value. * * @see org.apache.lucene.document.Field#setBoost(float) * @see org.apache.lucene.util.SmallFloat */ public byte encodeNormValue(float f) { return SmallFloat.floatToByte315(f); } /** * Static accessor kept for backwards compability reason, use encodeNormValue instead. * @param f norm-value to encode * @return byte representing the given float * @deprecated Use {@link #encodeNormValue} instead. * * @see #encodeNormValue(float) */ @Deprecated public static byte encodeNorm(float f) { return SmallFloat.floatToByte315(f); } /** Computes a score factor based on a term or phrase's frequency in a * document. This value is multiplied by the {@link #idf(int, int)} * factor for each term in the query and these products are then summed to * form the initial score for a document. * *
Terms and phrases repeated in a document indicate the topic of the
* document, so implementations of this method usually return larger values
* when freq is large, and smaller values when freq
* is small.
*
*
The default implementation calls {@link #tf(float)}. * * @param freq the frequency of a term within a document * @return a score factor based on a term's within-document frequency */ public float tf(int freq) { return tf((float)freq); } /** Computes the amount of a sloppy phrase match, based on an edit distance. * This value is summed for each sloppy phrase match in a document to form * the frequency that is passed to {@link #tf(float)}. * *
A phrase match with a small edit distance to a document passage more * closely matches the document, so implementations of this method usually * return larger values when the edit distance is small and smaller values * when it is large. * * @see PhraseQuery#setSlop(int) * @param distance the edit distance of this sloppy phrase match * @return the frequency increment for this match */ public abstract float sloppyFreq(int distance); /** Computes a score factor based on a term or phrase's frequency in a * document. This value is multiplied by the {@link #idf(int, int)} * factor for each term in the query and these products are then summed to * form the initial score for a document. * *
Terms and phrases repeated in a document indicate the topic of the
* document, so implementations of this method usually return larger values
* when freq is large, and smaller values when freq
* is small.
*
* @param freq the frequency of a term within a document
* @return a score factor based on a term's within-document frequency
*/
public abstract float tf(float freq);
/**
* Computes a score factor for a simple term and returns an explanation
* for that score factor.
*
*
* The default implementation uses: * *
* idf(searcher.docFreq(term), searcher.maxDoc()); ** * Note that {@link Searcher#maxDoc()} is used instead of * {@link org.apache.lucene.index.IndexReader#numDocs() IndexReader#numDocs()} because also * {@link Searcher#docFreq(Term)} is used, and when the latter * is inaccurate, so is {@link Searcher#maxDoc()}, and in the same direction. * In addition, {@link Searcher#maxDoc()} is more efficient to compute * * @param term the term in question * @param searcher the document collection being searched * @return an IDFExplain object that includes both an idf score factor and an explanation for the term. * @throws IOException */ public IDFExplanation idfExplain(final Term term, final Searcher searcher) throws IOException { final int df = searcher.docFreq(term); final int max = searcher.maxDoc(); final float idf = idf(df, max); return new IDFExplanation() { @Override public String explain() { return "idf(docFreq=" + df + ", maxDocs=" + max + ")"; } @Override public float getIdf() { return idf; }}; } /** * Computes a score factor for a phrase. * *
* The default implementation sums the idf factor for
* each term in the phrase.
*
* @param terms the terms in the phrase
* @param searcher the document collection being searched
* @return an IDFExplain object that includes both an idf
* score factor for the phrase and an explanation
* for each term.
* @throws IOException
*/
public IDFExplanation idfExplain(Collection Terms that occur in fewer documents are better indicators of topic, so
* implementations of this method usually return larger values for rare terms,
* and smaller values for common terms.
*
* @param docFreq the number of documents which contain the term
* @param numDocs the total number of documents in the collection
* @return a score factor based on the term's document frequency
*/
public abstract float idf(int docFreq, int numDocs);
/** Computes a score factor based on the fraction of all query terms that a
* document contains. This value is multiplied into scores.
*
* The presence of a large portion of the query terms indicates a better
* match with the query, so implementations of this method usually return
* larger values when the ratio between these parameters is large and smaller
* values when the ratio between them is small.
*
* @param overlap the number of query terms matched in the document
* @param maxOverlap the total number of terms in the query
* @return a score factor based on term overlap with the query
*/
public abstract float coord(int overlap, int maxOverlap);
/**
* Calculate a scoring factor based on the data in the payload. Overriding implementations
* are responsible for interpreting what is in the payload. Lucene makes no assumptions about
* what is in the byte array.
*
* The default implementation returns 1.
*
* @param docId The docId currently being scored. If this value is {@link #NO_DOC_ID_PROVIDED}, then it should be assumed that the PayloadQuery implementation does not provide document information
* @param fieldName The fieldName of the term this payload belongs to
* @param start The start position of the payload
* @param end The end position of the payload
* @param payload The payload byte array to be scored
* @param offset The offset into the payload array
* @param length The length in the array
* @return An implementation dependent float to be used as a scoring factor
*
*/
public float scorePayload(int docId, String fieldName, int start, int end, byte [] payload, int offset, int length)
{
return 1;
}
}