Trier des produits par pertinence

"""
Trier des produits par un score pondéré : correspondance textuelle,
disponibilité, marge, popularité.

Niveau N0. Déterministe, sans dépendance, et surtout discutable : les quatre
pondérations sont des arguments, pas des constantes enfouies dans le code.
C'est tout l'intérêt de l'approche. Quand le commerce dit que le premier
résultat est mauvais, la discussion porte sur un nombre qu'un responsable de
rayon peut lire, et la réponse arrive dans l'après-midi plutôt que dans un
cycle de réentraînement.

Deux décisions la rendent utilisable.

Chaque signal est sur la même échelle de zéro à un avant que les pondérations
ne le touchent : le texte et la disponibilité par construction, la marge et
la popularité parce qu'une valeur hors de l'échelle y est ramenée plutôt que
laissée écraser les autres. Un poids de deux compte vraiment deux fois plus,
et le score, moyenne sur des pondérations qui ne peuvent pas être négatives,
reste dans cette échelle.

Ramenée, et non refusée : une marge de -0,05 existe pour de bon — un
déstockage vendu à perte — et cette fonction est appelée sur chaque page de
résultats. Un seul produit mal renseigné ne doit pas faire tomber toute la
page de catégorie. Les produits dont un signal a dû être déplacé ressortent
nommés, pour que le défaut se voie au lieu de se taire. Les pondérations sont
une autre affaire : elles viennent du code, et une pondération qui n'est pas
un nombre fini, nul ou positif, est refusée.

Le tri est stable : deux produits que le score ne sait pas séparer restent
dans l'ordre où le catalogue les a donnés. Un tri instable rebattrait les
résultats à égalité d'un affichage à l'autre, et plus personne ne saurait
reproduire une réclamation.
"""

import math
import unicodedata

# The order the weights are applied in. Fixing it keeps the arithmetic
# identical everywhere, which is what makes a ranking reproducible.
SIGNALS = ("text", "availability", "margin", "popularity")

# A starting point, not a truth. These are the numbers to argue about.
DEFAULT_WEIGHTS = {"text": 6.0, "availability": 2.0, "margin": 1.0, "popularity": 3.0}


def fold(text: str) -> str:
    """
    Lowercase and drop accents, so that "crème" finds "creme".

    Only the diacritics Latin scripts use (U+0300 to U+036F) are dropped: in
    Devanagari or Arabic the vowel signs are marks too, and dropping them
    would turn one word into another.
    """
    decomposed = unicodedata.normalize("NFD", text.lower())
    return "".join(c for c in decomposed if not "\u0300" <= c <= "\u036f")


def terms(text: str) -> list[str]:
    """Split on anything that is not a letter, a mark or a digit."""
    letters = "".join(c if c.isalnum() or unicodedata.category(c)[0] == "M" else " " for c in fold(text))
    return letters.split()


def text_match(query: str, product: dict) -> float:
    """
    Share of the query terms found at the start of a word of the product.

    Prefix matching, not equality: a shopper who types "chauss" is looking
    for "chaussures", and "sandale" finds "sandales". Not the other way round:
    "sandales" does not find "sandale".

    It is a share, not a relevance score. On a one-word query every product
    that holds the word scores 1.0, and the ranking is then decided entirely by
    stock, margin and popularity. If you already run a search engine — BM25 in
    PostgreSQL, Elasticsearch, Meilisearch — put its score here instead,
    normalised to nought-to-one. The value of this rung is the arbitration
    between the four weights, not this signal.
    """
    wanted = terms(query)
    if not wanted:
        return 0.0
    haystack = terms(product["title"] + " " + " ".join(product.get("tags", ())))
    found = sum(1 for term in wanted if any(word.startswith(term) for word in haystack))
    return found / len(wanted)


# The signals that come from the catalogue rather than from the query, and can
# therefore arrive out of scale.
FROM_DATA = ("margin", "popularity")


def on_scale(value) -> tuple[float, bool]:
    """
    Bring a value onto the nought-to-one scale, and say whether it had to move.

    Anything that is not a finite number reads as nought: a margin arriving as
    None, as a string or as NaN is a data fault, not a ranking signal, and it
    is reported rather than trusted.
    """
    number = value if isinstance(value, (int, float)) and not isinstance(value, bool) else None
    if number is None or not math.isfinite(number):
        return 0.0, True
    bounded = min(max(float(number), 0.0), 1.0)
    return bounded, bounded != float(number)


