Статьи

Создайте свой собственный Lucene Query and Scorer

Июль 26, 2018

Время от времени мы сталкиваемся с проблемой поиска, которая не может быть просто решена с простой релевантностью Solr. Обычно это означает, что клиент точно знает , как следует оценивать документы. У них может быть небольшая терпимость к близким приближениям этого скоринга с помощью повышений Solr, запросов функций и т. Д. Им нужна технология на основе Lucene для анализа текста и эффективных структур данных, но они должны быть очень специфичными в отношении того, как документы должны оцениваться относительно друг с другом.

Для этих крайне специализированных случаев мы можем назначить небольшую амбулаторную операцию для вашей установки Solr — создание собственного Lucene Query.

Это ядерный вариант

Прежде чем мы погрузимся, слово предостережения. Если вам не нужен только образовательный опыт, создание пользовательского запроса Lucene должно стать «ядерным вариантом» для релевантности поиска. Это очень неудобно, и есть много входов и выходов. Если вы действительно думаете об этом, чтобы решить реальную проблему, вы уже пошли по следующим путям:

  1. Вы использовали обширный набор синтаксических анализаторов и функций Solr, включая запросы функций, объединения и т. Д. Ничто из этого не решило вашу проблему
  2. Вы исчерпали экосистему плагинов, которые расширяют возможности (1). Это не сработало.
  3. Вы реализовали свой собственный плагин парсера запросов, который принимает пользовательский ввод и генерирует существующие запросы Lucene для выполнения этой работы. Это все еще не решило вашу проблему.
  4. Вы тщательно продумали свои анализаторы — массировали свои данные так, чтобы во время индексации и времени запроса текст выстраивался точно так, как это должно оптимизировать поведение существующего поискового скоринга. Это все еще не получил то, что вы хотели.
  5. Вы внедрили свою собственные схожести , который модифицирует как Lucene вычисляет традиционные статистические релевантности — нормы запроса, термин частота и т.д.
  6. Вы пытались использовать CustomScoreQuery от Lucene, чтобы обернуть существующий запрос и изменить оценку каждого документа с помощью обратного вызова. Это все еще не было достаточно низким уровнем для вас, вам нужно было еще больше контроля.

Если вы все еще читаете, вы либо думаете, что это будет весело / познавательно (полезно для вас!), Либо вы один из тех меньшинств, которые должны точно контролировать то, что происходит с поиском. Если вы не знаете, вы можете связаться с нами для получения профессиональных услуг.

Хорошо, вернемся к действию …

Переподготовка — Lucene Searching 101

Напомним, что для поиска в Lucene нам нужно получить IndexSearcher. Этот IndexSearcher выполняет поиск по IndexReader. Предполагая, что мы создали индекс, с этими классами мы можем выполнить поиск как в этом коде:

Directory dir = new RAMDirectory(); 
IndexReader idxReader = new IndexReader(dir);
idxSearcher idxSearcher = new IndexSearcher(idxReader)
Query q = new TermQuery(new Term(“field”, “value”));
idxSearcher.search(q);

Давайте подведем итоги объектов, которые мы создали:

  • Каталог — интерфейс Lucene к файловой системе. Это довольно просто. Мы не будем погружаться здесь.
  • IndexReader — доступ к структурам данных в инвертированном индексе Lucene. Если мы хотим найти термин и посетить каждый документ, в котором он существует, мы должны начать с него. Если бы мы хотели поиграть с векторами терминов, смещениями или чем-то еще, хранящимся в индексе, мы бы искали и этот материал.
  • IndexSearcher — упаковывает IndexReader с целью получения поисковых запросов и их выполнения.
  • Запрос — Как мы ожидаем, что поисковик будет выполнять поиск, включая оценку и какие документы возвращаются. В этом случае мы ищем «значение» в поле «поле». Это то, с чем мы хотим играть

В дополнение к этим классам отметим, что класс поддержки существует за кулисами:

  • Сходство — определяет правила / формулы для расчета норм во время индекса и нормализации запроса.

Теперь с этой схемой давайте подумаем о пользовательском запросе Lucene, который мы можем реализовать, чтобы помочь нам учиться. Как насчет запроса, который ищет термины в обратном направлении. Если документ соответствует термину в обратном направлении (например, ананаб для банана), мы вернем оценку 5,0. Если документ соответствует форвардной версии, давайте все равно вернем документ с оценкой 1,0 вместо. Мы назовем этот запрос «BackwardsTermQuery».

