--- name: wikifita-site-search-system type: analysis title: "Search System Deep-Dive" description: "BM25 search with PageRank boosting, title matching, and graph-proximity scoring: index construction, tokenization, scoring formula, and the BFS distance computation." tags: [wikifita, search, bm25, pagerank, proximity, bfs, scoring] timestamp: 2026-07-21 --- # 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 ```mermaid 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`. 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é" -> "Café" (decomposed) 2. Strip diacritics (Unicode combining marks, category \p{M}) "Café" -> "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 ```typescript type SearchIndex = { documents: SearchDocument[]; // One per page documentFrequency: Map; // 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; // 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: ```typescript function buildUndirectedAdjacency(corpus: WikiCorpus): Map { const adj = new Map(); 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 ```typescript function graphDistance(start: string, target: string, adjacency: Map): number { if (start === target) return 0; const visited = new Set([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 ```typescript 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=&limit=<1-50>&focus= ``` ### 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 ```json { "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 ```mermaid 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 1. **No fuzzy matching**: The BM25 index requires exact token matches after accent folding. Typos are not tolerated. 2. **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. 3. **No stemming**: "pesquisando" and "pesquisa" are different tokens. Portuguese stemming is not applied. 4. **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. 5. **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. --- ## Related Pages - [[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)