Search engines and vector databases

const DOCS: Record<string, string> = {
  d1: "cheap flight deals to paris",
  d2: "low-cost airfare for summer trips",
  d3: "error E1234 when booking a flight",
  d4: "hotel prices in paris",
  d5: "fix payment error on checkout",
};

// Toy 3-number embeddings: [travel, price, error]. Real models output hundreds of numbers learned from text.
const EMBED: Record<string, number[]> = {
  cheap: [0, 1, 0], "low-cost": [0, 1, 0], deals: [0, 0.8, 0], prices: [0, 0.9, 0],
  flight: [1, 0, 0], airfare: [0.9, 0.3, 0], trips: [0.8, 0, 0], hotel: [0.4, 0.2, 0], paris: [0.3, 0, 0],
  booking: [0.5, 0, 0], error: [0, 0, 1], fix: [0, 0, 0.6], payment: [0, 0.4, 0.3], checkout: [0, 0.3, 0.2],
};

const words = (text: string) => text.toLowerCase().split(" ");
const byScore = (scores: Map<string, number>) =>
  [...scores.keys()].sort((a, b) => scores.get(b)! - scores.get(a)! || (a < b ? -1 : 1));

// An inverted index scores documents that contain the query's words, rarer words counting more (idf).
function keywordRank(query: string): string[] {
  const scores = new Map<string, number>();
  for (const [doc, text] of Object.entries(DOCS)) {
    const w = words(text);
    for (const term of words(query)) {
      if (!w.includes(term)) continue;
      const df = Object.values(DOCS).filter((t) => words(t).includes(term)).length;
      scores.set(doc, (scores.get(doc) ?? 0) + Math.log(1 + Object.keys(DOCS).length / df));
    }
  }
  return byScore(scores);
}

function vector(text: string): number[] {
  const known = words(text).filter((w) => w in EMBED).map((w) => EMBED[w]);
  return known.length ? [0, 1, 2].map((i) => known.reduce((s, v) => s + v[i], 0) / known.length) : [0, 0, 0];
}

function cosine(a: number[], b: number[]): number {
  const na = Math.sqrt(a.reduce((s, x) => s + x * x, 0)), nb = Math.sqrt(b.reduce((s, x) => s + x * x, 0));
  return na && nb ? a.reduce((s, x, i) => s + x * b[i], 0) / (na * nb) : 0;
}

// Vector search ranks every document by how close its meaning is, whether or not words match.
function vectorRank(query: string, k = 3): string[] {
  const q = vector(query);
  return byScore(new Map(Object.entries(DOCS).map(([doc, text]) => [doc, cosine(q, vector(text))]))).slice(0, k);
}

// Reciprocal rank fusion: add 1 / (60 + rank) from each list, so documents near the top of either list rise.
function hybrid(query: string, k = 3): string[] {
  const fused = new Map<string, number>();
  for (const ranking of [keywordRank(query), vectorRank(query, Object.keys(DOCS).length)]) {
    ranking.forEach((doc, i) => fused.set(doc, (fused.get(doc) ?? 0) + 1 / (60 + i + 1)));
  }
  return byScore(fused).slice(0, k);
}

for (const query of ["cheap flight", "low-cost airfare", "error E1234"]) {
  console.log(`"${query}"`);
  console.log("  keyword:", keywordRank(query).join(", ") || "(no matches)");
  console.log("  vector: ", vectorRank(query).join(", "));
  console.log("  hybrid: ", hybrid(query).join(", "));
}

import java.util.*;
import java.util.stream.*;

public class Main {
    static final Map<String, String> DOCS = new LinkedHashMap<>();
    static final Map<String, double[]> EMBED = new HashMap<>();

