Search System Deep-Dive

The Wikifita Atlas implements a custom search system that combines BM25 text relevance with PageRank authority, title matching, and graph-based proximity. The search index is built lazily from the wiki corpus and cached for the lifetime of the corpus instance.

All search logic lives in lib/wiki.ts, functions buildSearchIndex (lines 739-764) and searchWiki (lines 788-831).

Architecture Overview

flowchart TD
    A[WikiCorpus] -->|lazy build| B[SearchIndex]
    B --> C[documents: SearchDocument[]]
    B --> D[documentFrequency: Map]
    B --> E[averageLength: number]
    F[Query] -->|tokenize| G[queryTokens]
    G --> H{For each document}
    H --> I[BM25 Score]
    H --> J[Title Boost]
    H --> K[PageRank Boost]
    H --> L[Proximity Boost]
    I --> M[Weighted Sum]
    J --> M
    K --> M
    L --> M
    M --> N[Sorted Results]

Search Index Construction

The search index is a lazy singleton, cached via WeakMap<WikiCorpus, SearchIndex>. When searchWiki is first called for a corpus, the index is built. Subsequent calls reuse the cached index until a new corpus replaces the old one (the WeakMap key changes).

Document Assembly

For each page in the corpus, the searchable text is assembled by concatenating multiple fields:

searchableText = title + " " + description + " " + tags.join(" ") + " " + type + " " + category + " " + path + " " + body

This means a search for "memory" will match pages with:

"Memory" in the title
type: memory in frontmatter
category: memory metadata
memorias/ in the file path
The word "memory" in the body text

Tokenization

The tokenizer (tokenize, lines 722-724) performs four transformations:

1. Unicode NFD normalization
   "Café" -> "Café" (decomposed)

2. Strip diacritics (Unicode combining marks, category \p{M})
   "Café" -> "Cafe"

3. Lowercase (pt-BR locale)
   "Cafe" -> "cafe"

4. Extract tokens matching /[\p{L}\p{N}_-]+/gu
   "cafe-com-leite 2.0" -> ["cafe", "com", "leite", "2.0"]

The accent folding (steps 1-2) is critical for Portuguese content. The wikifita corpus contains extensive Portuguese text with diacritics (memória, diretiva, pesquisa). The tokenizer ensures that searching for "memoria" matches "memória" and vice versa.

The token pattern [\p{L}\p{N}_-]+ captures:

Unicode letters (including accented characters before folding)
Digits
Underscores and hyphens (common in filenames and technical terms)

Index Structure

type SearchIndex = {
  documents: SearchDocument[];           // One per page
  documentFrequency: Map<string, number>; // token -> number of docs containing it
  averageLength: number;                 // Mean document length in tokens
};

type SearchDocument = {
  page: WikiPage;                        // Reference to the source page
  tokens: string[];                      // All tokens in order
  frequencies: Map<string, number>;      // token -> count within this document
  length: number;                        // Total token count (min 1)
};

Document Frequency

After all documents are tokenized, the documentFrequency map is built by counting how many documents contain each unique token:

for each document in index:
    for each unique token in document.frequencies:
        documentFrequency[token] += 1

This map is used in the BM25 IDF calculation. A token that appears in many documents has low IDF (low discriminative power), while a token in few documents has high IDF.

Average Document Length

\text{avgdl} = \frac{1}{N} \sum_{i=1}^{N} \text{dl}_i

Where $\text{dl}_i$ is the token count of document $i$ (minimum 1 to avoid division by zero). The average length is used in BM25's document length normalization.

BM25 Scoring

BM25 (Best Match 25) is a probabilistic retrieval function that scores documents based on term frequency and inverse document frequency. The Wikifita implementation uses non-standard parameters tuned for wiki content.

Parameters

Parameter	Value	Standard BM25	Effect
`k1`	1.35	1.2-2.0	Term frequency saturation. Higher values increase the impact of repeated terms.
`b`	0.72	0.75	Document length normalization. Lower values reduce the penalty for long documents.

The b = 0.72 value is slightly below the standard 0.75, meaning long wiki pages are penalized less than they would be in standard BM25. This is deliberate: wiki pages naturally vary in length, and short stub pages should not rank artificially high just because they are short.

The k1 = 1.35 is slightly above the standard 1.2, giving more weight to terms that appear multiple times in a document. This helps surface pages that deeply cover a topic, not just mention it once.

BM25 Formula

For each query term $q$ and document $d$ :

