Full text search with a preprocessed query
GitHub: search_rrf_substitutions.py Related:
- Querying for tmux keybinding with Reciprocal Rank Fusion
- Select search candidates with FTS5, then rank by semantic similarity
- Rank tmux description FTS5 matches with BM25
The code below is using the RRF approach outlined in
Querying for tmux keybinding with Reciprocal Rank Fusion
. What’s different from that code is that before passing the query to the search_bm25 function, the query is preproceed to remove words that are in a “stop words” list and to substitute words that are in a substitutions list.
The words in the stop-words and substitutions list haven’t had a lot of thought put into them. This is just an example of how these features could be implemented.
"""Combine FTS5 term substitutions and semantic rankings with RRF."""
import argparse
import re
import sqlite3
from dataclasses import dataclass
from pathlib import Path
from chromadb.errors import ChromaError
from search_bm25 import search as search_bm25
from search_chroma import search as search_chroma
STOP_WORDS = {
"a",
"an",
"and",
"are",
"as",
"at",
"be",
"by",
"for",
"from",
"in",
"is",
"it",
"of",
"on",
"or",
"that",
"the",
"to",
"was",
"with",
}
# Exact whole-word replacements, looked up case-insensitively.
# Values replace the original FTS terms; they do not expand the query with synonyms.
SUBSTITUTIONS = {
"close": "kill",
"bigger": "resize",
"smaller": "resize",
"2": "two",
"go": "move",
}
@dataclass
class Result:
key: str
description: str
score: float = 0.0
fts_rank: int | None = None
semantic_rank: int | None = None
def fts_query(query: str) -> str:
"""Remove stop words, substitute terms, then OR-join them for FTS5."""
words = re.findall(r"[^\W_]+", query, flags=re.UNICODE)
if not words:
raise ValueError("Enter at least one word to search for.")
# Match stop words case-insensitively, preserving the remaining words.
# Filtering affects the FTS query only, not the index or semantic query.
words = [word for word in words if word.casefold() not in STOP_WORDS]
# Apply substitutions only here, after stop-word filtering and before
# FTS5 tokenization/stemming. Unmapped words retain their original spelling.
words = [SUBSTITUTIONS.get(word.casefold(), word) for word in words]
# Quote terms so user-supplied words cannot become FTS operators.
return " OR ".join(f'"{word}"' for word in words)
def fuse(
lexical: list[tuple[str, str, float]],
semantic: list[tuple[str, str, float]],
k: int = 60,
) -> list[Result]:
"""Fuse ranked lists by key; use positions, not the original scores."""
if k < 0:
raise ValueError("RRF k must be nonnegative.")
combined: dict[str, Result] = {}
for rank, (key, description, _) in enumerate(lexical, start=1):
result = combined.setdefault(key, Result(key, description))
result.fts_rank = rank
result.score += 1 / (k + rank)
for rank, (key, description, _) in enumerate(semantic, start=1):
kkresult = combined.setdefault(key, Result(key, description))
result.semantic_rank = rank
result.score += 1 / (k + rank)
# Missing from a list means zero contribution. Higher fused scores win.
# Case-sensitive key ordering makes exact score ties deterministic.
return sorted(combined.values(), key=lambda result: (-result.score, result.key))
def search(
database: Path,
chroma_path: Path,
query: str,
collection_name: str = "tmux-key-bindings",
results: int = 5,
candidates: int = 20,
k: int = 60,
) -> list[Result]:
"""Retrieve independently, fuse their top candidates, then limit output."""
if results < 1 or candidates < 1:
raise ValueError("Results and candidates must be positive.")
if k < 0:
raise ValueError("RRF k must be nonnegative.")
lexical_query = fts_query(query)
# MATCH cannot accept an empty expression. If every word was excluded,
# skip lexical retrieval and let the semantic list contribute on its own.
lexical = search_bm25(database, lexical_query)[:candidates] if lexical_query else []
# The original query goes to the embedding model, without OR rewriting.
# Semantic retrieval runs even when FTS5 returns no matches.
semantic = search_chroma(chroma_path, query, collection_name, candidates)
return fuse(lexical, semantic, k)[:results]
def main() -> None:
parser = argparse.ArgumentParser(description=__doc__)
parser.add_argument("query", help="Text to search with both retrieval methods")
parser.add_argument(
"--database", type=Path, default=Path("tmux_key_bindings.sqlite3")
)
parser.add_argument("--chroma", type=Path, default=Path("data/chroma"))
parser.add_argument("--collection", default="tmux-key-bindings")
parser.add_argument(
"--results", type=int, default=5, help="Final results (default: 5)"
)
parser.add_argument(
"--candidates",
type=int,
default=20,
help="Maximum entries from each ranked list to fuse (default: 20)",
)
parser.add_argument("--k", type=int, default=60, help="RRF constant (default: 60)")
args = parser.parse_args()
try:
rows = search(
args.database,
args.chroma,
args.query,
args.collection,
args.results,
args.candidates,
args.k,
)
except (sqlite3.Error, ChromaError, ValueError) as error:
parser.exit(1, f"Search failed: {error}\n")
lexical_query = fts_query(args.query)
print(f"FTS5 query: {lexical_query or '(skipped: all terms are stop words)'}")
if not rows:
print("No results found.")
return
print("RRF score\tFTS rank\tSemantic rank\tKey\tDescription")
for row in rows:
print(
f"{row.score:.9g}\t{row.fts_rank or '-'}\t"
f"{row.semantic_rank or '-'}\t{row.key}\t{row.description}"
)
if __name__ == "__main__":
main()
Do stop-words and word substitutions improve the results? #
The word “to” gets removed from “go to window 3”. For what are probably not great reasons, the presence of the word “to” improved the results when the same query was run without stop-words being removed:
find-command ❯ uv run python search_rrf_substitutions.py "go to window 3"
FTS5 query: "move" OR "window" OR "3"
RRF score FTS rank Semantic rank Key Description
0.031099325 8 1 c Create a new window.
0.031099325 1 8 l Move to the previously selected window.
0.0310096154 4 5 M-n Move to the next window with a bell or activity marker.
0.0305361305 5 6 M-p Move to the previous window with a bell or activity marker.
0.0304147465 10 2 n Change to the next window.
The same query without preprocessing (“to” was useful here):
find-command ❯ uv run python search_rrf.py "go to window 3"
FTS5 query: "go" OR "to" OR "window" OR "3"
RRF score FTS rank Semantic rank Key Description
0.0322580645 2 2 n Change to the next window.
0.0320184426 1 4 0 to 9 Select windows 0 to 9.
0.0317460317 3 3 p Change to the previous window.
0.0303308824 4 8 l Move to the previously selected window.
0.0300904977 8 5 M-n Move to the next window with a bell or activity marker.
“Change the size of the pane” does’t have great results. I’m expecting one of the “Resize the current pane…” commands:
find-command ❯ uv run python search_rrf_substitutions.py "change the size of the pane"
FTS5 query: "change" OR "size" OR "pane"
RRF score FTS rank Semantic rank Key Description
0.0312805474 6 2 } Swap the current pane with the next pane.
0.0310096154 5 4 { Swap the current pane with the previous pane.
0.030798389 3 7 Up, Down, Left, Right Change to the pane above, below, to the left, or to the right of the current pane.
0.0296703297 10 5 * Create a new floating pane.
0.0296312555 7 8 M Clear the marked pane.
I’ll set the --results param to a bigger value to see what the top ranked semantic result is. The top semantic result is “Split the current pane into two, top and bottom”. The top FTS5 result is “Change to the next window”. Despite not getting great results for the query, the FTS and semantic results are cancelling themselves in an appropriate way.
find-command ❯ uv run python search_rrf_substitutions.py "change the size of the pane" --results 25
FTS5 query: "change" OR "size" OR "pane"
RRF score FTS rank Semantic rank Key Description
0.0312805474 6 2 } Swap the current pane with the next pane.
0.0310096154 5 4 { Swap the current pane with the previous pane.
0.030798389 3 7 Up, Down, Left, Right Change to the pane above, below, to the left, or to the right of the current pane.
0.0296703297 10 5 * Create a new floating pane.
0.0296312555 7 8 M Clear the marked pane.
0.0293804556 17 1 " Split the current pane into two, top and bottom.
0.0292360222 11 6 ; Move to the previously active pane.
0.0287828947 4 16 m Mark the current pane (see select-pane -m).
0.0287784679 9 10 x Kill the current pane.
0.0286935287 18 3 % Split the current pane into two, left and right.
0.0277777778 12 12 z Toggle zoom state of the current pane.
0.0276506484 16 9 M-o Rotate the panes in the current window backwards.
0.0273972603 13 13 C-o Rotate the panes in the current window forwards.
0.0273641102 8 19 q Briefly display pane indexes.
0.027027027 14 14 ! Break the current pane out of the window.
0.0267427349 19 11 C-Up, C-Down, C-Left, C-Right Resize the current pane in steps of one cell.
0.0263203463 15 17 o Select the next pane in the current window.
0.0258333333 20 15 M-Up, M-Down, M-Left, M-Right Resize the current pane in steps of five cells.
0.0163934426 1 - n Change to the next window.
0.0161290323 2 - p Change to the previous window.
0.0128205128 - 18 M-1 to M-7 Arrange panes in one of the seven preset layouts: even-horizontal, even-vertical, main-horizontal, main-horizontal-mirrored, main-vertical, main-vertical-mirrored, or tiled.