Show similar articles

"""
Related articles from tag overlap, weighted by how rare each tag is.

Rung N0. Standard library, deterministic, and computed once for the whole
corpus instead of on every page view: the neighbours of an article do not
depend on who is reading it, so no reader should ever wait for this.

Counting shared tags is the obvious version, and it is the wrong one. A tag
every article carries says nothing about any of them; a tag three articles
carry says almost everything about those three. Weighting each tag by its
rarity is the whole difference between a useful block and one that files the
site announcement next to every article on the site.
"""

import math
from collections import Counter


def tag_weights(articles: list[dict]) -> dict[str, float]:
    """
    Inverse document frequency of every tag in the corpus.

    log(corpus size / tag count) is exactly zero for a tag carried by every
    article. That is the point, not a rounding accident: such a tag must not
    create any similarity at all.
    """
    counts = Counter(tag for article in articles for tag in set(article["tags"]))
    return {tag: math.log(len(articles) / count) for tag, count in counts.items()}


def _norm(vector: dict[str, float]) -> float:
    return math.sqrt(sum(weight * weight for weight in vector.values()))


def similarity(first_tags, second_tags, weights: dict[str, float]) -> float:
    """Cosine between two tag sets, each weighted by tag rarity."""
    first = {tag: weights.get(tag, 0.0) for tag in set(first_tags)}
    second = {tag: weights.get(tag, 0.0) for tag in set(second_tags)}
    shared = sum(first[tag] * second[tag] for tag in first.keys() & second.keys())
    norms = _norm(first) * _norm(second)
    # An article carrying only universal tags has a null vector, and no
    # neighbours. Saying nothing is the honest answer here.
    return shared / norms if norms else 0.0


def build_neighbour_table(articles: list[dict], k: int = 5, minimum: float = 0.0) -> dict:
    """
    Return `{article id: [(neighbour id, score), ...]}`, best neighbour first.

    Built offline, for the whole corpus at once, when an article is published
    or retagged. Rendering the block on a page is then a lookup in this table,
    never a search.
    """
    weights = tag_weights(articles)
    table = {}
    for article in articles:
        neighbours = []
        for other in articles:
            if other["id"] == article["id"]:
                continue
            score = round(similarity(article["tags"], other["tags"], weights), 3)
            if score > minimum:
                neighbours.append((other["id"], score))
        # Ties broken by identifier, so that two builds give the same page.
        neighbours.sort(key=lambda neighbour: (-neighbour[1], neighbour[0]))
        table[article["id"]] = neighbours[:k]
    return table

/**
 * Related articles from tag overlap, weighted by how rare each tag is.
 *
 * Rung N0. No dependency, deterministic, and computed once for the whole
 * corpus instead of on every page view: the neighbours of an article do not
 * depend on who is reading it, so no reader should ever wait for this.
 *
 * Counting shared tags is the obvious version, and it is the wrong one. A tag
 * every article carries says nothing about any of them; a tag three articles
 * carry says almost everything about those three. Weighting each tag by its
 * rarity is the whole difference between a useful block and one that files
 * the site announcement next to every article on the site.
 */

/**
 * Inverse document frequency of every tag in the corpus.
 *
 * log(corpus size / tag count) is exactly zero for a tag carried by every
 * article. That is the point, not a rounding accident: such a tag must not
 * create any similarity at all.
 */
export function tagWeights(articles) {
  const counts = new Map();
  for (const article of articles) {
    for (const tag of new Set(article.tags)) counts.set(tag, (counts.get(tag) ?? 0) + 1);
  }
  const weights = new Map();
  for (const [tag, count] of counts) weights.set(tag, Math.log(articles.length / count));
  return weights;
}

function norm(vector) {
  return Math.hypot(...vector.values());
}

/** Cosine between two tag sets, each weighted by tag rarity. */
export function similarity(firstTags, secondTags, weights) {
  const vector = (tags) => new Map([...new Set(tags)].map((t) => [t, weights.get(t) ?? 0]));
  const first = vector(firstTags);
  const second = vector(secondTags);

  let shared = 0;
  for (const [tag, weight] of first) shared += weight * (second.get(tag) ?? 0);
  const norms = norm(first) * norm(second);
  // An article carrying only universal tags has a null vector, and no
  // neighbours. Saying nothing is the honest answer here.
  return norms ? shared / norms : 0;
}

