> For the complete documentation index, see [llms.txt](https://isubasinghe.gitbook.io/isithas-wiki/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://isubasinghe.gitbook.io/isithas-wiki/computer_science/search.md).

# search

## Basic idea

Locating items matching a query in a large corpus. Information-retrieval search uses an inverted index plus a ranking function (TF-IDF, BM25); algorithmic search explores combinatorial state spaces.

## Key formulas

* TF-IDF: $\text{tfidf}(t,d) = tf(t,d) \cdot \log\dfrac{N}{df(t)}$
* BM25: $\text{score}(d,q) = \sum\_t \text{IDF}(t),\dfrac{tf(t,d)(k\_1+1)}{tf(t,d) + k\_1(1-b+b,|d|/\overline{|d|})}$