def out_of_scale(product: dict) -> list[str]:
    """The catalogue signals `signals` had to move, named for the caller."""
    return [name for name in FROM_DATA if on_scale(product[name])[1]]


def signals(product: dict, query: str) -> dict[str, float]:
    """The four signals, each on the same nought-to-one scale."""
    measured = {
        "text": text_match(query, product),
        "availability": 1.0 if product["in_stock"] else 0.0,
    }
    for name in FROM_DATA:
        measured[name] = on_scale(product[name])[0]
    return measured


def score(measured: dict[str, float], weights: dict[str, float]) -> float:
    """Weighted mean of the signals, so the score stays on the same scale."""
    missing = [name for name in SIGNALS if name not in weights]
    if missing:
        raise ValueError(f"every signal needs a weight, and these have none: {', '.join(missing)}")
    for name in SIGNALS:
        weight = weights[name]
        ok = isinstance(weight, (int, float)) and not isinstance(weight, bool) and math.isfinite(weight)
        if not ok or weight < 0:
            # Unlike a signal, a weight comes from the code, not from the
            # catalogue: it is refused rather than brought back into line.
            raise ValueError(f"a weight must be a finite number, nought or above: {name} is {weight!r}")
    total = 0.0
    weighted = 0.0
    for name in SIGNALS:
        total += weights[name]
        weighted += weights[name] * measured[name]
    return weighted / total if total else 0.0


def rank(products: list[dict], query: str, weights: dict = DEFAULT_WEIGHTS) -> list[dict]:
    """
    Sort the catalogue, best first, and hand back the reason for each place.

    Returning the signals alongside the score costs nothing and settles most
    arguments before they start: whoever asks why a product came third can see
    which signal held it back. `out_of_scale` names the catalogue signals that
    had to be brought back onto the scale, so that a margin of -0.05 shows up
    in the output instead of taking the page down.
    """
    scored = []
    for product in products:
        measured = signals(product, query)
        scored.append({
            "product": product,
            "score": score(measured, weights),
            "signals": measured,
            "out_of_scale": out_of_scale(product),
        })
    # Stable: products the score cannot separate keep their catalogue order.
    scored.sort(key=lambda row: -row["score"])
    return scored

/**
 * Trier des produits par un score pondéré : correspondance textuelle,
 * disponibilité, marge, popularité.
 *
 * Niveau N0. Déterministe, sans dépendance, et surtout discutable : les quatre
 * pondérations sont des arguments, pas des constantes enfouies dans le code.
 * C'est tout l'intérêt de l'approche. Quand le commerce dit que le premier
 * résultat est mauvais, la discussion porte sur un nombre qu'un responsable de
 * rayon peut lire, et la réponse arrive dans l'après-midi plutôt que dans un
 * cycle de réentraînement.
 *
 * Deux décisions la rendent utilisable.
 *
 * Chaque signal est sur la même échelle de zéro à un avant que les pondérations
 * ne le touchent : le texte et la disponibilité par construction, la marge et
 * la popularité parce qu'une valeur hors de l'échelle y est ramenée plutôt que
 * laissée écraser les autres. Un poids de deux compte vraiment deux fois plus,
 * et le score, moyenne sur des pondérations qui ne peuvent pas être négatives,
 * reste dans cette échelle.
 *
 * Ramenée, et non refusée : une marge de -0,05 existe pour de bon — un
 * déstockage vendu à perte — et cette fonction est appelée sur chaque page de
 * résultats. Un seul produit mal renseigné ne doit pas faire tomber toute la
 * page de catégorie. Les produits dont un signal a dû être déplacé ressortent
 * nommés, pour que le défaut se voie au lieu de se taire. Les pondérations sont
 * une autre affaire : elles viennent du code, et une pondération qui n'est pas
 * un nombre fini, nul ou positif, est refusée.
 *
 * Le tri est stable : deux produits que le score ne sait pas séparer restent
 * dans l'ordre où le catalogue les a donnés. Un tri instable rebattrait les
 * résultats à égalité d'un affichage à l'autre, et plus personne ne saurait
 * reproduire une réclamation.
 */

// The order the weights are applied in. Fixing it keeps the arithmetic
// identical everywhere, which is what makes a ranking reproducible.
export const SIGNALS = ['text', 'availability', 'margin', 'popularity'];

// A starting point, not a truth. These are the numbers to argue about.
export const DEFAULT_WEIGHTS = { text: 6, availability: 2, margin: 1, popularity: 3 };

