Principles of Full-Text Search Engines and a Brief Introduction to Lucene

Preface

Following my previous blog post introducing the Whoosh search engine, I planned to write a series of articles on “Building Your Own Search Engine from Scratch.” On second thought, I figured I should first write an article introducing the principles, and then start—hence this article.

Data in our lives generally falls into two types: structured data and unstructured data.

• Structured data: Data with a fixed format or limited length, such as databases, metadata, etc.
• Unstructured data: Data of variable length or without a fixed format, such as emails, Word documents, etc.

Unstructured data is also known as full-text data.

According to this classification of data, search also falls into two types:

• Search of structured data: For example, searching a database using SQL statements. Another example is searching metadata, such as using Windows Search to search by file name, type, modification time, etc.
• Search of unstructured data: For example, Windows Search can also search file contents; the grep command under Linux; and Google and Baidu can search large amounts of content data.

There are mainly two methods for searching unstructured data, that is, full-text data:

One is serial scanning (Serial Scanning): So-called serial scanning, for example if you want to find files whose content contains a certain string, you look at one document after another; for each document, you read from beginning to end; if this document contains the string, then this document is the file we are looking for; then you look at the next file, until all files have been scanned. For example, using Windows Search can also search file contents, but it is quite slow. Suppose you have an 80G hard drive, if you want to find a file whose content contains a certain string, it might take several hours. The grep command under Linux is also this kind of approach. This is a relatively primitive method, but for files with a small amount of data, this method is still the most direct and convenient. However, for a large number of files, this method is very slow.

The other is full-text search (Full-text Search): that is, first build an index, then search the index. An index is information extracted from unstructured data and then reorganized.

Basic Implementation Principles of a Full-Text Search Engine

The following figure comes from Lucene in Action, but it describes not only Lucene but also the general process of a full-text search engine.

Full-text search generally consists of two processes, index creation (Indexing) and searching the index (Search).

• Index creation: The process of extracting information from all structured and unstructured data in the real world and creating an index.
• Searching the index: The process of receiving the user’s query request, searching the created index, and then returning results.

Index Creation

The index creation process of full-text search generally has the following steps:

Step 1: Some original documents (Document) to be indexed.

To make it easier to explain the index creation process, here we specially use two files as examples:

• File 1: Students should be allowed to go out with their friends, but not allowed to drink beer.
• File 2: My friend Jerry went to school to see his students but found them drunk which is not allowed.

Step 2: Pass the original documents to the tokenizer component (Tokenizer).

The tokenizer component (Tokenizer) will do the following things (this process is called Tokenize):

1. Split the document into individual words.
2. Remove punctuation.
3. Remove stop words (Stop word).

So-called stop words (Stop word) are some of the most common words in a language. Because they have no special meaning, in most cases they cannot become search keywords, so when creating an index, these words are removed to reduce the size of the index.

Stop words (Stop word) in English such as: “the”, “a”, “this”, etc.

For the tokenizer component (Tokenizer) of each language, there is a stop word (stop word) set.

The result obtained after tokenization (Tokenizer) is called a token (Token).

In our example, we get the following tokens (Token):

“Students”, “allowed”, “go”, “their”, “friends”, “allowed”, “drink”, “beer”, “My”, “friend”, “Jerry”, “went”, “school”, “see”, “his”, “students”, “found”, “them”, “drunk”, “allowed”.

Step 3: Pass the obtained tokens (Token) to the linguistic processor component (Linguistic Processor).

The linguistic processor component (linguistic processor) mainly does some language-related processing on the obtained tokens (Token).

For English, the linguistic processor component (Linguistic Processor) generally does the following:

1. Convert to lowercase (Lowercase).
2. Reduce words to their stem form, such as "cars" to "car", etc. This operation is called: stemming.
3. Transform words into their root form, such as "drove" to "drive", etc. This operation is called: lemmatization.

Similarities and differences between Stemming and lemmatization:

• Similarities: Both stemming and lemmatization aim to turn vocabulary into root form.
• The two methods are different:
  • Stemming uses a “reduction” approach: “cars” to “car”, “driving” to “drive”.
  • Lemmatization uses a “transformation” approach: “drove” to “drove”, “driving” to “drive”.