/**
 * Return `{ [article id]: [[neighbour id, score], ...] }`, best first.
 *
 * Built offline, for the whole corpus at once, when an article is published
 * or retagged. Rendering the block on a page is then a lookup in this table,
 * never a search.
 */
export function buildNeighbourTable(articles, { k = 5, minimum = 0 } = {}) {
  const weights = tagWeights(articles);
  const table = {};
  for (const article of articles) {
    const neighbours = [];
    for (const other of articles) {
      if (other.id === article.id) continue;
      const score = Math.round(similarity(article.tags, other.tags, weights) * 1000) / 1000;
      if (score > minimum) neighbours.push([other.id, score]);
    }
    // Ties broken by identifier, so that two builds give the same page.
    neighbours.sort((a, b) => b[1] - a[1] || (a[0] < b[0] ? -1 : 1));
    table[article.id] = neighbours.slice(0, k);
  }
  return table;
}

"""
Related articles from the text itself: TF-IDF, then cosine similarity.

Rung N1. N0 only sees what someone remembered to tag. This reads the article,
and lets the corpus decide which words matter: a word appearing in every
article weighs almost nothing, which is the idea of N0 applied to vocabulary
instead of labels. Nobody has to maintain anything.

Still computed offline, once per corpus change, and it returns the same
neighbour table as N0. The page-rendering code does not change when you move
from one rung to the next, which is what makes the move cheap.
"""

from sklearn.feature_extraction.text import TfidfVectorizer
from sklearn.metrics.pairwise import linear_kernel


def article_text(article: dict) -> str:
    """
    The title counts twice.

    A word in a title is a stronger claim about the subject than the same word
    buried in the fourth paragraph, and repeating the title is the cheapest
    way to say so to a bag-of-words model.
    """
    return f"{article['title']} {article['title']} {article['body']}"


def build_neighbour_table(
    articles: list[dict],
    k: int = 5,
    minimum: float = 0.05,
    stop_words: list[str] | None = None,
) -> dict:
    """
    Return `{article id: [(neighbour id, score), ...]}`, best neighbour first.

    `stop_words` is a per-language list, so it belongs to the caller and not
    to this function. Without one the ranking still works, because a word in
    every article is downweighted anyway, but the floor has to do more of the
    job on a small corpus.

    `minimum` is that floor, not a knob to be tweaked until the block looks
    full: below it, two articles share ordinary words and nothing else, and
    showing no block beats showing a wrong one.
    """
    if len(articles) < 2:
        return {article["id"]: [] for article in articles}

    # Rows come out l2-normalised, so their dot product is already a cosine.
    vectoriser = TfidfVectorizer(stop_words=stop_words)
    matrix = vectoriser.fit_transform(article_text(a) for a in articles)
    scores = linear_kernel(matrix)

    table = {}
    for index, article in enumerate(articles):
        neighbours = [
            (other["id"], round(float(scores[index][position]), 3))
            for position, other in enumerate(articles)
            if position != index
        ]
        # Ties broken by identifier, so that two builds give the same page.
        neighbours = sorted(
            (n for n in neighbours if n[1] > minimum),
            key=lambda neighbour: (-neighbour[1], neighbour[0]),
        )
        table[article["id"]] = neighbours[:k]
    return table

/**
 * Related articles from the text itself: TF-IDF, then cosine similarity.
 *
 * Rung N1. N0 only sees what someone remembered to tag. This reads the
 * article, and lets the corpus decide which words matter: a word appearing in
 * every article weighs almost nothing, which is the idea of N0 applied to
 * vocabulary instead of labels. Nobody has to maintain anything.
 *
 * Written out rather than pulled from a library, because TF-IDF is a count, a
 * logarithm and a division. The weighting below is the standard smoothed one,
 * so this ranks a corpus exactly as the Python version does.
 */

// Runs of two or more letters, digits or underscores. A one-letter token
// carries no subject, and dropping it costs nothing.
const TOKEN = /[\p{L}\p{N}_]{2,}/gu;

export function tokenise(text, stopWords = new Set()) {
  return (text.toLowerCase().match(TOKEN) ?? []).filter((term) => !stopWords.has(term));
}

