Inverttihakemistoa

Inverttihakemistoa, which translates to "inverted index" in English, is a data structure used by search engines and information retrieval systems to store and search through a collection of documents. Instead of storing documents and then searching for keywords within them, an inverted index stores a list of words and for each word, a list of documents that contain it.

The core of an inverted index consists of two main components: a vocabulary (or dictionary) and a postings list. The vocabulary is a sorted list of all unique terms (words) present in the document collection. For each term in the vocabulary, there is a corresponding postings list. The postings list contains the identifiers of the documents in which the term appears. Often, the postings list also includes additional information, such as the frequency of the term within each document or the positions of the term within the document, which can be used for more advanced searching like phrase searching or proximity searching.

When a search query is submitted, the system looks up each term of the query in the inverted index. It then retrieves the postings lists for each term. To find documents that contain all the query terms (an AND operation), the system performs an intersection of these postings lists. For an OR operation, it performs a union. The efficiency of the inverted index allows for very fast retrieval of relevant documents, even from massive datasets. This makes it a fundamental component in modern search technologies.