/**
 * Lowercase and drop accents, so that "crème" finds "creme".
 *
 * Only the diacritics Latin scripts use (U+0300 to U+036F) are dropped: in
 * Devanagari or Arabic the vowel signs are marks too, and dropping them would
 * turn one word into another.
 */
export function fold(text) {
  return text.toLowerCase().normalize('NFD').replace(/[\u0300-\u036f]/g, '');
}

/** Split on anything that is not a letter, a mark or a digit. */
export function terms(text) {
  return fold(text).match(/[\p{L}\p{M}\p{N}]+/gu) ?? [];
}

/**
 * Share of the query terms found at the start of a word of the product.
 *
 * Prefix matching, not equality: a shopper who types "chauss" is looking for
 * "chaussures", and "sandale" finds "sandales". Not the other way round:
 * "sandales" does not find "sandale".
 *
 * It is a share, not a relevance score. On a one-word query every product that
 * holds the word scores 1.0, and the ranking is then decided entirely by stock,
 * margin and popularity. If you already run a search engine — BM25 in
 * PostgreSQL, Elasticsearch, Meilisearch — put its score here instead,
 * normalised to nought-to-one. The value of this rung is the arbitration
 * between the four weights, not this signal.
 */
export function textMatch(query, product) {
  const wanted = terms(query);
  if (wanted.length === 0) return 0;
  const haystack = terms(`${product.title} ${(product.tags ?? []).join(' ')}`);
  const found = wanted.filter((term) => haystack.some((word) => word.startsWith(term)));
  return found.length / wanted.length;
}

// The signals that come from the catalogue rather than from the query, and can
// therefore arrive out of scale.
export const FROM_DATA = ['margin', 'popularity'];

/**
 * Bring a value onto the nought-to-one scale, and say whether it had to move.
 *
 * Anything that is not a finite number reads as nought: a margin arriving as
 * null, as a string or as NaN is a data fault, not a ranking signal, and it is
 * reported rather than trusted.
 */
export function onScale(value) {
  if (typeof value !== 'number' || !Number.isFinite(value)) return [0, true];
  const bounded = Math.min(Math.max(value, 0), 1);
  return [bounded, bounded !== value];
}

/** The catalogue signals `signals` had to move, named for the caller. */
export function outOfScale(product) {
  return FROM_DATA.filter((name) => onScale(product[name])[1]);
}

/** The four signals, each on the same nought-to-one scale. */
export function signals(product, query) {
  // A field the catalogue does not have at all is a schema fault, not a dirty
  // value: it is refused, as it is in Python.
  for (const name of [...FROM_DATA, 'inStock']) {
    if (!(name in product)) throw new RangeError(`the catalogue gives no ${name} for this product`);
  }
  return {
    text: textMatch(query, product),
    availability: product.inStock ? 1 : 0,
    margin: onScale(product.margin)[0],
    popularity: onScale(product.popularity)[0],
  };
}

/** Weighted mean of the signals, so the score stays on the same scale. */
export function score(measured, weights) {
  const missing = SIGNALS.filter((name) => !(name in weights));
  if (missing.length > 0) {
    throw new RangeError(`every signal needs a weight, and these have none: ${missing.join(', ')}`);
  }
  for (const name of SIGNALS) {
    const weight = weights[name];
    // Unlike a signal, a weight comes from the code, not from the catalogue:
    // it is refused rather than brought back into line.
    if (typeof weight !== 'number' || !Number.isFinite(weight) || weight < 0) {
      throw new RangeError(`a weight must be a finite number, nought or above: ${name} is ${weight}`);
    }
  }
  let total = 0;
  let weighted = 0;
  for (const name of SIGNALS) {
    total += weights[name];
    weighted += weights[name] * measured[name];
  }
  return total ? weighted / total : 0;
}

/**
 * Sort the catalogue, best first, and hand back the reason for each place.
 *
 * Returning the signals alongside the score costs nothing and settles most
 * arguments before they start: whoever asks why a product came third can see
 * which signal held it back. `outOfScale` names the catalogue signals that had
 * to be brought back onto the scale, so that a margin of -0.05 shows up in the
 * output instead of taking the page down.
 */
export function rank(products, query, weights = DEFAULT_WEIGHTS) {
  const scored = products.map((product) => {
    const measured = signals(product, query);
    return {
      product,
      score: score(measured, weights),
      signals: measured,
      outOfScale: outOfScale(product),
    };
  });
  // Array.prototype.sort is stable: products the score cannot separate keep
  // their catalogue order.
  scored.sort((a, b) => b.score - a.score);
  return scored;
}