Full-text search

When dealing with a small number of documents, a full-text-search engine can scan the contents of each document directly for every query, a strategy known as "serial scanning." Some tools, such as grep, operate in this way.^[1][8]

When the number of documents or queries is large, full-text search is typically divided into two tasks: indexing and searching. During indexing, the engine scans all documents and builds a list of search terms, often called an index, or more precisely, a concordance. During the search stage, queries are performed against the index rather than the original documents.^[1][2][8][9]

The indexer records each term found in a document and may note its position within the text. Common words, known as stop words (for instance, "the" or "and"), are omitted because they add little value to search results. Some indexers also perform stemming, which reduces words to their base form; for example, "drives", "drove", and "driven" may all be indexed under the concept word "drive."^{[1][2][8][10]}

Recall and precision are standard measures for search effectiveness. Recall quantifies the proportion of relevant results returned by a search, while precision measures the proportion of returned results that are relevant. Formally, recall is the ratio of relevant results returned to the total number of relevant results available, and precision is the ratio of the number of relevant results returned to the total number of results returned.^{[1][2][4][11]}

The diagram at the right illustrates a search with low recall and low precision. In the diagram, red and green dots represent the total population of potential search results for a given query, with green dots indicating relevant results and red indicating irrelevant results. Relevance is indicated by proximity to the center of the inner circle. The results actually returned by the search are highlighted on a light-blue background. In the example, only one relevant result of three possible relevant results was returned, giving a recall of ⅓ (33%). The precision is 1/4 (25%), since only one of the four results returned was relevant.^[11]

Due to the ambiguities of natural language, full-text-search systems typically include features such as filtering to increase precision and stemming to increase recall. Controlled-vocabulary search can also help alleviate low-precision results by tagging documents to reduce ambiguity.^[1][2][9] There is generally a trade-off between precision and recall: increasing precision can reduce overall recall, while increasing recall may lower precision.^[1][2][11]

Full-text search can retrieve many documents that are not relevant to the intended query. Such documents are called false positives (see Type I error). The retrieval of irrelevant documents is often caused by the inherent ambiguity of natural language.^[1][2][9] In the accompanying diagram, false positives are represented by irrelevant results (red dots) that were returned by the search (highlighted on a light-blue background).

Clustering techniques, often based on Bayesian algorithms, can help reduce false positives. For example, for a search term such as "bank", clustering can categorize documents into groups such as "financial institution", "place to sit", or "place to store." Depending on the occurrence of words relevant to these categories, a search term or a search result can be assigned to one or more categories. This approach is widely used in the e-discovery domain.^[12]

At a basic level, search engines return items that contain the exact phrase listed in the query. Tools and methodologies exist to account for grammatical or typographical errors and to refine results; however, these techniques still typically require a close textual match. Because there are often multiple ways to refer to an entity or concept, full-text search may fail to retrieve an item if the exact term is not used in the query.

Not to be confused with semantic search, synonyms can be retrieved by creating an index of related terms, such that when a variation of a word is searched, items containing any of the related terms may also be returned.^[13]

The limitations of full-text searching have been addressed in two ways: by providing users with tools to express search questions more precisely, and by developing algorithms that improve retrieval precision.^{[1][2][8][11][14]}

The following is a partial list of software products that support full-text indexing and search. Some of these are accompanied by documentation describing their architecture or algorithms, which may provide additional insight into how full-text search is implemented.