DocMorph / docmorph /index.py
Shoufa Zhang
Deploy DocMorph & SeekMorph interactive Studio and 5-layer production benchmark
66227f0
Raw History Blame Contribute Delete
11.1 kB
"""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