Source code for web_search_helper.engine

"""The search, in Python: the reference twin of ``assets/search.php``.

The PHP file is what answers visitors; this module answers the same question
the same way, so that thresholds can be measured (``calibrate``) and the PHP
engine checked against it (``tests/test_php_parity.py``). Any change to the
ranking goes into BOTH, or the parity test fails.

Three signals, two engines, one verdict:

- **words**: BM25 (k1 = 1.5, b = 0.75) with a conjunctive pass first (if some
  passages contain every word of the question, only they compete), a
  coverage² weight otherwise, and a timid typo tolerance (a word is replaced
  by its neighbours only when it is absent from the corpus);
- **meaning**: the cosine of each passage's best window, and the cosine of the
  best section centroid;
- **fusion**: reciprocal rank fusion of the two rankings (k = 60);
- **verdict**: answer only if one of three routes says the corpus treats the
  question; otherwise return nothing at all.
"""

from __future__ import annotations

import math
import re
import unicodedata

import numpy as np

from .index import Index
from .text import tokenize


[docs] def max_typos(w: str) -> int: return 0 if len(w) < 4 else (1 if len(w) < 7 else 2)
[docs] def within(a: str, b: str, budget: int) -> int: """Levenshtein distance, or ``budget + 1`` as soon as it is exceeded. >>> within("elefant", "elephant", 2), within("art", "zzzzzz", 1) (2, 2) """ if abs(len(a) - len(b)) > budget: return budget + 1 prev = list(range(len(b) + 1)) for i in range(1, len(a) + 1): cur = [i] + [0] * len(b) best = i for j in range(1, len(b) + 1): cost = 0 if a[i - 1] == b[j - 1] else 1 cur[j] = min(prev[j] + 1, cur[j - 1] + 1, prev[j - 1] + cost) best = min(best, cur[j]) if best > budget: return budget + 1 prev = cur return prev[-1]
def _by_length(idx: Index) -> dict[int, list[str]]: cache = getattr(idx, "_by_length", None) if cache is None: cache = {} for w in idx.words: cache.setdefault(len(w), []).append(w) idx._by_length = cache return cache
[docs] def expand_terms(q_terms: list[str], idx: Index) -> list[list[tuple[str, float]]]: """One group per question word: the word itself, or up to three neighbours. Neighbours rank by corpus frequency over (1 + distance)², and keep only those weighing at least a quarter of the best. A word unknown even from afar keeps an EMPTY group: it still counts against coverage and blocks the conjunctive pass, so an off-topic question does not shrink to the one word the corpus happens to use. """ groups = [] for t in q_terms: if t in idx.postings: groups.append([(t, 1.0)]) continue budget = max_typos(t) cands = [] if budget: by_len = _by_length(idx) for n in range(len(t) - budget, len(t) + budget + 1): for w in by_len.get(n, []): d = within(t, w, budget) if d <= budget: cands.append((w, d, len(idx.postings[w]) / ((1 + d) ** 2))) if not cands: groups.append([]) continue cands.sort(key=lambda c: -c[2]) floor = cands[0][2] / 4 groups.append([(w, 1 / (1 + d)) for w, d, r in cands if r >= floor][:3]) return groups
[docs] def lexical(q: str, idx: Index) -> dict: q_terms = list(dict.fromkeys(tokenize(q, idx.stop))) typed = len(q.split()) pool_k = idx.meta["ranking"]["pool_k"] if not q_terms: return {"ranked": [], "terms": [], "best": 0.0, "conj": False, "df1": 0, "typed": typed} groups = expand_terms(q_terms, idx) G, N = len(groups), len(idx.passages) tf: dict[int, list[float]] = {} cands: list[int] = [] for gi, g in enumerate(groups): for w, weight in g: for i, c in idx.postings.get(w, []): if i not in tf: tf[i] = [0.0] * G cands.append(i) tf[i][gi] += c * weight df = [sum(1 for i in cands if tf[i][gi]) for gi in range(G)] idf = [math.log(1 + (N - d + 0.5) / (d + 0.5)) for d in df] k1, b, avg = 1.5, 0.75, idx.meta["avg_len"] conj, union = [], [] for i in cands: s, matched = 0.0, 0 for gi in range(G): x = tf[i][gi] if not x: continue matched += 1 s += idf[gi] * (x * (k1 + 1)) / (x + k1 * (1 - b + b * idx.lengths[i] / avg)) cov = matched / G (conj if matched == G else union).append((s * cov * cov, i)) pool = conj or union pool.sort(key=lambda e: (-e[0], e[1])) return { "ranked": [i for _, i in pool[:pool_k]], "terms": [w for g in groups for w, _ in g], "best": pool[0][0] if pool else 0.0, "conj": bool(conj), "df1": df[0] if G == 1 else 0, "typed": typed, }
[docs] def semantic(qv: np.ndarray, idx: Index) -> dict: pool_k = idx.meta["ranking"]["pool_k"] dots = idx.vectors.astype(np.float64) @ qv.astype(np.float64) best = np.array([dots[a : a + len(p["o"])].max() for a, p in zip(idx.first_vec, idx.passages)]) order = sorted(range(len(best)), key=lambda i: -best[i]) sec = idx.centroids.astype(np.float64) @ qv.astype(np.float64) return { "ranked": order[:pool_k], "top": float(best[order[0]]), "sectop": float(sec.max()) if len(sec) else -1.0, }
[docs] def sure_enough(kw: dict, sem: dict | None, th: dict) -> bool: """The verdict: three routes in OR, because none suffices everywhere. - one typed word: only its PRESENCE decides (it must appear in at least ``df_min`` passages); its embedding is too poor to judge; - meaning: best window ≥ ``sem_min`` AND best section ≥ ``sec_min``; - words: every word found in one passage AND its BM25 ≥ ``lex_min``. """ if not kw["terms"]: return False if kw["typed"] == 1: return kw["df1"] >= th["df_min"] if sem is not None and sem["top"] >= th["sem_min"] and sem["sectop"] >= th["sec_min"]: return True return kw["conj"] and kw["best"] >= th["lex_min"]
[docs] def rrf(a: list[int], b: list[int], k: int, top: int) -> list[int]: scores: dict[int, float] = {} for ranking in (a, b): for r, i in enumerate(ranking): scores[i] = scores.get(i, 0.0) + 1 / (k + r + 1) return [i for i, _ in sorted(scores.items(), key=lambda e: -e[1])][:top]
def _starts_upper(s: str) -> bool: # Twin of PHP's /^[«"“(]*[\p{Lu}\p{Lt}0-9]/u. s = s.lstrip('«"“(') return bool(s) and (unicodedata.category(s[0]) in ("Lu", "Lt") or s[0] in "0123456789") #: TeX formulas an excerpt must never cut: display $$…$$ and \[…\], inline \(…\). MATH = re.compile(r"\$\$.*?\$\$|\\\[.*?\\\]|\\\(.*?\\\)", re.DOTALL) def _outside_math(spans: list[tuple[int, int]], start: int, end: int) -> tuple[int, int]: # Twin of PHP's wsh_outside_math: a bound inside a formula moves out of it, # the start back to its opening, the end on past its closing, so the page # never receives half a formula it cannot typeset. for a, b in spans: if a < start < b: start = a if a < end < b: end = b return start, end
[docs] def excerpt(i: int, qv: np.ndarray | None, terms: list[str], idx: Index) -> dict: """Two windows of passage ``i``, snapped to sentence boundaries. The best window and its better neighbour: a few sentences, never the whole passage. The start moves forward to the first whole sentence; the end moves forward to the end of the current sentence (at most 400 characters). Window bounds and cosines travel with the excerpt: the page needs them to compose its extractive answer. """ p = idx.passages[i] t, o = p["t"], p["o"] n, nf = len(t), len(o) if qv is not None: a = idx.first_vec[i] note = [float(x) for x in idx.vectors[a : a + nf].astype(np.float64) @ qv.astype(np.float64)] else: tset = set(terms) note = [] for f in range(nf): start = o[f - 1] if f else 0 note.append(float(sum(1 for w in tokenize(t[start : o[f]]) if w in tset))) m = note.index(max(note)) lo = hi = m if nf > 1: if m == 0: hi = 1 elif m == nf - 1 or note[m - 1] > note[m + 1]: lo = m - 1 else: hi = m + 1 spans = [m.span() for m in MATH.finditer(t)] start, end = _outside_math(spans, o[lo - 1] if lo else 0, o[hi]) if start > 0: for mm in re.finditer(r"[.!?…]\s+", t[start:end]): if _starts_upper(t[start + mm.end() :]): if mm.end() < end - start: start += mm.end() break if end < n: tail = t[end : end + 400] for mm in re.finditer(r"[.!?…]", tail): rest = tail[mm.end() :] if not rest.strip() or (rest[:1].isspace() and _starts_upper(rest.lstrip())): end += mm.end() break start, end = _outside_math(spans, start, end) bounds = [max(0, min(o[f], end) - start) for f in range(lo, hi + 1)] bounds[-1] = end - start return { "doc": p["c"], "section": p["s"], "url": p.get("u", ""), "meta": p.get("m", {}), "text": t[start:end], "o": bounds, "cos": [note[f] if qv is not None else 0.0 for f in range(lo, hi + 1)], "before": start > 0, "after": end < n, }