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
import unicodedata
from collections import Counter


def tag_set(tags) -> set[str]:
    """Each tag once, in NFC, so that a tag typed on two systems meets itself."""
    if isinstance(tags, str):
        # A lone string would be read letter by letter, and "blog" would meet "gloss".
        raise TypeError("tags must be a list of strings, not a string")
    return {unicodedata.normalize("NFC", tag) for tag in tags}


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 tag_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 tag_set(first_tags)}
    second = {tag: weights.get(tag, 0.0) for tag in tag_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.
 */
/** Each tag once, in NFC, so that a tag typed on two systems meets itself. */
export function tagSet(tags) {
  // A lone string would be read letter by letter, and "blog" would meet "gloss".
  if (typeof tags === 'string') throw new TypeError('tags must be an array of strings, not a string');
  return new Set(Array.from(tags, (tag) => tag.normalize('NFC')));
}

export function tagWeights(articles) {
  const counts = new Map();
  for (const article of articles) {
    for (const tag of tagSet(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([...tagSet(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 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. The
encoder named below is a multilingual one, trained so that a sentence and its
translation land close together: that is what could bring the French and the
English piece on sourdough together, which the test's local double does not do.
It reads only the start of a long article (128 tokens in Python, 512 in
JavaScript) and truncates the rest. That difference is a trap: the same article
gets two different vectors depending on which runtime encoded it, with no error
anywhere. Build the table and encode a new article with the same one. And for
articles, encoding the title and the standfirst is usually better than the whole
text cut off mid-paragraph: they say what the piece is about, and they fit.

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 the build now runs: a model whose weights are downloaded
once, then loaded each time the table is built.

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

import math

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'] or ''}. {article['body'] or ''}"  # a NULL column is empty


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 - downloads and loads the weights
        from sentence_transformers import SentenceTransformer

        encoder = SentenceTransformer(MODEL_NAME)

    # One batched call, over the whole corpus, every time the table is built.
    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")
    # A NaN would silently empty the table, a short vector would score 1.0 with anything.
    if any(len(v) != len(vectors[0]) or not all(map(math.isfinite, v)) for v in vectors):
        raise EncodingFailed("vectors of different sizes, or values that are not finite numbers")

    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. The
 * encoder named below is a multilingual one, trained so that a sentence and its
 * translation land close together: that is what could bring the French and the
 * English piece on sourdough together, which the test's local double does not do.
 * It reads only the start of a long article (128 tokens in Python, 512 in
 * JavaScript) and truncates the rest. That difference is a trap: the same article
 * gets two different vectors depending on which runtime encoded it, with no error
 * anywhere. Build the table and encode a new article with the same one. And for
 * articles, encoding the title and the standfirst is usually better than the whole
 * text cut off mid-paragraph: they say what the piece is about, and they fit.
 *
 * 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 the build now runs: a model whose weights are downloaded
 * once, then loaded each time the table is built.
 *
 * 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 ?? ''}`; // a NULL column is empty
}

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

/**
 * 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('@huggingface/transformers');
    const extract = await pipeline('feature-extraction', MODEL_NAME);
    encoder = { encode: async (batch) => (await extract(batch, { pooling: 'mean' })).tolist() };
  }

  // One batched call, over the whole corpus, every time the table is built.
  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`);
  }
  // A NaN would silently empty the table, a short vector would score 1.0 with anything.
  if (vectors.some((v) => v.length !== vectors[0].length || !v.every(Number.isFinite))) {
    throw new EncodingFailed('vectors of different sizes, or values that are not finite numbers');
  }

  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;
}