\text{BM25}(q, d) = \sum_{t \in q} \text{IDF}(t) \cdot \frac{f(t, d) \cdot (k_1 + 1)}{f(t, d) + k_1 \cdot \left(1 - b + b \cdot \frac{\text{dl}}{\text{avgdl}}\right)}

Where:

$f(t, d)$ = frequency of term $t$ in document $d$
$\text{dl}$ = document length (token count)
$\text{avgdl}$ = average document length across the corpus
$N$ = total number of documents
$\text{df}(t)$ = number of documents containing term $t$

IDF Calculation

\text{IDF}(t) = \ln\left(1 + \frac{N - \text{df}(t) + 0.5}{\text{df}(t) + 0.5}\right)

This is the Robertson-Sparck Jones IDF variant with a +1 floor, ensuring all IDF values are positive. Rare terms (low df) get high IDF; common terms (high df) get low IDF.

Term appears in	IDF (N=100)	Interpretation
1 document	$\ln(1 + 198/1.5) \approx 4.88$	Very distinctive
10 documents	$\ln(1 + 90.5/10.5) \approx 2.25$	Moderately distinctive
50 documents	$\ln(1 + 50.5/50.5) \approx 0.69$	Common
100 documents	$\ln(1 + 0.5/100.5) \approx 0.005$	Near-zero (appears everywhere)

Term Frequency Saturation

The numerator $f(t,d) \cdot (k_1 + 1)$ grows linearly with frequency, but the denominator $f(t,d) + k_1 \cdot (1 - b + b \cdot \text{dl/avgdl})$ also grows, causing the score to saturate. With $k_1 = 1.35$ :

Term Frequency	Raw BM25 Contribution (normalized doc)
1	$\frac{1 \times 2.35}{1 + 1.35} = 1.0$ (baseline)
2	$\frac{2 \times 2.35}{2 + 1.35} = 1.40$
5	$\frac{5 \times 2.35}{5 + 1.35} = 1.85$
10	$\frac{10 \times 2.35}{10 + 1.35} = 2.07$
50	$\frac{50 \times 2.35}{50 + 1.35} = 2.29$

The diminishing returns are clear: going from 1 to 2 occurrences gives a 40% boost, but going from 10 to 50 gives only 11%.

Score Composition

The final search score is a weighted sum of four components:

\text{finalScore} = \text{bm25} \times 1.8 + \text{titleBoost} + \text{pagerankBoost} + \text{proximityBoost}

Component Breakdown

Component	Weight	Range	Source
BM25	$\times 1.8$	0 to ~15 (depends on query)	Text relevance
Title Boost	+4.0, +1.5, or 0	Discrete	Exact or substring title match
PageRank Boost	0 to +1.25	Continuous	Proportional to normalized PageRank wikifita-site-pagerank
Proximity Boost	0 to +1.25	Discrete (0, 0.20, 0.55, 0.90, 1.25)	BFS graph distance wikifita-site-graph-construction

Title Boost

The title boost is a strong signal for navigational queries (when the user is searching for a specific page by name):

Condition	Boost	Example
Normalized title equals normalized query	+4.0	Query "memory index" matches page titled "Memory Index"
Normalized title contains normalized query	+1.5	Query "memory" matches page titled "Memory Index"
Neither	0	Query "pagerank" does not match "Memory Index" title

Both comparisons use the same accent-folding tokenizer as the BM25 index: NFD normalization, diacritic stripping, lowercase.

PageRank Boost

\text{pagerankBoost} = \frac{\text{pagerank}(p)}{\text{pagerank}_{\max}} \times 1.25

The highest-ranked page in the corpus gets a boost of exactly 1.25. All other pages get a proportionally smaller boost. This ensures authoritative, well-connected pages surface above obscure ones when text relevance is similar.

Proximity Boost

When a focusPath is provided (the user is searching from a specific document page), the system computes the BFS graph distance between the focus page and each candidate result.

See the dedicated section below for the full BFS algorithm.

\text{proximityBoost} = \max(0,\ 1.25 - \text{distance} \times 0.35)

Graph Distance	Proximity Boost	Interpretation
0 (same page)	1.25	Focus page itself
1 (direct link)	0.90	Directly linked from focus
2 (two hops)	0.55	Linked from a linked page
3 (three hops)	0.20	Distant connection
>3 or disconnected	0.00	No proximity signal

Graph Distance (BFS)

The proximity boost uses Breadth-First Search on an undirected version of the link graph to find the shortest path between two pages.

Graph Construction for BFS

