Full-text search

In text retrieval, full-text search refers to a set of techniques for searching a single computer-stored document or a collection in a full-text database. Full-text search is distinguished from searches based on metadata or on specific parts of documents, such as titles, abstracts, selected sections, or bibliographical references.

In a full-text search, a search engine examines the words in stored documents to find matches for user queries. Full-text-search techniques began to appear in the 1960s (for example, IBM STAIRS in 1969), and became common in online bibliographic databases during the 1990s. Many websites and application programs, including word processors, implement full-text search functionality. Some web search engines, such as the former AltaVista, indexed the full text of web pages, while others indexed only selected portions of pages.

Indexing

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.

The precision vs. recall tradeoff

150px|thumb|right|Diagram of a low-precision, low-recall search

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.

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. 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.

Synonym problem

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.

Performance improvements

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.

Phrase search: Matches documents containing an exact sequence of words, such as "Wikipedia, the free encyclopedia."
Concept search: Matches multi-word concepts, for example compound term processing. This approach is increasingly used in e-discovery solutions.
Concordance search: Produces an alphabetical list of all principal words that occur in a text along with their immediate context.
Proximity search: Retrieves documents in which two or more words occur within a specified distance, for example "Wikipedia" WITHIN2 "free" retrieves documents where "Wikipedia" and "free" are separated by at most two words.
Regular expression search: Uses a complex but powerful syntax to specify precise retrieval conditions.
Fuzzy search: Retrieves documents that match the query terms approximately, allowing for variations such as edit distance.
Wildcard search: Substitutes one or more characters in a query with a wildcard symbol (e.g., *). For example, "s*n" matches "sin", "son", or "sun."

Software

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.

Free and open source software

<!--

Please do not add web links or products which do not have Wikipedia articles. They will be summarily deleted.

-->

Apache Lucene
Apache Solr
ArangoSearch
BaseX
KinoSearch
Lemur/Indri
MariaDB
mnoGoSearch
MySQL
OpenSearch
PostgreSQL
Searchdaimon
Sphinx
Swish-e
Terrier IR Platform
Xapian

Proprietary software