Этот пример размещен здесь на github .

Сказка о 3 классах — запрос, вес и бомбардир

Прежде чем мы перейдем к коду, давайте поговорим об общей архитектуре.

Запрос Lucene следует этой общей структуре:

  • Пользовательский класс Query, унаследованный от Query
  • Пользовательский весовой класс, наследуемый от веса
  • Пользовательский класс Scorer, наследуемый от Scorer

Эти три объекта обертывают друг друга. Запрос создает вес, а вес, в свою очередь, создает счетчик.

Запрос сам по себе очень простой класс. Одна из его основных обязанностей при передаче в IndexSearcher — создание экземпляра Weight. Помимо этого, перед Lucene и пользователями вашего запроса есть дополнительные обязанности, которые мы рассмотрим в разделе «Запрос» ниже.

Запрос создает Вес. Зачем? Lucene нужен способ отслеживать статистику уровня IndexSearcher, специфичную для каждого запроса, сохраняя при этом возможность повторного использования запроса для нескольких IndexSearchers. Это роль весовой категории. При выполнении поиска IndexSearcher просит Query создать экземпляр Weight. Этот экземпляр становится контейнером для хранения высокоуровневой статистики для запроса, относящегося к этому IndexSearcher (мы рассмотрим эти шаги подробнее в разделе «Вес» ниже). IndexSearcher безопасно владеет Весом и может злоупотреблять им и распоряжаться им по мере необходимости. Если впоследствии запрос повторно используется другим IndexSearcher, просто создается новый вес.

Once an IndexSearcher has a Weight, and has calculated any IndexSearcher level statistics, the IndexSearcher’s next task is to find matching documents and score them. To do this, the Weight in turn creates a Scorer. Just as the Weight is tied closely to an IndexSearcher, a Scorer is tied to an individual IndexReader. Now this may seem a little odd – in our code above the IndexSearcher always has exactly one IndexReader right? Not quite. See, a little hidden implementation detail is that IndexReaders may actually wrap other smaller IndexReaders – each tied to a different segment of the index. Therefore, an IndexSearcher needs to have the ability score documents across multiple, independent IndexReaders. How your scorer should iterate over matches and score documents is outlined in the “Scorer” section below.

So to summarize, we can expand the last line from our example above…

idxSearcher.search(q);

… into this psuedocode:

Weight w = q.createWeight(idxSearcher);
// IndexSearcher level calculations for weight
Foreach IndexReader idxReader:
    Scorer s = w.scorer(idxReader);
    // collect matches and score them

Now that we have the basic flow down, let’s pick apart the three classes in a little more detail for our custom implementation.

Our Custom Query

What should our custom Query implementation look like? Query implementations always have two audiences: (1) Lucene and (2) users of your Query implementation. For your users, expose whatever methods you require to modify how a searcher matches and scores with your query. Want to only return as a match 1/3 of the documents that match the query? Want to punish the score because the document length is longer than the query length? Add the appropriate modifier on the query that impacts the scorer’s behavior.

For our BackwardsTermQuery, we don’t expose accessors to modify the behavior of the search. The user simply uses the constructor to specify the term and field to search. In our constructor, we will simply be reusing Lucene’s existing TermQuery for searching individual terms in a document.

private TermQuery backwardsQuery;
private TermQuery forwardsQuery;

public BackwardsTermQuery(String field, String term) {
    // A wrapped TermQuery for the reverse string
    Term backwardsTerm = new Term(field, new StringBuilder(term).reverse().toString());
    backwardsQuery = new TermQuery(backwardsTerm);
    // A wrapped TermQuery for the Forward
    Term forwardsTerm = new Term(field, term);
    forwardsQuery = new TermQuery(forwardsTerm);
}

Just as importantly, be sure your Query meets the expectation of Lucene. Most importantly, you MUST override the following.

  • createWeight()
  • hashCode()
  • equals()

The method createWeight() we’ve discussed. This is where you’ll create a weight instance for an IndexSearcher. Pass any parameters that will influence the scoring algorithm, as the Weight will in turn be creating a searcher.

Even though they are not abstract methods, overriding the hashCode()/equals() methods is very important. These methods are used by Lucene/Solr to cache queries/results. If two queries are equal, there’s no reason to rerun the query. Running another instance of your query could result in seeing the results of your first query multiple times. You’ll see your search for “peas” work great, then you’ll search for “bananas” and see “peas” search results. Override equals() and hashCode() so that “peas” != bananas.

