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. ==The precision vs. recall tradeoff==

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. There is generally a trade-off between precision and recall: increasing precision can reduce overall recall, while increasing recall may lower precision. ==False-positive problem==

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. 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 • Apache Lucene • Apache Solr • ArangoSearch • BaseX • KinoSearch • Lemur/Indri • MariaDB • mnoGoSearch • MySQL • OpenSearch • PostgreSQL • Searchdaimon • Sphinx • Swish-e • Terrier IR Platform • Xapian Proprietary software • Algolia • Autonomy Corporation • Azure Search • Bar Ilan Responsa Project • Basis database • Brainware • BRS/Search • Concept Searching Limited • Dieselpoint • dtSearch • Elasticsearch • Endeca • Exalead • Fast Search & Transfer • Inktomi • Lucid Imagination • MarkLogic • MongoDB • SAP HANA • Swiftype • Thunderstone Software LLC • Vivísimo == References ==