search.mjs

Functions

Imports

It imports no other module of this repo. Imported by index.mjs.

Source

1/** Reciprocal rank fusion constant. See fuse(). */
2export const RRF_K = 60;
3
4/**
5 * Every token is quoted: fts5 has its own query language, so unquoted input breaks on a hyphen and NEAR silently changes the
6 * meaning. Doubling embedded quotes is the whole escape.
7 *
8 * @param {string} token
9 * @returns {string}
10 */
11export function ftsLiteral(token) {
12  return `"${token.replace(/"/g, '""')}"`;
13}
14
15/**
16 * An FTS5 MATCH expression from already-split words and phrases, every one a literal, all ANDed.
17 *
18 * @param {{ terms: string[], phrases?: string[] }} parsed
19 * @param {boolean} [prefix] when true the LAST term also matches as a prefix, so "cloudf" finds "cloudflare" while someone is
20 *   still typing. Only the last term, because the earlier ones are complete words the moment a space follows them.
21 * @returns {string | null} null when there is nothing to match on
22 */
23export function toMatchExpression(parsed, prefix = false) {
24  /** @type {string[]} */
25  const parts = [];
26  for (const phrase of parsed.phrases ?? []) parts.push(ftsLiteral(phrase));
27  parsed.terms.forEach((term, i) => {
28    const isLast = i === parsed.terms.length - 1;
29    parts.push(prefix && isLast ? `${ftsLiteral(term)}*` : ftsLiteral(term));
30  });
31  if (parts.length === 0) return null;
32  return parts.join(" AND ");
33}
34
35/**
36 * Rank based, never score based: bm25 from two indexes with different tokenizers is not comparable on value. k = 60 is the
37 * original RRF paper's constant. ranks and contributions are parallel to sources.
38 *
39 * @template {{ uid: string }} T
40 * @param {T[][]} lists
41 * @param {number} [k]
42 * @returns {Array<{ item: T, score: number, sources: number[], ranks: number[], contributions: number[] }>}
43 */
44export function fuse(lists, k = RRF_K) {
45  /** @type {Map<string, { item: T, score: number, sources: number[], ranks: number[], contributions: number[] }>} */
46  const scores = new Map();
47
48  lists.forEach((list, listIndex) => {
49    list.forEach((item, i) => {
50      const rank = i + 1;
51      const contribution = 1 / (k + rank);
52      const existing = scores.get(item.uid);
53      if (existing) {
54        existing.score += contribution;
55        existing.sources.push(listIndex);
56        existing.ranks.push(rank);
57        existing.contributions.push(contribution);
58      } else {
59        scores.set(item.uid, { item, score: contribution, sources: [listIndex], ranks: [rank], contributions: [contribution] });
60      }
61    });
62  });
63
64  return [...scores.values()].sort((a, b) => b.score - a.score);
65}