Afficher des articles similaires

"""
Articles liés par chevauchement d'étiquettes, pondéré par la rareté de
chaque étiquette.

Niveau N0. Sans dépendance, déterministe, et calculé une fois pour le fonds
entier au lieu de l'être à chaque affichage de page : les voisins d'un
article ne dépendent pas de qui le lit, donc aucun lecteur ne devrait jamais
attendre ce calcul.

Compter les étiquettes partagées est la version évidente, et c'est la
mauvaise. Une étiquette que tous les articles portent ne dit rien d'aucun
d'eux ; une étiquette que trois articles portent dit presque tout de ces
trois-là. Pondérer chaque étiquette par sa rareté fait toute la différence
entre un bloc utile et un bloc qui range l'annonce du site à côté de chaque
article du 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

/**
 * Articles liés par chevauchement d'étiquettes, pondéré par la rareté de
 * chaque étiquette.
 *
 * Niveau N0. Sans dépendance, déterministe, et calculé une fois pour le fonds
 * entier au lieu de l'être à chaque affichage de page : les voisins d'un
 * article ne dépendent pas de qui le lit, donc aucun lecteur ne devrait jamais
 * attendre ce calcul.
 *
 * Compter les étiquettes partagées est la version évidente, et c'est la
 * mauvaise. Une étiquette que tous les articles portent ne dit rien d'aucun
 * d'eux ; une étiquette que trois articles portent dit presque tout de ces
 * trois-là. Pondérer chaque étiquette par sa rareté fait toute la différence
 * entre un bloc utile et un bloc qui range l'annonce du site à côté de chaque
 * article du 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;
}

"""
Articles liés par des embeddings de documents auto-hébergés.

Niveau N2. N1 compare des mots. Deux articles qui traitent du même sujet
avec deux vocabulaires, ou dans deux langues, ne partagent aucun terme et
obtiennent exactement zéro. L'encodeur nommé ci-dessous est multilingue,
entraîné pour qu'une phrase et sa traduction tombent près l'une de l'autre :
c'est ce qui pourrait réunir l'article français et l'article anglais sur le
levain, ce que le double local du test ne fait pas. Il ne lit que le début
d'un long article (128 jetons en Python, 512 en JavaScript) et coupe le
reste. Cet écart est un piège : le même article reçoit deux vecteurs
différents selon l'environnement qui l'a encodé, et aucune erreur ne le
signale. Construisez la table et encodez un article neuf avec le même. Et
pour des articles, encoder le titre et le chapeau vaut souvent mieux que le
texte entier coupé au milieu d'un paragraphe : ils disent le sujet, et ils
tiennent dans la fenêtre.

La table est toujours construite hors ligne, une fois par modification du
fonds, et elle a la même forme que celle que rendent N0 et N1 : le code qui
affiche la page ne change jamais. Ce qui change, c'est ce que la
construction fait tourner : un modèle dont les poids sont téléchargés une
fois, puis chargés à chaque construction de la table.

L'encodeur est un paramètre doté d'une valeur par défaut réelle : le lecteur
voit ainsi le code de chargement, tandis que le test injecte un double local.
"""

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

/**
 * Articles liés par des embeddings de documents auto-hébergés.
 *
 * Niveau N2. N1 compare des mots. Deux articles qui traitent du même sujet
 * avec deux vocabulaires, ou dans deux langues, ne partagent aucun terme et
 * obtiennent exactement zéro. L'encodeur nommé ci-dessous est multilingue,
 * entraîné pour qu'une phrase et sa traduction tombent près l'une de l'autre :
 * c'est ce qui pourrait réunir l'article français et l'article anglais sur le
 * levain, ce que le double local du test ne fait pas. Il ne lit que le début
 * d'un long article (128 jetons en Python, 512 en JavaScript) et coupe le
 * reste. Cet écart est un piège : le même article reçoit deux vecteurs
 * différents selon l'environnement qui l'a encodé, et aucune erreur ne le
 * signale. Construisez la table et encodez un article neuf avec le même. Et
 * pour des articles, encoder le titre et le chapeau vaut souvent mieux que le
 * texte entier coupé au milieu d'un paragraphe : ils disent le sujet, et ils
 * tiennent dans la fenêtre.
 *
 * La table est toujours construite hors ligne, une fois par modification du
 * fonds, et elle a la même forme que celle que rendent N0 et N1 : le code qui
 * affiche la page ne change jamais. Ce qui change, c'est ce que la
 * construction fait tourner : un modèle dont les poids sont téléchargés une
 * fois, puis chargés à chaque construction de la table.
 *
 * L'encodeur est un paramètre doté d'une valeur par défaut réelle : le lecteur
 * voit ainsi le code de chargement, tandis que le test injecte un double local.
 */

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