Live demo: https://umer-78.github.io/text-search/
A search engine written from scratch in Python: an inverted index that records positions, BM25 ranking, phrase and boolean queries, a Porter stemmer and edit-distance typo tolerance. No dependencies — not even NumPy. Every posting list, every score and every suffix rule is implemented here.
$ textsearch explain saturating length normalisation
BM25 ranking [bm25.txt] 76 terms (average 61.1)
term in doc in corpus idf contributes
satur 2 1 2.159 2.8605
length 2 2 1.649 2.1838
normalis 1 3 1.312 1.1823
total 6.2266
- 115 tests, Python 3.10–3.12, standard library only
- Every claim below is asserted by a test, including the two places where the textbook version of the algorithm is wrong and this one deviates
git clone https://github.com/umer-78/text-search.git
cd text-search
pip install -e ".[dev]"
pytest -q # 115 tests
textsearch index corpus
textsearch search "ranking documents by relevance"
textsearch phrase "posting lists"
textsearch boolean "index AND (bm25 OR ranking) AND NOT compression"
textsearch fuzzy stemer
textsearch explain saturating length normalisation
textsearch suggest invertd
textsearch statsThe corpus is twelve short documents about information retrieval, written for
this project and regenerated by tools/make_corpus.py. CI regenerates it and
fails if a byte changes, so the numbers printed below are reproducible rather
than remembered.
$ textsearch index corpus
indexed 12 documents from corpus -> index/corpus.pkl
387 distinct terms, 616 postings, 61.1 terms per document on average
The inverse document frequency in the published BM25 is:
idf(t) = ln( (N − df + 0.5) / (df + 0.5) )
The numerator goes below the denominator as soon as a term appears in more than
half the collection, and the logarithm goes negative. A negative idf does not
mean "this term is uninformative"; it means the score subtracts. Search this
corpus for documents and every file that contains the word is pushed below
every file that does not.
The word document appears in 10 of the 12 corpus files. Both forms, measured:
| form | value |
|---|---|
ln((N − df + 0.5) / (df + 0.5)) |
−1.4351 |
ln(1 + (N − df + 0.5) / (df + 0.5)) |
+0.2136 |
The 1 + is what Lucene uses. It leaves the curve's shape alone where the term
is rare and floors the whole thing above zero. Index.textbook_idf is kept
beside Index.idf so the failure can be demonstrated rather than described, and
test_textbook_idf_goes_negative_for_a_common_term pins both numbers.
Stopwords are removed from the index, but their positions are held open — the tokeniser emits an empty string rather than dropping the slot:
$ textsearch stem "Universities are running experiments"
word stem
Universities univers
are ar
running run
experiments experi
index terms: ['univers', 'run', 'experi']
That is the well-known half of the problem: without positions, a search for
"New York" matches a document mentioning New Mexico and York in different
paragraphs. The half that is easy to get wrong is the query side. Tokenising
state of the art gives ['state', '', '', 'art']. Collapse that to
['state', 'art'], demand adjacency, and the phrase search is wrong in both
directions at once:
| document | contains the phrase? | naive implementation |
|---|---|---|
the state of the art in ranking |
yes | missed |
state art |
no | matched |
So the offsets survive from the query into the lookup: art is required three
positions after state, not one. This was a live bug, caught by the test that
now guards it.
$ textsearch phrase "posting lists"
1. Stopwords [stopwords.txt] score 1.8651
2. Boolean queries [boolean-queries.txt] score 1.7948
3. Compressing posting lists [compression.txt] score 1.7681
3 document(s) contain the phrase; 6 contain the words anywhere.
Six documents use both words; three put them together. That gap is the entire justification for storing positions, and it costs this index 616 postings instead of 616 counts.
Two separate mechanisms, measured separately. Three documents: short.txt says
"alpha" twice in five terms, spam.txt says it twenty times, long.txt says it
twice in sixty-two terms.
Saturation. Ten times the mentions, holding length constant:
| TF-IDF | BM25 | |
|---|---|---|
| score ratio, tf 20 vs tf 2 | ×10.00 | ×1.25 |
Length normalisation. Identical term frequency, twelve times the length:
| TF-IDF | BM25 | |
|---|---|---|
short.txt vs long.txt |
identical | ×1.83 |
TF-IDF cannot distinguish the two documents at all, and rewards repetition
linearly and without limit. k1 controls the first curve and b the second;
setting k1=0 makes every frequency score the same, and b=0 switches length
off entirely. Both are tested.
$ textsearch boolean "index AND (bm25 OR ranking) AND NOT compression"
Caching search results [caching.txt]
Phrase queries [phrase-queries.txt]
2 document(s) match. Boolean queries filter; they do not rank.
bm25.txt is missing from those results, and that is correct: it never uses the
word "index". Boolean retrieval matches literal terms, not subject matter, which
is exactly why it is a poor default and a good filter. The parser is
recursive-descent over AND, OR, NOT and parentheses, with NOT binding
tightest and AND tighter than OR, so alpha OR beta AND gamma parses as
alpha OR (beta AND gamma). boolean_search returns a set, deliberately:
handing back a ranked list would imply a relevance judgement the query never
made.
The Porter algorithm is five steps of suffix rules gated on a syllable count. It
is written out in full in tokenize.py, which makes its limits legible:
$ textsearch suggest invertd
invertd:
invert 1 edit(s), 1 documents
insert 2 edit(s), 1 documents
invent 2 edit(s), 1 documents
invers 2 edit(s), 1 documents
universe and university both reduce to univers and become the same term —
a false merge. In the other direction, stemming and stems both reduce to
stem, but stemmer does not: the -er rule fires only when the remainder has
measure greater than one, and stemm has measure one. A search for the noun
misses the gerund. Both behaviours have tests
(test_porter_does_not_conflate_stemming_with_stemmer) because a stemmer that
is quietly wrong in one direction is worse than one whose failures are written
down.
Typos are handled separately, by edit distance over the vocabulary. Ties are broken by document frequency — given two corrections equally close, the commoner word is the likelier intent — and the distance computation abandons a comparison as soon as every cell exceeds the threshold, which is what makes scanning 387 terms per lookup affordable.
$ textsearch fuzzy stemer
nothing matched 'stemer' exactly; searching near terms instead
1. Stemming and its costs [stemming.txt] score 2.145
matched: stemmer
src/textsearch/
tokenize.py folding, stopwords, the Porter stemmer
index.py documents, postings, positions, idf, persistence
search.py BM25, phrases, booleans, edit distance, explanation
cli.py nine subcommands
corpus/ 12 documents, regenerated by tools/make_corpus.py
tests/ 115 tests
Index.save / Index.load round-trip the whole structure, and a test asserts
that a reloaded index produces byte-identical rankings and can still be extended
with new documents — a persistence format that quietly drops the scoring
parameters would be undetectable until someone compared results months later.
$ pytest -q
115 passed
They are grouped by what they defend: test_tokenize.py on folding, stopwords
and each Porter step; test_index.py on postings, positions, statistics, both
idf forms and persistence; test_search.py on ranking, phrases, boolean
precedence, edit distance and explanation. The four that matter most are the
ones that would pass against a subtly wrong implementation of the algorithm as
usually written: the negative idf, the phrase gap, the saturation ratio and the
Porter -er limitation.
MIT.