/** The title counts twice: a word in a title is a stronger claim. */
export function articleText(article) {
  return `${article.title} ${article.title} ${article.body}`;
}

/** One l2-normalised TF-IDF vector per document, as a Map of term to weight. */
export function vectorise(texts, stopWords = new Set()) {
  const documents = texts.map((text) => tokenise(text, stopWords));
  const appearances = new Map();
  for (const terms of documents) {
    for (const term of new Set(terms)) appearances.set(term, (appearances.get(term) ?? 0) + 1);
  }

  // Smoothed: as if one extra document held every term, so a term present
  // everywhere still has a defined weight instead of a division by zero.
  const idf = (term) => Math.log((1 + documents.length) / (1 + appearances.get(term))) + 1;

  return documents.map((terms) => {
    const vector = new Map();
    for (const term of terms) vector.set(term, (vector.get(term) ?? 0) + 1);
    for (const [term, count] of vector) vector.set(term, count * idf(term));
    const norm = Math.hypot(...vector.values());
    if (norm) for (const [term, weight] of vector) vector.set(term, weight / norm);
    return vector;
  });
}

/** Both vectors are unit length, so their dot product is the cosine. */
function cosine(first, second) {
  let total = 0;
  for (const [term, weight] of first) total += weight * (second.get(term) ?? 0);
  return total;
}

/**
 * Return `{ [article id]: [[neighbour id, score], ...] }`, best first.
 *
 * `stopWords` is a per-language list, so it belongs to the caller and not to
 * this function. Without one the ranking still works, because a word in every
 * article is downweighted anyway, but the floor has to do more of the job on
 * a small corpus.
 *
 * `minimum` is that floor, not a knob to be tweaked until the block looks
 * full: below it, two articles share ordinary words and nothing else, and
 * showing no block beats showing a wrong one.
 */
export function buildNeighbourTable(articles, { k = 5, minimum = 0.05, stopWords = [] } = {}) {
  if (articles.length < 2) return Object.fromEntries(articles.map((a) => [a.id, []]));

  const vectors = vectorise(articles.map(articleText), new Set(stopWords));
  const table = {};
  articles.forEach((article, index) => {
    const neighbours = [];
    articles.forEach((other, position) => {
      if (position === index) return;
      const score = Math.round(cosine(vectors[index], vectors[position]) * 1000) / 1000;
      if (score > minimum) neighbours.push([other.id, score]);
    });
    // Ties broken by identifier, so that two builds give the same page.
    neighbours.sort((a, b) => b[1] - a[1] || (a[0] < b[0] ? -1 : 1));
    table[article.id] = neighbours.slice(0, k);
  });
  return table;
}

"""
Related articles from self-hosted document embeddings.

Rung N2. N1 compares words. Two articles that cover the same subject with two
vocabularies, or in two languages, share no term and score exactly zero. An
encoder maps each article to a vector where meaning, not spelling, decides the
distance, so the French and the English piece on sourdough can land together.

The table is still built offline, once per corpus change, and it has the same
shape as the one N0 and N1 return: the page-rendering code never changes.
What changes is what you now run — a few hundred megabytes of weights, a
process to keep warm, and a vector index once the corpus outgrows a list.

The encoder is a parameter with a real default, so the reader sees the loading
code while the test injects a local double.
"""

MODEL_NAME = "sentence-transformers/paraphrase-multilingual-MiniLM-L12-v2"


class EncodingFailed(RuntimeError):
    """The encoder could not be run, or returned something unusable."""


def article_text(article: dict) -> str:
    """One string per article. An encoder wants a sentence, not a bag of words."""
    return f"{article['title']}. {article['body']}"


def unit(vector) -> list[float]:
    """Normalise once, so that a cosine is a dot product afterwards."""
    values = [float(value) for value in vector]
    norm = sum(value * value for value in values) ** 0.5
    return [value / norm for value in values] if norm else values


def build_neighbour_table(articles: list[dict], encoder=None, k: int = 5,
                          minimum: float = 0.0) -> dict:
    """Return `{article id: [(neighbour id, score), ...]}`, best neighbour first."""
    if len(articles) < 2:
        return {article["id"]: [] for article in articles}
    texts = [article_text(article) for article in articles]

    if encoder is None:  # pragma: no cover - loads several hundred megabytes
        from sentence_transformers import SentenceTransformer

        encoder = SentenceTransformer(MODEL_NAME)

    # One batched call. Encoding article by article wastes most of the machine,
    # and this runs over the whole corpus every time an article is published.
    try:
        vectors = [unit(vector) for vector in encoder.encode(texts)]
    except Exception as error:  # noqa: BLE001 - a model failure is not the caller's fault
        raise EncodingFailed(str(error)) from error
    if len(vectors) != len(texts):
        raise EncodingFailed(f"{len(vectors)} vectors returned for {len(texts)} articles")

    table = {}
    for index, article in enumerate(articles):
        neighbours = []
        for position, other in enumerate(articles):
            if position == index:
                continue
            score = round(sum(x * y for x, y in zip(vectors[index], vectors[position])), 3)
            if score > minimum:
                neighbours.append((other["id"], score))
        # Ties broken by identifier, so that two builds give the same page.
        neighbours.sort(key=lambda neighbour: (-neighbour[1], neighbour[0]))
        table[article["id"]] = neighbours[:k]
    return table

/**
 * Related articles from self-hosted document embeddings.
 *
 * Rung N2. N1 compares words. Two articles that cover the same subject with
 * two vocabularies, or in two languages, share no term and score exactly
 * zero. An encoder maps each article to a vector where meaning, not spelling,
 * decides the distance, so the French and the English piece on sourdough can
 * land together.
 *
 * The table is still built offline, once per corpus change, and it has the
 * same shape as the one N0 and N1 return: the page-rendering code never
 * changes. What changes is what you now run — a few hundred megabytes of
 * weights, a process to keep warm, and a vector index once the corpus
 * outgrows an array.
 *
 * The encoder is a parameter with a real default, so the reader sees the
 * loading code while the test injects a local double.
 */

export const MODEL_NAME = 'Xenova/paraphrase-multilingual-MiniLM-L12-v2';

export class EncodingFailed extends Error {}

/** One string per article. An encoder wants a sentence, not a bag of words. */
export function articleText(article) {
  return `${article.title}. ${article.body}`;
}

/** Normalise once, so that a cosine is a dot product afterwards. */
export function unit(vector) {
  const norm = Math.hypot(...vector);
  return norm ? vector.map((value) => value / norm) : [...vector];
}

/**
 * Return `{ [article id]: [[neighbour id, score], ...] }`, best first.
 *
 * @param {object[]} articles
 * @param {object} options
 * @param {{encode: Function}} [options.encoder] injected so this can be
 *   tested without downloading a model; defaults to a real local encoder
 */
export async function buildNeighbourTable(articles, { encoder, k = 5, minimum = 0 } = {}) {
  if (articles.length < 2) return Object.fromEntries(articles.map((a) => [a.id, []]));
  const texts = articles.map(articleText);

  if (!encoder) {
    // Downloads and loads the weights, so it is never reached in the tests.
    const { pipeline } = await import('@xenova/transformers');
    const extract = await pipeline('feature-extraction', MODEL_NAME);
    encoder = { encode: async (batch) => (await extract(batch, { pooling: 'mean' })).tolist() };
  }

  // One batched call. Encoding article by article wastes most of the machine,
  // and this runs over the whole corpus every time an article is published.
  let vectors;
  try {
    vectors = (await encoder.encode(texts)).map(unit);
  } catch (error) {
    throw new EncodingFailed(String(error));
  }
  if (vectors.length !== texts.length) {
    throw new EncodingFailed(`${vectors.length} vectors returned for ${texts.length} articles`);
  }

  const table = {};
  articles.forEach((article, index) => {
    const neighbours = [];
    articles.forEach((other, position) => {
      if (position === index) return;
      const cosine = vectors[index].reduce((sum, value, d) => sum + value * vectors[position][d], 0);
      const score = Math.round(cosine * 1000) / 1000;
      if (score > minimum) neighbours.push([other.id, score]);
    });
    // Ties broken by identifier, so that two builds give the same page.
    neighbours.sort((a, b) => b[1] - a[1] || (a[0] < b[0] ? -1 : 1));
    table[article.id] = neighbours.slice(0, k);
  });
  return table;
}