• The two algorithms are different:
  • Stemming mainly uses some fixed algorithm to do this reduction, such as removing “s”, removing “ing” and adding “e”, changing “ational” to “ate”, changing “tional” to “tion”.
  • Lemmatization mainly uses the approach of storing some kind of dictionary to do this transformation. For example, the dictionary has mappings from “driving” to “drive”, “drove” to “drive”, “am, is, are” to “be”; when transforming, you just look it up in the dictionary.
• Stemming and lemmatization are not mutually exclusive; they have an intersection. Some words can achieve the same conversion using both methods.

The result of the linguistic processor component (linguistic processor) is called a term (Term).

In our example, after language processing, the terms (Term) obtained are as follows:

“student”, “allow”, “go”, “their”, “friend”, “allow”, “drink”, “beer”, “my”, “friend”, “jerry”, “go”, “school”, “see”, “his”, “student”, “find”, “them”, “drink”, “allow”.

It is precisely because of the language processing step that searching for drove can also find drive.

Querying the Index

When the user enters keywords to search, the search engine looks for matching indexes in the index, and through the index finds the original documents. This is the process of querying the index. But this is not the end yet—do you think finding the original documents is all there is to it? nope. If there are only one or ten documents containing the string we queried, we have indeed found them. But what if there are a thousand results, or even tens of thousands? Which one is the file you want most?

At this point we need to calculate the weight of each result according to a scoring algorithm, sort them, and then display them to the user~

Querying the index generally goes through the following four steps:

1. The user enters a query statement
2. Perform lexical analysis on the query statement (identify words and keywords), syntactic analysis (form a syntax tree according to the grammar rules of the query statement), and language processing (further processing of the original language)
3. Search the index to get documents that match the syntax tree
4. Sort the results according to the relevance between the obtained documents and the query statement

The process of determining the relationships between terms (Term) to obtain document relevance applies an algorithm called the vector space model (Vector Space Model)**

Below we carefully analyze these two processes:

1. The process of calculating weights (Term weight).

There are mainly two factors that affect the importance of a term (Term) in a document:

• Term Frequency (tf): That is, how many times this Term appears in this document. The larger the tf, the more important it is.
• Document Frequency (df): That is, how many documents contain this Term. The larger the df, the less important it is.

Easy to understand? The more times a term (Term) appears in a document, the more important this term (Term) is to this document. For example, the word “search” appears many times in this document, indicating that this document is mainly about this topic. However, in an English document, this appears even more times—does that mean it’s more important? No. This is adjusted by the second factor. The second factor indicates that the more documents contain this term (Term), the more common this term (Term) is, insufficient to distinguish these documents, and thus the lower its importance.

This is also like the technologies we programmers learn. For the programmer themselves, the deeper they master this technology the better (the deeper the mastery means the more time spent studying it, the larger the tf), the more competitive they are when looking for a job. However, for all programmers, the fewer people who know this technology the better (few people who know it means small df), the more competitive they are when looking for a job. The value of a person lies in irreplaceability—that’s the idea.

Now that the principle is clear, let’s look at the formula:

This is merely a simple typical implementation of the term weight calculation formula. Different full-text search systems will have different implementations; Lucene is slightly different from this.

2. The process of determining the relationships between Terms to obtain document relevance, that is, the vector space model algorithm (VSM).

We regard a document as a series of terms (Term), each term (Term) has a weight (Term weight), and different terms (Term) affect the scoring calculation of document relevance according to their own weights in the document.

So we regard the weights (term weight) of all terms (term) in this document as a vector.

Document = {term1, term2, …… ,term N}

Document Vector = {weight1, weight2, …… ,weight N}

Likewise we regard the query statement as a simple document, also represented by a vector.

Query = {term1, term 2, …… , term N}

Query Vector = {weight1, weight2, …… , weight N}

We put all the searched document vectors and the query vector into an N-dimensional space, where each term (term) is one dimension. As shown in the figure:

We believe that the smaller the angle between two vectors, the greater the relevance.

So we calculate the cosine of the angle as the relevance score. The smaller the angle, the larger the cosine value, the higher the score, and the greater the relevance.