Our BackwardsTermQuery implements createWeight() by creating a custom BackwardsWeight that we’ll cover below:

@Override
public Weight createWeight(IndexSearcher searcher) throws IOException {
    return new BackwardsWeight(searcher);
}

BackwardsTermQuery has a fairly boilerplate equals() and hashCode() that passes through to the wrapped TermQuerys. Be sure equals() includes all the boilerplate stuff such as the check for self-comparison, the use of the super equals operator, the class comparison, etc etc. By using Lucene’s unit test suite, we can get a lot of good checks that our implementation of these is correct.

@Override
public boolean equals(Object other) {
    if (this == other) {
        return true;
    }
    if (!super.equals(other)) {
        return false;
    }
    if (getClass() != other .getClass()) {
        return false;
    }
    BackwardsTermQuery otherQ = (BackwardsTermQuery)(other);        
    if (otherQ.getBoost() != getBoost()) {
        return false;
    }
    return otherQ.backwardsQuery.equals(backwardsQuery) && otherQ.forwardsQuery.equals(forwardsQuery);
}

@Override
public int hashCode() {
    return super.hashCode() + backwardsQuery.hashCode() + forwardsQuery.hashCode(); 
}

Our Custom Weight

You may choose to use Weight simply as a mechanism to create Scorers (where the real meat of search scoring lives). However, your Custom Weight class must at least provide boilerplate implementations of the query normalization methods even if you largely ignore what is passed in:

  • getValueForNormalization
  • normalize

These methods participate in a little ritual that IndexSearcher puts your Weight through with the Similarity for query normalization. To summarize the query normalization code in the IndexSearcher:

float v = weight.getValueForNormalization();
float norm = getSimilarity().queryNorm(v);
weight.normalize(norm, 1.0f);

Great, what does this code do? Well a value is extracted from Weight. This value is then passed to a Similarity instance that “normalizes” that value. Weight then receives this normalized value back. In short, this is allowing IndexSearcher to give weight some information about how its “value for normalization” compares to the rest of the stuff being searched by this searcher.

This is extremely high level, “value for normalization” could mean anything, but here it generally means “what I think is my weight” and what Weight receives back is what the searcher says “no really here is your weight”. The details of what that means depend on the Similarity and Weight implementation. It’s expected that the Weight’s generated Scorer will use this normalized weight in scoring. You can chose to do whatever you want in your own Scorer including completely ignoring what’s passed to normalize().

While our Weight isn’t factoring into the scoring calculation, for consistency sake, we’ll participate in the little ritual by overriding these methods:

@Override
public float getValueForNormalization() throws IOException {
    return backwardsWeight.getValueForNormalization() + 
            forwardsWeight.getValueForNormalization();
}

@Override
public void normalize(float norm, float topLevelBoost) {
    backwardsWeight.normalize(norm, topLevelBoost);
    forwardsWeight.normalize(norm, topLevelBoost);
}

Outside of these query normalization details, and implementing “scorer”, little else happens in the Weight. However, you may perform whatever else that requires an IndexSearcher in the Weight constructor. In our implementation, we don’t perform any additional steps with IndexSearcher.

The final and most important requirement of Weight is to create a Scorer. For BackwardsWeight we construct our custom BackwardsScorer, passing scorers created from each of the wrapped queries to work with.

@Override
public Scorer scorer(AtomicReaderContext context, boolean scoreDocsInOrder,
        boolean topScorer, Bits acceptDocs) throws IOException {
    Scorer backwardsScorer = backwardsWeight.scorer(context, scoreDocsInOrder, topScorer, acceptDocs);
    Scorer forwardsScorer = forwardsWeight.scorer(context, scoreDocsInOrder, topScorer, acceptDocs);
    return new BackwardsScorer(this, context, backwardsScorer, forwardsScorer);
}

Our Custom Scorer

The Scorer is the real meat of the search work. Responsible for identifying matches and providing scores for those matches, this is where the lion share of our customization will occur.

It’s important to note that a Scorer is also a Lucene DocIdSetIterator. A DocIdSetIterator is a cursor into a set of documents in the index. It provides three important methods:

  • docID() – what is the id of the current document? (this is an internal Lucene ID, not the Solr “id” field you might have in your index)
  • nextDoc() – advance to the next document
  • advance(target) – advance (seek) to the target