The BFS graph treats the link graph as undirected: if page A links to page B, traversal can go in either direction. This is implemented by combining outlinks and backlinks:

function buildUndirectedAdjacency(corpus: WikiCorpus): Map<string, string[]> {
  const adj = new Map<string, string[]>();
  for (const page of corpus.pages) {
    // Add outlinks (forward direction)
    for (const target of page.outlinks) {
      addEdge(adj, page.path, target);
    }
    // Add backlinks (reverse direction)
    for (const source of page.backlinks) {
      addEdge(adj, page.path, source);
    }
  }
  return adj;
}

BFS Algorithm

function graphDistance(start: string, target: string, adjacency: Map<string, string[]>): number {
  if (start === target) return 0;

  const visited = new Set<string>([start]);
  const queue: [string, number][] = [[start, 0]];
  const maxDepth = 3;

  while (queue.length > 0) {
    const [current, depth] = queue.shift();
    if (depth >= maxDepth) continue;

    for (const neighbor of adjacency.get(current) || []) {
      if (neighbor === target) return depth + 1;
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, depth + 1]);
      }
    }
  }

  return Infinity; // Beyond max depth or disconnected
}

Properties

Max depth: 3 hops. The search does not explore beyond 3 hops, preventing expensive traversal on large graphs.
Undirected: A page that links to the focus page (backlink) is distance 1, just like a page linked from the focus page (outlink).
Shortest path: BFS guarantees the shortest path is found first.
Disconnected pages: Pages unreachable within 3 hops return Infinity, resulting in a proximity boost of 0.
Self-distance: The focus page itself has distance 0 and receives the maximum boost of 1.25.

Performance

For the Wikifita corpus (50-200 pages, max depth 3), BFS explores at most $O(k^3)$ nodes where $k$ is the average degree. With $k \approx 4$ and $N \approx 100$ , this is roughly $4^3 = 64$ nodes per search -- negligible.

The BFS runs once per candidate result. For a typical search returning 10-20 results, the total BFS cost is 10-20 traversals of at most 64 nodes each.

Query Processing

Tokenization

The query string is tokenized using the same function as document indexing:

1. Unicode NFD normalization
2. Strip diacritics
3. Lowercase (pt-BR locale)
4. Extract tokens: /[\p{L}\p{N}_-]+/gu

This ensures query tokens match document tokens regardless of accent differences.

Multi-Term Queries

For multi-term queries, BM25 sums the per-term scores. Each query term is scored independently against each document, and the contributions are additive:

\text{BM25}(Q, d) = \sum_{t \in Q} \text{BM25}_t(t, d)

The title boost checks if the full normalized query matches the title (not individual terms). So a query "unit distance" gets +4.0 only if the title is exactly "Unit Distance" (after normalization), not if it contains "unit" or "distance" separately.

Result Ranking

Results are sorted by a three-level comparison:

1. score DESC        (primary: composite score)
2. pagerank DESC     (first tiebreaker: page authority)
3. path ASC          (final tiebreaker: alphabetical for determinism)

Result Object

type WikiSearchResult = {
  path: string;           // Page file path
  score: number;          // Final composite score
  bm25: number;           // Raw BM25 score (before weight)
  titleBoost: number;     // 0, 1.5, or 4.0
  pagerankBoost: number;  // 0 to 1.25
  proximityBoost: number; // 0 to 1.25
  explanation: string;    // Human-readable score breakdown
};

The explanation field provides a human-readable breakdown of how the score was computed, useful for debugging and transparency.

Suppression Rules

Certain pages are excluded from search suggestions (but not from the search index itself):

Suppressed Filename	Reason
`claude` (any extension)	Internal agent configuration
`agents` (any extension)	Internal agent configuration
`index` (any extension)	Index pages are navigation, not content
`prefill` (any part of filename)	Template content
`template` (any part of filename)	Template content

Suppressed pages can still appear in direct search results but are excluded from the top-3 suggestions on the home page and sidebar.

Search API

The search API is exposed at:

GET /api/search?q=<query>&limit=<1-50>&focus=<path>

Parameters

Parameter	Type	Default	Description
`q`	string	required	Search query
`limit`	number	10	Maximum results (1-50)
`focus`	string	optional	Page path for proximity boosting

Response

{
  "query": "pagerank algorithm",
  "limit": 10,
  "source": {
    "repository": "aleffita/wikifita",
    "branch": "main",
    "commit": "abc123",
    "state": "live"
  },
  "results": [
    {
      "path": "wiki/pagerank.md",
      "score": 12.45,
      "bm25": 5.2,
      "titleBoost": 4.0,
      "pagerankBoost": 0.89,
      "proximityBoost": 0.90,
      "explanation": "bm25=5.20*1.8=9.36 title=4.00 pr=0.89 prox=0.90"
    }
  ]
}

Response Headers

Header	Description
`Content-Type`	`application/json`
`ETag`	Deterministic hash for cache validation
`X-Wikifita-Source`	`github` or `snapshot`
`X-Wikifita-Commit`	Current commit SHA
`Cache-Control`	`no-store`

Scoring Example

Consider a wiki with 50 pages. A user searches for "memoria persistente" from the page memorias/MEMORY.md.

Query Tokenization

"memoria persistente" -> ["memoria", "persistente"]

Candidate: `memorias/MEMORY.md` (Memory Index)

Component	Calculation	Value
BM25	"memoria" appears 5 times, "persistente" appears 3 times	8.5
BM25 weighted	8.5 * 1.8	15.3
Title boost	"Memory Index" contains "memoria" after normalization	+1.5
PageRank boost	Highest-ranked page, normalized rank = 0.72	+0.90
Proximity boost	Distance 0 (same page)	+1.25
Total		18.95

Candidate: `wiki/log.md` (Changelog)

Component	Calculation	Value
BM25	"memoria" appears 1 time, "persistente" appears 0 times	1.2
BM25 weighted	1.2 * 1.8	2.16
Title boost	"Changelog" does not contain "memoria"	0
PageRank boost	Medium rank, normalized = 0.35	+0.44
Proximity boost	Distance 1 (linked from MEMORY.md)	+0.90
Total		3.50

The Memory Index page wins decisively due to high BM25, title match, and zero-distance proximity.

Index Lifecycle

flowchart TD
    A[New WikiCorpus] -->|first searchWiki call| B[buildSearchIndex]
    B --> C[Tokenize all pages]
    C --> D[Compute document frequencies]
    D --> E[Compute average document length]
    E --> F[Cache via WeakMap]
    F --> G[SearchIndex ready]
    G -->|searchWiki called| H[Tokenize query]
    H --> I[Score all documents]
    I --> J[Sort results]
    J --> K[Apply suppression]
    K --> L[Return WikiSearchResult[]]

    M[New corpus instance] -->|WeakMap key changes| N[Old index eligible for GC]
    N --> A

The WeakMap caching means:

The index is built once per corpus instance
When the corpus is replaced (new commit SHA, new snapshot), a new index is built
Old indices are garbage-collected when no references to the old corpus remain

Limitations

No fuzzy matching: The BM25 index requires exact token matches after accent folding. Typos are not tolerated.
No phrase queries: Multi-word queries are treated as independent terms. The phrase "unit distance" is scored as the sum of "unit" and "distance" individually.
No stemming: "pesquisando" and "pesquisa" are different tokens. Portuguese stemming is not applied.
No field boosting at query time: The title, description, and body are concatenated into a single searchable text. Field-level boosting (e.g., title matches count 2x) happens only through the explicit title boost component.
Proximity requires focus: The proximity boost only activates when a focusPath is provided (searching from a document page). Home page and standalone search have no proximity signal.

wikifita-site-pagerank -- PageRank algorithm that feeds the pagerankBoost
wikifita-site-graph-construction -- Link graph used for BFS proximity
wikifita-site-corpus-pipeline -- Corpus building where the search index is derived
wikifita-site-architecture -- Full technical architecture
wikifita-site-llm-integration -- LLM endpoints (no search, but related access patterns)

Search System Deep-Dive

Architecture Overview

Search Index Construction

Document Assembly

Tokenization

Index Structure

Document Frequency

Average Document Length

BM25 Scoring

Parameters

BM25 Formula

IDF Calculation

Term Frequency Saturation

Score Composition

Component Breakdown

Title Boost

PageRank Boost

Proximity Boost

Graph Distance (BFS)

Graph Construction for BFS

BFS Algorithm

Properties

Performance

Query Processing

Tokenization

Multi-Term Queries

Result Ranking

Result Object

Suppression Rules

Search API

Parameters

Response

Response Headers

Scoring Example

Query Tokenization

Candidate: memorias/MEMORY.md (Memory Index)

Candidate: wiki/log.md (Changelog)

Index Lifecycle

Limitations

Related Pages

Candidate: `memorias/MEMORY.md` (Memory Index)

Candidate: `wiki/log.md` (Changelog)