    static {
        DOCS.put("d1", "cheap flight deals to paris");
        DOCS.put("d2", "low-cost airfare for summer trips");
        DOCS.put("d3", "error E1234 when booking a flight");
        DOCS.put("d4", "hotel prices in paris");
        DOCS.put("d5", "fix payment error on checkout");
        // Toy 3-number embeddings: [travel, price, error]. Real models output hundreds of numbers learned from text.
        Object[][] e = {{"cheap", 0, 1, 0}, {"low-cost", 0, 1, 0}, {"deals", 0, .8, 0}, {"prices", 0, .9, 0},
            {"flight", 1, 0, 0}, {"airfare", .9, .3, 0}, {"trips", .8, 0, 0}, {"hotel", .4, .2, 0}, {"paris", .3, 0, 0},
            {"booking", .5, 0, 0}, {"error", 0, 0, 1}, {"fix", 0, 0, .6}, {"payment", 0, .4, .3}, {"checkout", 0, .3, .2}};
        for (Object[] r : e) EMBED.put((String) r[0], new double[] {((Number) r[1]).doubleValue(), ((Number) r[2]).doubleValue(), ((Number) r[3]).doubleValue()});
    }

    static List<String> words(String text) { return Arrays.asList(text.toLowerCase().split(" ")); }

    static List<String> byScore(Map<String, Double> scores) {
        return scores.keySet().stream().sorted(Comparator.comparing((String d) -> -scores.get(d)).thenComparing(d -> d)).collect(Collectors.toList());
    }

    // An inverted index scores documents that contain the query's words, rarer words counting more (idf).
    static List<String> keywordRank(String query) {
        Map<String, Double> scores = new HashMap<>();
        DOCS.forEach((doc, text) -> {
            for (String term : words(query)) {
                if (!words(text).contains(term)) continue;
                long df = DOCS.values().stream().filter(t -> words(t).contains(term)).count();
                scores.merge(doc, Math.log(1 + (double) DOCS.size() / df), Double::sum);
            }
        });
        return byScore(scores);
    }

    static double[] vector(String text) {
        List<double[]> known = words(text).stream().filter(EMBED::containsKey).map(EMBED::get).collect(Collectors.toList());
        double[] v = new double[3];
        if (known.isEmpty()) return v;
        for (int i = 0; i < 3; i++) { double s = 0; for (double[] k : known) s += k[i]; v[i] = s / known.size(); }
        return v;
    }

    static double cosine(double[] a, double[] b) {
        double na = 0, nb = 0, dot = 0;
        for (double x : a) na += x * x;
        for (double x : b) nb += x * x;
        for (int i = 0; i < 3; i++) dot += a[i] * b[i];
        na = Math.sqrt(na); nb = Math.sqrt(nb);
        return na != 0 && nb != 0 ? dot / (na * nb) : 0;
    }

    // Vector search ranks every document by how close its meaning is, whether or not words match.
    static List<String> vectorRank(String query, int k) {
        double[] q = vector(query);
        Map<String, Double> scores = new HashMap<>();
        DOCS.forEach((doc, text) -> scores.put(doc, cosine(q, vector(text))));
        return byScore(scores).subList(0, k);
    }

    // Reciprocal rank fusion: add 1 / (60 + rank) from each list, so documents near the top of either list rise.
    static List<String> hybrid(String query, int k) {
        Map<String, Double> fused = new HashMap<>();
        for (List<String> ranking : List.of(keywordRank(query), vectorRank(query, DOCS.size()))) {
            for (int i = 0; i < ranking.size(); i++) fused.merge(ranking.get(i), 1.0 / (60 + i + 1), Double::sum);
        }
        return byScore(fused).subList(0, k);
    }

    public static void main(String[] args) {
        for (String query : List.of("cheap flight", "low-cost airfare", "error E1234")) {
            System.out.println("\"" + query + "\"");
            List<String> kw = keywordRank(query);
            System.out.println("  keyword: " + (kw.isEmpty() ? "(no matches)" : String.join(", ", kw)));
            System.out.println("  vector:  " + String.join(", ", vectorRank(query, 3)));
            System.out.println("  hybrid:  " + String.join(", ", hybrid(query, 3)));
        }
    }
}