One uses a DocIdSetIterator by first calling nextDoc() or advance() and then reading the docID to get the iterator’s current location. The value of the docIDs only increase as they are iterated over.

By implementing this interface a Scorer acts as an iterator over matches in the index. A Scorer for the query “field1:cat” can be iterated over in this manner to return all the documents that match the cat query. In fact, if you recall from my article, this is exactly how the terms are stored in the search index.

You can chose to either figure out how to correctly iterate through the documents in a search index, or you can use the other Lucene queries as building blocks. The latter is often the simplest. For example, if you wish to iterate over the set of documents containing two terms, simply use the scorer corresponding to a BooleanQuery for iteration purposes.

The first method of our scorer to look at is docID(). It works by reporting the lowest docID() of our underlying scorers. This scorer can be thought of as being “before” the other in the index, and as we want to report numerically increasing docIDs, we always want to chose this value:

@Override
public int docID() {
    int backwordsDocId = backwardsScorer.docID();
    int forwardsDocId = forwardsScorer.docID();
    if (backwordsDocId <= forwardsDocId && backwordsDocId != NO_MORE_DOCS) {
        currScore = BACKWARDS_SCORE;
        return backwordsDocId;
    } else if (forwardsDocId != NO_MORE_DOCS) {
        currScore = FORWARDS_SCORE;
        return forwardsDocId;
    }
    return NO_MORE_DOCS;
}

Similarly, we always want to advance the scorer with the lowest docID, moving it ahead. Then, we report our current position by returning docID() which as we’ve just seen will report the docID of the scorer that advanced the least in the nextDoc() operation.

@Override
public int nextDoc() throws IOException {
    int currDocId = docID();
    // increment one or both
    if (currDocId == backwardsScorer.docID()) {
        backwardsScorer.nextDoc();
    }
    if (currDocId == forwardsScorer.docID()) {
        forwardsScorer.nextDoc();
    }
    return docID();
}

In our advance() implementation, we allow each Scorer to advance. An advance() implementation promises to either land docID() exactly on or past target. Our call to docID() after we call advance will return either that one or both are on target, or it will return the lowest docID past target.

@Override
public int advance(int target) throws IOException {
    backwardsScorer.advance(target);
    forwardsScorer.advance(target);
    return docID();
}

What a Scorer adds on top of DocIdSetIterator is the “score” method. When score() is called, a score for the current document (the doc at docID) is expected to be returned. Using the full capabilities of the IndexReader, any number of information stored in the index can be consulted to arrive at a score either in score() or while iterating documents in nextDoc()/advance(). Given the docId, you’ll be able to access the term vector for that document (if available) to perform more sophisticated calculations.

In our query, we’ll simply keep track as to whether the current docID is from the wrapped backwards term scorer, indicating a match on the backwards term, or the forwards scorer, indicating a match on the normal, unreversed term. Recall docID() is always called on advance/nextDoc. You’ll notice we update currScore in docID, updating it every time the document advances.

@Override
public float score() throws IOException {
    return currScore;
}

A Note on Unit Testing

Now that we have an implementation of a search query, we’ll want to test it! I highly recommend using Lucene’s test framework. Lucene will randomly inject different implementations of various support classes, index implementations, to throw your code off balance. Additionally, Lucene creates test implementations of classes such as IndexReader that work to check whether your Query correctly fulfills its contract. In my work, I’ve had numerous cases where tests would fail intermittently, pointing to places where my use of Lucene’s data structures subtly violated the expected contract.

An example unit test is included in the github project associated with this blog post.

Wrapping Up

That’s a lot of stuff! And I didn’t even cover everything there is to know! As an exercise to the reader, you can explore the Scorer methods cost() and freq(), as well as the rewrite() method of Query used optionally for optimization.

Additionally, I haven’t explored how most of the traditional search queries end up using a framework of Scorers/Weights that don’t actually inherit from Scorer or Weight known as “SimScorer” and “SimWeight”. These support classes consult a Similarity instance to customize calculation certain search statistics such as tf, convert a payload to a boost, etc.

In short there’s a lot here! So tread carefully, there’s plenty of fiddly bits out there! But have fun! Creating a custom Lucene query is a great way to really understand how search works, and the last resort short in solving relevancy problems short of creating your own search engine.

And if you have relevancy issues, contact us! If you don’t know whether you do, our search relevancy product, Quepid – might be able to tell you!

32
Share: