> 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 solutions or records in a large space. Information retrieval uses indexes and ranking functions; algorithmic search explores state spaces using costs, heuristics, constraints, and goal predicates.

## 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|})}$
* A\*: $f(n)=g(n)+h(n)$
* Admissible heuristic: $h(n)\leq h^\*(n)$