"""Persistent hybrid search index (inverted-index BM25 + dense vector RRF) with CJK/English tokenization.""" from __future__ import annotations import json import math import re import threading from collections import Counter from dataclasses import dataclass from pathlib import Path from typing import Iterable from docmorph.parser import DocChunk _WORD_RE = re.compile(r"[A-Za-z0-9_]+") _CJK_RUN_RE = re.compile(r"[\u4e00-\u9fff]+") def tokenize_multilingual(text: str) -> list[str]: """Tokenize English words and CJK unigrams + bigrams.""" lowered = text.lower() tokens = _WORD_RE.findall(lowered) for run in _CJK_RUN_RE.findall(lowered): tokens.extend(list(run)) if len(run) > 1: tokens.extend(run[i : i + 2] for i in range(len(run) - 1)) return tokens @dataclass(frozen=True) class SearchHit: """Ranked search result with RRF score, BM25 score, and optional neighbor-expanded text.""" chunk: DocChunk score: float bm25_score: float expanded_content: str def format_citation(self, rank: int | None = None) -> str: prefix = f"[{rank}] " if rank is not None else "" return f"{prefix}{self.chunk.doc_id} ({self.chunk.breadcrumb_str}) [{self.chunk.kind}]\n{self.expanded_content}" class HybridIndex: """Thread-safe inverted-index BM25 + dense vector Reciprocal Rank Fusion (RRF) store.""" def __init__(self, rrf_k: int = 60, k1: float = 1.5, b: float = 0.75) -> None: self.rrf_k = max(1, int(rrf_k)) self.k1 = float(k1) self.b = float(b) self._lock = threading.RLock() self._chunks: dict[str, DocChunk] = {} self._embeddings: dict[str, tuple[float, ...]] = {} self._doc_lens: dict[str, int] = {} self._postings: dict[str, dict[str, int]] = {} self._total_dl: int = 0 def __len__(self) -> int: with self._lock: return len(self._chunks) @property def chunks(self) -> list[DocChunk]: with self._lock: return list(self._chunks.values()) def _unindex_chunk(self, chunk_id: str) -> None: old_len = self._doc_lens.pop(chunk_id, 0) self._total_dl = max(0, self._total_dl - old_len) empty_terms: list[str] = [] for term, plist in self._postings.items(): if chunk_id in plist: del plist[chunk_id] if not plist: empty_terms.append(term) for term in empty_terms: del self._postings[term] def add(self, chunk: DocChunk, embedding: list[float] | tuple[float, ...] | None = None) -> None: """Index or update a single DocChunk in O(|tokens|) time.""" with self._lock: if chunk.chunk_id in self._chunks: self._unindex_chunk(chunk.chunk_id) self._chunks[chunk.chunk_id] = chunk if embedding is not None: self._embeddings[chunk.chunk_id] = tuple(float(x) for x in embedding) tokens = tokenize_multilingual(f"{chunk.breadcrumb_str}\n{chunk.content}") tf = Counter(tokens) dl = len(tokens) self._doc_lens[chunk.chunk_id] = dl self._total_dl += dl for term, freq in tf.items(): self._postings.setdefault(term, {})[chunk.chunk_id] = freq def remove(self, chunk_id: str) -> bool: """Remove a chunk by ID from the index.""" with self._lock: if chunk_id not in self._chunks: return False del self._chunks[chunk_id] self._embeddings.pop(chunk_id, None) self._unindex_chunk(chunk_id) return True def remove_document(self, doc_id: str, namespace: str | None = None) -> int: """Remove all chunks belonging to doc_id (optionally scoped to namespace).""" with self._lock: to_delete = [ cid for cid, c in self._chunks.items() if c.doc_id == doc_id and (namespace is None or c.namespace == namespace) ] for cid in to_delete: self.remove(cid) return len(to_delete) def add_many( self, chunks: Iterable[DocChunk], embeddings: dict[str, list[float] | tuple[float, ...]] | None = None, ) -> int: count = 0 emb_map = embeddings or {} with self._lock: for chunk in chunks: self.add(chunk, embedding=emb_map.get(chunk.chunk_id)) count += 1 return count def search( self, query: str, *, top_k: int = 5, namespace: str | None = None, doc_id: str | None = None, query_embedding: list[float] | tuple[float, ...] | None = None, expand_window: int = 0, ) -> list[SearchHit]: """Search indexed chunks using inverted-index BM25 fused with optional dense vector similarity.""" with self._lock: if not self._chunks or top_k <= 0: return [] if namespace is None and doc_id is None: allowed_ids = set(self._chunks.keys()) else: allowed_ids = { cid for cid, c in self._chunks.items() if (namespace is None or c.namespace == namespace) and (doc_id is None or c.doc_id == doc_id) } if not allowed_ids: return [] n_docs = len(allowed_ids) if n_docs == len(self._chunks): avgdl = self._total_dl / max(1, n_docs) else: avgdl = sum(self._doc_lens.get(cid, 0) for cid in allowed_ids) / max(1, n_docs) q_tokens = tokenize_multilingual(query) bm25_scores: dict[str, float] = {cid: 0.0 for cid in allowed_ids} for q in q_tokens: plist = self._postings.get(q) if not plist: continue if n_docs == len(self._chunks): df = len(plist) else: df = sum(1 for cid in plist if cid in allowed_ids) if df == 0: continue idf = math.log(1.0 + (n_docs - df + 0.5) / (df + 0.5)) for cid, tf in plist.items(): if cid not in allowed_ids: continue dl = self._doc_lens.get(cid, 0) denom = tf + self.k1 * (1.0 - self.b + self.b * (dl / max(1.0, avgdl))) bm25_scores[cid] += idf * (tf * (self.k1 + 1.0)) / denom candidates = [self._chunks[cid] for cid in allowed_ids] bm25_ranked = sorted(candidates, key=lambda c: (bm25_scores[c.chunk_id], -c.chunk_index), reverse=True) rrf_scores: dict[str, float] = { c.chunk_id: 1.0 / (self.rrf_k + rank + 1) for rank, c in enumerate(bm25_ranked) } if query_embedding: q_norm = math.sqrt(sum(x * x for x in query_embedding)) or 1.0 vec_scores: dict[str, float] = {} for c in candidates: emb = self._embeddings.get(c.chunk_id) if emb and len(emb) == len(query_embedding): d_norm = math.sqrt(sum(x * x for x in emb)) or 1.0 vec_scores[c.chunk_id] = sum(a * b for a, b in zip(query_embedding, emb)) / (q_norm * d_norm) else: vec_scores[c.chunk_id] = -1.0 vec_ranked = sorted(candidates, key=lambda c: vec_scores[c.chunk_id], reverse=True) for rank, c in enumerate(vec_ranked): rrf_scores[c.chunk_id] += 1.0 / (self.rrf_k + rank + 1) if not query_embedding: matched = [c for c in candidates if bm25_scores[c.chunk_id] > 0.0] else: matched = [ c for c in candidates if bm25_scores[c.chunk_id] > 0.0 or vec_scores.get(c.chunk_id, -1.0) > 0.0 ] if not matched: return [] final_chunks = sorted( matched, key=lambda c: (rrf_scores[c.chunk_id], bm25_scores[c.chunk_id], -c.chunk_index), reverse=True, )[:top_k] by_doc_idx: dict[tuple[str, str, int], DocChunk] = { (c.namespace, c.doc_id, c.chunk_index): c for c in self._chunks.values() } hits: list[SearchHit] = [] for c in final_chunks: if expand_window > 0: window_parts: list[str] = [] for idx_offset in range(-expand_window, expand_window + 1): neighbor = by_doc_idx.get((c.namespace, c.doc_id, c.chunk_index + idx_offset)) if neighbor is not None and neighbor.section_path == c.section_path: window_parts.append(neighbor.content) expanded = "\n\n".join(window_parts) if window_parts else c.content else: expanded = c.content hits.append( SearchHit( chunk=c, score=round(rrf_scores[c.chunk_id], 6), bm25_score=round(bm25_scores[c.chunk_id], 4), expanded_content=expanded, ) ) return hits def save(self, path: str | Path) -> None: """Persist the index atomically to a JSONL file.""" with self._lock: dest = Path(path) dest.parent.mkdir(parents=True, exist_ok=True) tmp_path = dest.with_suffix(dest.suffix + ".tmp") with tmp_path.open("w", encoding="utf-8") as f: for cid, chunk in self._chunks.items(): row = chunk.to_dict() if cid in self._embeddings: row["embedding"] = list(self._embeddings[cid]) f.write(json.dumps(row, ensure_ascii=False) + "\n") tmp_path.replace(dest) @classmethod def load(cls, path: str | Path) -> HybridIndex: """Load an index from a JSONL file, skipping corrupted partial lines.""" index = cls() src = Path(path) if not src.is_file(): raise FileNotFoundError(f"Index file not found: {src}") for raw_line in src.read_text(encoding="utf-8").splitlines(): line = raw_line.strip() if not line: continue try: row = json.loads(line) except json.JSONDecodeError: continue if not isinstance(row, dict) or "chunk_id" not in row or "content" not in row: continue emb = row.pop("embedding", None) chunk = DocChunk.from_dict(row) index.add(chunk, embedding=emb if isinstance(emb, list) else None) return index