Someone might ask, query statements are generally very short, containing few terms (Term), so the dimensionality of the query vector is small, while documents are long, containing many terms (Term), so the dimensionality of the document vector is large. How come in your figure both dimensions are N?

Here, since they need to be placed in the same vector space, naturally the dimensions are the same. When they differ, take the union of the two; if a certain term (Term) is not contained, then the weight (Term Weight) is 0.

The relevance scoring formula is as follows:

For example, the query statement has 11 Terms, and a total of three documents were found. Their respective weights (Term weight) are shown in the following table.

Then we calculate, the relevance scores of the three documents with the query statement are respectively:

So document two has the highest relevance and is returned first, followed by document one, and finally document three.

Up to this point, we can find the documents we want most.

A Brief Introduction to Lucene

Index Creation and Search Process

1. Indexing process:
   1. There is a series of files to be indexed
   2. The files to be indexed undergo syntactic analysis and language processing to form a series of terms (Term).
   3. Through index creation, a dictionary and inverted index table are formed.
   4. Through index storage, the index is written to the hard disk.

2. Search process: a) The user enters a query statement. b) The query statement undergoes syntactic analysis and language analysis to obtain a series of terms (Term). c) Through syntactic analysis, a query tree is obtained. d) Through index storage, the index is read into memory. e) Use the query tree to search the index, thereby obtaining the document linked list of each term (Term), and perform intersection, difference, and union on the document linked lists to obtain the result documents. f) Sort the searched result documents by their relevance to the query. g) Return the query results to the user.

Building an Index

To index documents, Lucene provides five basic classes, which are Document, Field, IndexWriter, Analyzer, Directory. Below we introduce the purpose of these five classes respectively:

Document

Document is used to describe a document. The document here can refer to an HTML page, an email, or a text file. A Document object is composed of multiple Field objects. You can think of a Document object as a record in a database, and each Field object is a field of the record.

Field

A Field object is used to describe a certain attribute of a document. For example, the title and content of an email can be described by two Field objects respectively.

Analyzer

Before a document is indexed, the document content first needs to undergo tokenization processing, and this part of the work is done by Analyzer. The Analyzer class is an abstract class with multiple implementations. You need to choose a suitable Analyzer for different languages and applications. Analyzer hands the tokenized content over to IndexWriter to build the index.

IndexWriter

IndexWriter is a core class used by Lucene to create indexes. Its role is to add Document objects one by one into the index.

Directory

This class represents the storage location of Lucene’s index. This is an abstract class. It currently has two implementations. The first is FSDirectory, which represents an index location stored in the file system. The second is RAMDirectory, which represents an index location stored in memory.

Searching Documents

Using Lucene to search is just as convenient as building an index. In the previous section, we have already built an index for the text documents under a directory. Now we need to search on this index to find documents containing a certain keyword or phrase. Lucene provides several basic classes to complete this process, which are IndexSearcher, Term, Query, TermQuery, Hits. Below we introduce the functions of these classes respectively.

Query

This is an abstract class with multiple implementations, such as TermQuery, BooleanQuery, PrefixQuery. The purpose of this class is to encapsulate the query string entered by the user into a Query that Lucene can recognize.

Term

Term is the basic unit of search. A Term object consists of two String-type fields. Creating a Term object can be done with the following statement: Term term = new Term(“fieldName”,”queryWord”); where the first parameter represents which Field of the document to search on, and the second parameter represents the keyword to query.

TermQuery

TermQuery is a subclass of the abstract class Query, and it is also the most basic query class supported by Lucene. Creating a TermQuery object is done with the following statement: TermQuery termQuery = new TermQuery(new Term(“fieldName”,”queryWord”)); Its constructor accepts only one parameter, which is a Term object.

IndexSearcher

IndexSearcher is used to search on a built index. It can only open an index in read-only mode, so multiple IndexSearcher instances can operate on one index.

Hits

Hits is used to save the search results.

Welcome to Connect with Me

• Coding livestream: https://live.bilibili.com/11883038
• WeChat official account: DealiAxy
• Zhihu: https://www.zhihu.com/people/dealiaxy
• Blog: https://blog.deali.cn